main.go raw
1 // Command bethe-brute verifies the combinatorial explosion on a Bethe
2 // lattice with coordination number z=280 by brute-forcing path reversal
3 // at increasing depths until a single depth takes over 60 seconds.
4 //
5 // A "secret" is a random path of length D on the tree. The "public key"
6 // is a SHA-256 fingerprint of the path. Brute force enumerates paths
7 // of length D, hashing each, until it finds the match.
8 //
9 // At small D, all paths are enumerated to verify the count matches
10 // z × (z-1)^(D-1). At larger D, search stops at the first match
11 // (average cost = half the search space).
12 package main
13
14 import (
15 "crypto/sha256"
16 "encoding/binary"
17 "fmt"
18 "math"
19 "math/rand/v2"
20 "time"
21 )
22
23 const Z = 280 // coordination number
24
25 type path []uint16
26
27 func randomPath(d int) path {
28 p := make(path, d)
29 if d > 0 {
30 p[0] = uint16(rand.IntN(Z))
31 }
32 for i := 1; i < d; i++ {
33 p[i] = uint16(rand.IntN(Z - 1))
34 }
35 return p
36 }
37
38 func fingerprint(p path) [32]byte {
39 buf := make([]byte, len(p)*2)
40 for i, d := range p {
41 binary.LittleEndian.PutUint16(buf[i*2:], d)
42 }
43 return sha256.Sum256(buf)
44 }
45
46 // enumerateAll counts every path and records where the match occurs.
47 func enumerateAll(p path, level, depth int, target [32]byte, count, foundAt *int64) {
48 if level == depth {
49 *count++
50 if fingerprint(p) == target && *foundAt == 0 {
51 *foundAt = *count
52 }
53 return
54 }
55 limit := Z
56 if level > 0 {
57 limit = Z - 1
58 }
59 for d := 0; d < limit; d++ {
60 p[level] = uint16(d)
61 enumerateAll(p, level+1, depth, target, count, foundAt)
62 }
63 }
64
65 // searchUntilFound stops as soon as the match is found. Returns paths explored.
66 func searchUntilFound(p path, level, depth int, target [32]byte, count *int64) bool {
67 if level == depth {
68 *count++
69 return fingerprint(p) == target
70 }
71 limit := Z
72 if level > 0 {
73 limit = Z - 1
74 }
75 for d := 0; d < limit; d++ {
76 p[level] = uint16(d)
77 if searchUntilFound(p, level+1, depth, target, count) {
78 return true
79 }
80 }
81 return false
82 }
83
84 func predictedPaths(d int) float64 {
85 if d <= 0 {
86 return 0
87 }
88 return float64(Z) * math.Pow(float64(Z-1), float64(d-1))
89 }
90
91 func main() {
92 fmt.Printf("Bethe lattice brute-force verification\n")
93 fmt.Printf("z = %d, branching = %d, bits/step = %.2f\n\n",
94 Z, Z-1, math.Log2(float64(Z-1)))
95
96 // Track rates across depths for scaling analysis.
97 var prevElapsed time.Duration
98
99 for d := 1; ; d++ {
100 predicted := predictedPaths(d)
101 bits := math.Log2(predicted)
102
103 secret := randomPath(d)
104 pub := fingerprint(secret)
105
106 fmt.Printf("D=%d | %.1f bits | secret=%v | pub=%x\n",
107 d, bits, []uint16(secret), pub[:8])
108
109 p := make(path, d)
110 start := time.Now()
111
112 var explored int64
113 var method string
114
115 // Full enumeration up to D=3 (21M paths, ~2s).
116 // Beyond that, search-until-found.
117 if d <= 3 {
118 var foundAt int64
119 enumerateAll(p, 0, d, pub, &explored, &foundAt)
120 method = "full"
121 predInt := int64(predicted)
122 fmt.Printf(" enumerated: %d | predicted: %d | match: %v\n",
123 explored, predInt, explored == predInt)
124 fmt.Printf(" found at: #%d (%.1f%%)\n",
125 foundAt, 100*float64(foundAt)/float64(explored))
126 } else {
127 found := searchUntilFound(p, 0, d, pub, &explored)
128 method = "first-match"
129 fmt.Printf(" explored: %d / %.0f (%.2f%%)\n",
130 explored, predicted, 100*float64(explored)/predicted)
131 fmt.Printf(" found: %v\n", found)
132 }
133
134 elapsed := time.Since(start)
135 rate := float64(explored) / elapsed.Seconds()
136
137 // Scaling ratio from previous depth.
138 scaling := ""
139 if prevElapsed > 0 && d > 1 {
140 ratio := elapsed.Seconds() / prevElapsed.Seconds()
141 // For full enumeration, expected ratio is 279.
142 // For first-match, ratio varies with luck but averages ~279.
143 scaling = fmt.Sprintf(" | scaling: %.1fx (expected ~279x)", ratio)
144 }
145
146 // Extrapolate to 128-bit security (D=16).
147 paths16 := float64(Z) * math.Pow(float64(Z-1), 15)
148 years16 := (paths16 / rate) / 31557600
149
150 fmt.Printf(" %s | %v | %.1e paths/sec%s\n", method, elapsed, rate, scaling)
151 fmt.Printf(" D=16 extrapolation: %.1e years\n\n", years16)
152
153 prevElapsed = elapsed
154
155 if elapsed >= 60*time.Second {
156 fmt.Printf("Reached 60s threshold at D=%d. Stopping.\n", d)
157 break
158 }
159 }
160 }
161