// Command bethe-brute verifies the combinatorial explosion on a Bethe
// lattice with coordination number z=280 by brute-forcing path reversal
// at increasing depths until a single depth takes over 60 seconds.
//
// A "secret" is a random path of length D on the tree. The "public key"
// is a SHA-256 fingerprint of the path. Brute force enumerates paths
// of length D, hashing each, until it finds the match.
//
// At small D, all paths are enumerated to verify the count matches
// z × (z-1)^(D-1). At larger D, search stops at the first match
// (average cost = half the search space).
package main

import (
	"crypto/sha256"
	"encoding/binary"
	"fmt"
	"math"
	"math/rand/v2"
	"time"
)

const Z = 280 // coordination number

type path []uint16

func randomPath(d int) path {
	p := make(path, d)
	if d > 0 {
		p[0] = uint16(rand.IntN(Z))
	}
	for i := 1; i < d; i++ {
		p[i] = uint16(rand.IntN(Z - 1))
	}
	return p
}

func fingerprint(p path) [32]byte {
	buf := make([]byte, len(p)*2)
	for i, d := range p {
		binary.LittleEndian.PutUint16(buf[i*2:], d)
	}
	return sha256.Sum256(buf)
}

// enumerateAll counts every path and records where the match occurs.
func enumerateAll(p path, level, depth int, target [32]byte, count, foundAt *int64) {
	if level == depth {
		*count++
		if fingerprint(p) == target && *foundAt == 0 {
			*foundAt = *count
		}
		return
	}
	limit := Z
	if level > 0 {
		limit = Z - 1
	}
	for d := 0; d < limit; d++ {
		p[level] = uint16(d)
		enumerateAll(p, level+1, depth, target, count, foundAt)
	}
}

// searchUntilFound stops as soon as the match is found. Returns paths explored.
func searchUntilFound(p path, level, depth int, target [32]byte, count *int64) bool {
	if level == depth {
		*count++
		return fingerprint(p) == target
	}
	limit := Z
	if level > 0 {
		limit = Z - 1
	}
	for d := 0; d < limit; d++ {
		p[level] = uint16(d)
		if searchUntilFound(p, level+1, depth, target, count) {
			return true
		}
	}
	return false
}

func predictedPaths(d int) float64 {
	if d <= 0 {
		return 0
	}
	return float64(Z) * math.Pow(float64(Z-1), float64(d-1))
}

func main() {
	fmt.Printf("Bethe lattice brute-force verification\n")
	fmt.Printf("z = %d, branching = %d, bits/step = %.2f\n\n",
		Z, Z-1, math.Log2(float64(Z-1)))

	// Track rates across depths for scaling analysis.
	var prevElapsed time.Duration

	for d := 1; ; d++ {
		predicted := predictedPaths(d)
		bits := math.Log2(predicted)

		secret := randomPath(d)
		pub := fingerprint(secret)

		fmt.Printf("D=%d | %.1f bits | secret=%v | pub=%x\n",
			d, bits, []uint16(secret), pub[:8])

		p := make(path, d)
		start := time.Now()

		var explored int64
		var method string

		// Full enumeration up to D=3 (21M paths, ~2s).
		// Beyond that, search-until-found.
		if d <= 3 {
			var foundAt int64
			enumerateAll(p, 0, d, pub, &explored, &foundAt)
			method = "full"
			predInt := int64(predicted)
			fmt.Printf("  enumerated: %d | predicted: %d | match: %v\n",
				explored, predInt, explored == predInt)
			fmt.Printf("  found at: #%d (%.1f%%)\n",
				foundAt, 100*float64(foundAt)/float64(explored))
		} else {
			found := searchUntilFound(p, 0, d, pub, &explored)
			method = "first-match"
			fmt.Printf("  explored: %d / %.0f (%.2f%%)\n",
				explored, predicted, 100*float64(explored)/predicted)
			fmt.Printf("  found: %v\n", found)
		}

		elapsed := time.Since(start)
		rate := float64(explored) / elapsed.Seconds()

		// Scaling ratio from previous depth.
		scaling := ""
		if prevElapsed > 0 && d > 1 {
			ratio := elapsed.Seconds() / prevElapsed.Seconds()
			// For full enumeration, expected ratio is 279.
			// For first-match, ratio varies with luck but averages ~279.
			scaling = fmt.Sprintf(" | scaling: %.1fx (expected ~279x)", ratio)
		}

		// Extrapolate to 128-bit security (D=16).
		paths16 := float64(Z) * math.Pow(float64(Z-1), 15)
		years16 := (paths16 / rate) / 31557600

		fmt.Printf("  %s | %v | %.1e paths/sec%s\n", method, elapsed, rate, scaling)
		fmt.Printf("  D=16 extrapolation: %.1e years\n\n", years16)

		prevElapsed = elapsed

		if elapsed >= 60*time.Second {
			fmt.Printf("Reached 60s threshold at D=%d. Stopping.\n", d)
			break
		}
	}
}