proof_foundations_test.go raw
1 package crypto
2
3 // Track 1: Algebraic Foundations — exhaustive proofs over finite state spaces.
4 //
5 // Each test verifies a mathematical property by exhaustive enumeration.
6 // If a test passes, the claim is proven for the entire domain. These are
7 // not probabilistic checks — they are complete proofs over finite sets.
8
9 import (
10 "sort"
11 "testing"
12
13 "git.mleku.dev/mleku/dendrite/pkg/axiom"
14 "git.mleku.dev/mleku/dendrite/pkg/dissolve"
15 "git.mleku.dev/mleku/dendrite/pkg/lattice"
16 "git.mleku.dev/mleku/dendrite/pkg/permutation"
17 "git.mleku.dev/mleku/dendrite/pkg/projection"
18 "git.mleku.dev/mleku/dendrite/pkg/ratio"
19 "git.mleku.dev/mleku/dendrite/pkg/state"
20 )
21
22 // ---- S_3 Group Axioms (exhaustive over all 6 elements) ----
23
24 func TestS3Closure(t *testing.T) {
25 // For all a, b in S_3: a.Compose(b) is in S_3.
26 all := permutation.All()
27 for _, a := range all {
28 for _, b := range all {
29 c := a.Compose(b)
30 if c >= permutation.Count {
31 t.Errorf("Compose(%v, %v) = %d, out of range", a, b, c)
32 }
33 }
34 }
35 }
36
37 func TestS3Identity(t *testing.T) {
38 // For all a in S_3: Identity.Compose(a) == a == a.Compose(Identity).
39 all := permutation.All()
40 for _, a := range all {
41 if permutation.Identity.Compose(a) != a {
42 t.Errorf("Identity.Compose(%v) = %v, want %v",
43 a, permutation.Identity.Compose(a), a)
44 }
45 if a.Compose(permutation.Identity) != a {
46 t.Errorf("%v.Compose(Identity) = %v, want %v",
47 a, a.Compose(permutation.Identity), a)
48 }
49 }
50 }
51
52 func TestS3Inverse(t *testing.T) {
53 // For all a in S_3: a.Compose(a^-1) == Identity == a^-1.Compose(a).
54 all := permutation.All()
55 for _, a := range all {
56 inv := a.Inverse()
57 if a.Compose(inv) != permutation.Identity {
58 t.Errorf("%v.Compose(%v.Inverse()) = %v, want Identity",
59 a, a, a.Compose(inv))
60 }
61 if inv.Compose(a) != permutation.Identity {
62 t.Errorf("%v.Inverse().Compose(%v) = %v, want Identity",
63 a, a, inv.Compose(a))
64 }
65 }
66 }
67
68 func TestS3Associativity(t *testing.T) {
69 // For all a, b, c in S_3: (a.b).c == a.(b.c).
70 // 6^3 = 216 cases — exhaustive.
71 all := permutation.All()
72 for _, a := range all {
73 for _, b := range all {
74 for _, c := range all {
75 ab_c := a.Compose(b).Compose(c)
76 a_bc := a.Compose(b.Compose(c))
77 if ab_c != a_bc {
78 t.Errorf("(%v.%v).%v = %v, but %v.(%v.%v) = %v",
79 a, b, c, ab_c, a, b, c, a_bc)
80 }
81 }
82 }
83 }
84 }
85
86 func TestS3OrderOfElements(t *testing.T) {
87 // S_3 element orders:
88 // Identity: order 1
89 // Transpositions (Swap01, Swap02, Swap12): order 2
90 // 3-cycles (Cycle012, Cycle021): order 3
91 expected := map[permutation.Perm]int{
92 permutation.Identity: 1,
93 permutation.Swap01: 2,
94 permutation.Swap02: 2,
95 permutation.Swap12: 2,
96 permutation.Cycle012: 3,
97 permutation.Cycle021: 3,
98 }
99
100 for p, wantOrder := range expected {
101 current := p
102 for i := 1; i <= 6; i++ {
103 if current == permutation.Identity {
104 if i != wantOrder {
105 t.Errorf("order of %v = %d, want %d", p, i, wantOrder)
106 }
107 break
108 }
109 current = current.Compose(p)
110 }
111 }
112 }
113
114 func TestS3NonAbelian(t *testing.T) {
115 // S_3 is non-abelian: there exist a, b where a.b != b.a.
116 // Verify at least one non-commutative pair exists.
117 found := false
118 all := permutation.All()
119 for _, a := range all {
120 for _, b := range all {
121 if a.Compose(b) != b.Compose(a) {
122 found = true
123 break
124 }
125 }
126 if found {
127 break
128 }
129 }
130 if !found {
131 t.Error("S_3 should be non-abelian but all pairs commute")
132 }
133 }
134
135 // ---- Trigram Permutation Action (exhaustive over 8 trigrams × 6 perms) ----
136
137 func TestPermActionBijective(t *testing.T) {
138 // For each permutation p, the map t -> p.ApplyTrigram(t) is a bijection on {0..7}.
139 all := permutation.All()
140 for _, p := range all {
141 seen := make(map[state.Trigram]bool)
142 for tri := range uint8(8) {
143 result := p.ApplyTrigram(state.Trigram(tri))
144 if result > 7 {
145 t.Errorf("%v.ApplyTrigram(%d) = %d, out of range", p, tri, result)
146 }
147 if seen[result] {
148 t.Errorf("%v.ApplyTrigram is not injective: %d maps to %d (already seen)", p, tri, result)
149 }
150 seen[result] = true
151 }
152 if len(seen) != 8 {
153 t.Errorf("%v.ApplyTrigram hit %d/8 values (not surjective)", p, len(seen))
154 }
155 }
156 }
157
158 func TestPermActionHomomorphism(t *testing.T) {
159 // (a.b).ApplyTrigram(t) == a.ApplyTrigram(b.ApplyTrigram(t))
160 // for all a, b in S_3 and all trigrams t.
161 // 6 × 6 × 8 = 288 cases — exhaustive.
162 all := permutation.All()
163 for _, a := range all {
164 for _, b := range all {
165 ab := a.Compose(b)
166 for tri := range uint8(8) {
167 t_ := state.Trigram(tri)
168 direct := ab.ApplyTrigram(t_)
169 stepped := a.ApplyTrigram(b.ApplyTrigram(t_))
170 if direct != stepped {
171 t.Errorf("(%v.%v).Apply(%d)=%d, but %v.Apply(%v.Apply(%d))=%d",
172 a, b, tri, direct, a, b, tri, stepped)
173 }
174 }
175 }
176 }
177 }
178
179 func TestPermIdentityFixesAllTrigrams(t *testing.T) {
180 // Identity.ApplyTrigram(t) == t for all t.
181 for tri := range uint8(8) {
182 result := permutation.Identity.ApplyTrigram(state.Trigram(tri))
183 if result != state.Trigram(tri) {
184 t.Errorf("Identity.ApplyTrigram(%d) = %d, want %d", tri, result, tri)
185 }
186 }
187 }
188
189 // ---- Hexagram Permutation Action (exhaustive over 64 hexagrams × 6 perms) ----
190
191 func TestHexPermConsistent(t *testing.T) {
192 // ApplyHexagram applies the permutation to both inner and outer trigrams.
193 // For all p in S_3 and all hexagrams h:
194 // p.ApplyHexagram(h) == Hex(p.ApplyTrigram(h.Inner()), p.ApplyTrigram(h.Outer()))
195 all := permutation.All()
196 for _, p := range all {
197 for h := range uint8(64) {
198 hex := state.Hexagram(h)
199 got := p.ApplyHexagram(hex)
200 want := state.Hex(p.ApplyTrigram(hex.Inner()), p.ApplyTrigram(hex.Outer()))
201 if got != want {
202 t.Errorf("%v.ApplyHexagram(%d): got %d, want %d", p, h, got, want)
203 }
204 }
205 }
206 }
207
208 // ---- Projection Key-to-Perm Mapping (exhaustive over 8 keys) ----
209
210 func TestProjectionKeyToPermSurjective(t *testing.T) {
211 // All 6 S_3 elements are reachable from the 8 projection keys.
212 // Keys 6,7 are collapse points that alias to existing perms.
213 seen := make(map[permutation.Perm]bool)
214 for k := range uint8(projection.KeyCount) {
215 p := projection.Key(k).Permutation()
216 seen[p] = true
217 }
218 if len(seen) != int(permutation.Count) {
219 t.Errorf("key-to-perm covers %d/%d permutations", len(seen), permutation.Count)
220 }
221 }
222
223 func TestProjectionCollapseAliases(t *testing.T) {
224 // Collapse keys alias to specific permutations:
225 // KeyCollapseA (110) → Identity
226 // KeyCollapseB (111) → Swap12
227 if projection.KeyCollapseA.Permutation() != permutation.Identity {
228 t.Errorf("CollapseA.Perm = %v, want Identity", projection.KeyCollapseA.Permutation())
229 }
230 if projection.KeyCollapseB.Permutation() != permutation.Swap12 {
231 t.Errorf("CollapseB.Perm = %v, want Swap12", projection.KeyCollapseB.Permutation())
232 }
233 }
234
235 func TestProjectionKeyOrder(t *testing.T) {
236 // Verify geometric orders: collapse=1, face/edge=2, vertex=3.
237 orders := map[projection.Key]int{
238 projection.KeyFaceXY: 2,
239 projection.KeyFaceXZ: 2,
240 projection.KeyFaceYZ: 2,
241 projection.KeyEdgeBias: 2,
242 projection.KeyVertexA: 3,
243 projection.KeyVertexB: 3,
244 projection.KeyCollapseA: 1,
245 projection.KeyCollapseB: 1,
246 }
247 for k, want := range orders {
248 if got := k.Order(); got != want {
249 t.Errorf("Key(%d).Order() = %d, want %d", k, got, want)
250 }
251 }
252 }
253
254 func TestProjectionPackRoundTrip(t *testing.T) {
255 // For all vertex × key pairs, Pack → Vertex/Key round-trips.
256 // 8 × 8 = 64 cases — exhaustive.
257 for v := range uint8(projection.VertexCount) {
258 for k := range uint8(projection.KeyCount) {
259 p := projection.Pack(projection.Vertex(v), projection.Key(k))
260 if p.Vertex() != projection.Vertex(v) {
261 t.Errorf("Pack(%d,%d).Vertex() = %d", v, k, p.Vertex())
262 }
263 if p.Key() != projection.Key(k) {
264 t.Errorf("Pack(%d,%d).Key() = %d", v, k, p.Key())
265 }
266 }
267 }
268 }
269
270 func TestProjection64Distinct(t *testing.T) {
271 // All 64 Projection values are distinct.
272 seen := make(map[projection.Projection]bool)
273 for v := range uint8(projection.VertexCount) {
274 for k := range uint8(projection.KeyCount) {
275 p := projection.Pack(projection.Vertex(v), projection.Key(k))
276 if seen[p] {
277 t.Errorf("duplicate projection for vertex=%d, key=%d", v, k)
278 }
279 seen[p] = true
280 }
281 }
282 if len(seen) != projection.ProjectionCount {
283 t.Errorf("got %d distinct projections, want %d", len(seen), projection.ProjectionCount)
284 }
285 }
286
287 // ---- ContextualLockIn Formula Verification (exhaustive over rationals) ----
288
289 func TestContextualLockInFormula(t *testing.T) {
290 // Formula: 0.3 + 0.7 * (occupied / total_neighbors)
291 // Verified for all combinations of occupied in {0..total} and total in {1..10}.
292 for total := 1; total <= 10; total++ {
293 for occupied := 0; occupied <= total; occupied++ {
294 rate := ratio.New(int64(occupied), int64(total))
295 expected := ratio.New(3, 10).Add(ratio.New(7, 10).Mul(rate))
296
297 // Build a lattice node with `total` neighbors, `occupied` of them occupied.
298 l := lattice.New()
299 center := l.AddNode([]axiom.Constraint{tagConstraint{"test"}})
300
301 var neighbors []*lattice.Node
302 for i := 0; i < total; i++ {
303 nb := l.AddNode([]axiom.Constraint{tagConstraint{"test"}})
304 l.Connect(center, nb)
305 neighbors = append(neighbors, nb)
306 }
307
308 // Bond the center node.
309 center.Bond(testElem{"test", "center"})
310
311 // Bond `occupied` neighbors.
312 for i := 0; i < occupied; i++ {
313 neighbors[i].Bond(testElem{"test", "nb"})
314 }
315
316 got := center.ContextualLockIn()
317 if !got.Equal(expected) {
318 t.Errorf("ContextualLockIn(occupied=%d, total=%d) = %s, want %s",
319 occupied, total, got, expected)
320 }
321 }
322 }
323 }
324
325 func TestContextualLockInBounds(t *testing.T) {
326 // ContextualLockIn is always in [0.3, 1.0] for bonded nodes with neighbors.
327 lo := ratio.New(3, 10)
328 hi := ratio.One
329
330 for total := 1; total <= 10; total++ {
331 for occupied := 0; occupied <= total; occupied++ {
332 l := lattice.New()
333 center := l.AddNode([]axiom.Constraint{tagConstraint{"test"}})
334 for i := 0; i < total; i++ {
335 nb := l.AddNode([]axiom.Constraint{tagConstraint{"test"}})
336 l.Connect(center, nb)
337 if i < occupied {
338 nb.Bond(testElem{"test", "nb"})
339 }
340 }
341 center.Bond(testElem{"test", "center"})
342
343 got := center.ContextualLockIn()
344 if got.Less(lo) {
345 t.Errorf("ContextualLockIn(occ=%d, total=%d) = %s < 0.3", occupied, total, got)
346 }
347 if hi.Less(got) {
348 t.Errorf("ContextualLockIn(occ=%d, total=%d) = %s > 1.0", occupied, total, got)
349 }
350 }
351 }
352 }
353
354 func TestContextualLockInZeroForUnbonded(t *testing.T) {
355 // An unbonded node returns zero regardless of neighbors.
356 l := lattice.New()
357 center := l.AddNode([]axiom.Constraint{tagConstraint{"test"}})
358 nb := l.AddNode([]axiom.Constraint{tagConstraint{"test"}})
359 l.Connect(center, nb)
360 nb.Bond(testElem{"test", "nb"})
361
362 got := center.ContextualLockIn()
363 if !got.IsZero() {
364 t.Errorf("ContextualLockIn of unbonded node = %s, want 0", got)
365 }
366 }
367
368 func TestContextualLockInNoNeighbors(t *testing.T) {
369 // A bonded node with no neighbors returns 0.3.
370 l := lattice.New()
371 n := l.AddNode([]axiom.Constraint{tagConstraint{"test"}})
372 n.Bond(testElem{"test", "solo"})
373
374 got := n.ContextualLockIn()
375 if !got.Equal(ratio.New(3, 10)) {
376 t.Errorf("ContextualLockIn of isolated node = %s, want 3/10", got)
377 }
378 }
379
380 // ---- Dissolution Determinism ----
381
382 func TestDissolutionDeterministic(t *testing.T) {
383 // Running ScanOnce on two identically constructed lattices with the
384 // same config produces the same dissolution set.
385 build := func() *lattice.Lattice {
386 l := lattice.New()
387 var nodes []*lattice.Node
388 for range 10 {
389 n := l.AddNode([]axiom.Constraint{tagConstraint{"word"}})
390 nodes = append(nodes, n)
391 }
392 for i := range nodes {
393 l.Connect(nodes[i], nodes[(i+1)%len(nodes)])
394 }
395 // Bond only every other node → isolated bonds have low contextual lock-in.
396 for i := 0; i < 10; i += 2 {
397 nodes[i].Bond(testElem{"word", "x"})
398 }
399 return l
400 }
401
402 cfg := dissolve.Config{Threshold: ratio.New(6, 10)}
403
404 // Run on first lattice.
405 l1 := build()
406 d1 := make(chan axiom.Element, 10)
407 e1 := make(chan dissolve.Event, 10)
408 dissolve.ScanOnce(l1, cfg, d1, e1)
409 close(d1)
410 close(e1)
411 var ids1 []uint64
412 for ev := range e1 {
413 ids1 = append(ids1, uint64(ev.NodeID))
414 }
415 sort.Slice(ids1, func(i, j int) bool { return ids1[i] < ids1[j] })
416
417 // Run on second lattice.
418 l2 := build()
419 d2 := make(chan axiom.Element, 10)
420 e2 := make(chan dissolve.Event, 10)
421 dissolve.ScanOnce(l2, cfg, d2, e2)
422 close(d2)
423 close(e2)
424 var ids2 []uint64
425 for ev := range e2 {
426 ids2 = append(ids2, uint64(ev.NodeID))
427 }
428 sort.Slice(ids2, func(i, j int) bool { return ids2[i] < ids2[j] })
429
430 // Same dissolution set.
431 if len(ids1) != len(ids2) {
432 t.Fatalf("dissolution count differs: %d vs %d", len(ids1), len(ids2))
433 }
434 for i := range ids1 {
435 if ids1[i] != ids2[i] {
436 t.Errorf("dissolution[%d]: %d vs %d", i, ids1[i], ids2[i])
437 }
438 }
439 }
440
441 func TestDissolutionThresholdMonotonic(t *testing.T) {
442 // Higher threshold dissolves at least as many nodes as lower threshold.
443 build := func() *lattice.Lattice {
444 l := lattice.New()
445 var nodes []*lattice.Node
446 for range 20 {
447 n := l.AddNode([]axiom.Constraint{tagConstraint{"word"}})
448 nodes = append(nodes, n)
449 }
450 for i := range nodes {
451 l.Connect(nodes[i], nodes[(i+1)%len(nodes)])
452 }
453 // Bond all nodes.
454 for _, n := range nodes {
455 n.Bond(testElem{"word", "x"})
456 }
457 return l
458 }
459
460 thresholds := []ratio.Ratio{
461 ratio.New(1, 10),
462 ratio.New(3, 10),
463 ratio.New(5, 10),
464 ratio.New(7, 10),
465 ratio.New(9, 10),
466 }
467
468 var prevCount int
469 for i, threshold := range thresholds {
470 l := build()
471 d := make(chan axiom.Element, 20)
472 e := make(chan dissolve.Event, 20)
473 dissolve.ScanOnce(l, dissolve.Config{Threshold: threshold}, d, e)
474 close(d)
475 close(e)
476 count := 0
477 for range e {
478 count++
479 }
480 for range d {
481 }
482 if i > 0 && count < prevCount {
483 t.Errorf("threshold %s dissolved %d, but lower threshold dissolved %d",
484 threshold, count, prevCount)
485 }
486 prevCount = count
487 }
488 }
489
490 // ---- Bond Determinism ----
491
492 func TestBondDeterministic(t *testing.T) {
493 // Bond(element) on the same node with the same constraint produces
494 // the same result (success/failure) deterministically.
495 for range 10 {
496 l := lattice.New()
497 n := l.AddNode([]axiom.Constraint{tagConstraint{"word"}})
498 e := testElem{"word", "test"}
499 result := n.Bond(e)
500 if !result {
501 t.Error("matching element should bond")
502 }
503 }
504 }
505
506 func TestBondRejectsNonMatching(t *testing.T) {
507 // An element that doesn't match the constraint is rejected.
508 l := lattice.New()
509 n := l.AddNode([]axiom.Constraint{tagConstraint{"word"}})
510 e := testElem{"punct", "!"}
511 if n.Bond(e) {
512 t.Error("mismatched element should not bond")
513 }
514 }
515
516 func TestBondIdempotent(t *testing.T) {
517 // Bonding a second element to an already-occupied node fails.
518 l := lattice.New()
519 n := l.AddNode([]axiom.Constraint{tagConstraint{"word"}})
520 n.Bond(testElem{"word", "a"})
521 if n.Bond(testElem{"word", "b"}) {
522 t.Error("bonding to occupied node should fail")
523 }
524 }
525
526 // ---- Hamadryad Hash Determinism and Distinctness ----
527
528 func TestHamadryadDeterministic(t *testing.T) {
529 // Same input → same hash.
530 msgs := []string{"", "hello", "dendrite", "test message"}
531 for _, msg := range msgs {
532 h1 := Hash([]byte(msg))
533 h2 := Hash([]byte(msg))
534 if h1 != h2 {
535 t.Errorf("Hash(%q) not deterministic", msg)
536 }
537 }
538 }
539
540 func TestHamadryadDistinct(t *testing.T) {
541 // Different inputs → different hashes (collision resistance test over small domain).
542 msgs := []string{"a", "b", "c", "d", "aa", "ab", "ba", "bb", "", "test"}
543 hashes := make(map[Hamadryad]string)
544 for _, msg := range msgs {
545 h := Hash([]byte(msg))
546 if prev, ok := hashes[h]; ok {
547 t.Errorf("collision: Hash(%q) == Hash(%q)", msg, prev)
548 }
549 hashes[h] = msg
550 }
551 }
552
553 // NTT correctness is proven exhaustively in ntt_test.go:
554 // - TestNTTRoundTrip: forward + inverse recovers original polynomial
555 // - TestNTTConvolution: pointwise multiply = polynomial product mod x^64+1
556 // - TestNTTNegacyclicWraparound: x^64 ≡ -1 (mod x^64+1)
557 // - TestBitRev6: bit-reversal permutation is an involution
558 // - TestPowMod: modular exponentiation correctness
559 // Those tests are exhaustive over their input domains and are not duplicated here.
560
561 // ---- Hexagram State Space ----
562
563 func TestHexagramInnerOuterRoundTrip(t *testing.T) {
564 // For all 64 hexagrams: Hex(h.Inner(), h.Outer()) == h.
565 for h := range uint8(64) {
566 hex := state.Hexagram(h)
567 reconstructed := state.Hex(hex.Inner(), hex.Outer())
568 if reconstructed != hex {
569 t.Errorf("Hex((%d).Inner(), (%d).Outer()) = %d, want %d",
570 h, h, reconstructed, h)
571 }
572 }
573 }
574
575 func TestHexagramInnerOuterPartition(t *testing.T) {
576 // Inner uses low 3 bits, outer uses high 3 bits.
577 // All 8 × 8 = 64 combinations should be representable.
578 seen := make(map[state.Hexagram]bool)
579 for inner := range uint8(8) {
580 for outer := range uint8(8) {
581 h := state.Hex(state.Trigram(inner), state.Trigram(outer))
582 if h.Inner() != state.Trigram(inner) {
583 t.Errorf("Hex(%d,%d).Inner() = %d", inner, outer, h.Inner())
584 }
585 if h.Outer() != state.Trigram(outer) {
586 t.Errorf("Hex(%d,%d).Outer() = %d", inner, outer, h.Outer())
587 }
588 seen[h] = true
589 }
590 }
591 if len(seen) != 64 {
592 t.Errorf("got %d distinct hexagrams, want 64", len(seen))
593 }
594 }
595
596 // ---- Trigram Bit Manipulation ----
597
598 func TestTrigramBitAccessors(t *testing.T) {
599 // For all 8 trigrams, verify bit accessors match bit positions.
600 for tri := range uint8(8) {
601 tg := state.Trigram(tri)
602 if tg.Bonding() != (tri&1 != 0) {
603 t.Errorf("Trigram(%d).Bonding() = %v, want %v", tri, tg.Bonding(), tri&1 != 0)
604 }
605 if tg.Constraint() != (tri&2 != 0) {
606 t.Errorf("Trigram(%d).Constraint() = %v, want %v", tri, tg.Constraint(), tri&2 != 0)
607 }
608 if tg.Energy() != (tri&4 != 0) {
609 t.Errorf("Trigram(%d).Energy() = %v, want %v", tri, tg.Energy(), tri&4 != 0)
610 }
611 }
612 }
613
614 func TestTrigramFlipInvolution(t *testing.T) {
615 // Flipping the same bit twice returns to original.
616 for tri := range uint8(8) {
617 for bit := range uint8(3) {
618 tg := state.Trigram(tri)
619 if tg.Flip(bit).Flip(bit) != tg {
620 t.Errorf("Trigram(%d).Flip(%d).Flip(%d) != original", tri, bit, bit)
621 }
622 }
623 }
624 }
625
626 // ---- Ratio Arithmetic Correctness ----
627
628 func TestRatioFieldAxioms(t *testing.T) {
629 // Verify commutativity, associativity, distributivity over a small domain.
630 vals := []ratio.Ratio{
631 ratio.Zero, ratio.One, ratio.Half,
632 ratio.New(1, 3), ratio.New(2, 3), ratio.New(3, 7),
633 ratio.New(-1, 2), ratio.New(5, 1),
634 }
635
636 for _, a := range vals {
637 for _, b := range vals {
638 // Commutativity of addition.
639 if !a.Add(b).Equal(b.Add(a)) {
640 t.Errorf("%s + %s != %s + %s", a, b, b, a)
641 }
642 // Commutativity of multiplication.
643 if !a.Mul(b).Equal(b.Mul(a)) {
644 t.Errorf("%s * %s != %s * %s", a, b, b, a)
645 }
646 }
647 }
648
649 // Distributivity: a*(b+c) == a*b + a*c.
650 for _, a := range vals {
651 for _, b := range vals {
652 for _, c := range vals {
653 lhs := a.Mul(b.Add(c))
654 rhs := a.Mul(b).Add(a.Mul(c))
655 if !lhs.Equal(rhs) {
656 t.Errorf("distributivity: %s*(%s+%s) = %s, but %s*%s + %s*%s = %s",
657 a, b, c, lhs, a, b, a, c, rhs)
658 }
659 }
660 }
661 }
662 }
663
664 func TestRatioNormalized(t *testing.T) {
665 // All constructed ratios are in lowest terms with positive denominator.
666 cases := [][2]int64{
667 {2, 4}, {3, 9}, {-6, 8}, {0, 5}, {7, 1}, {-3, -6},
668 }
669 for _, tc := range cases {
670 r := ratio.New(tc[0], tc[1])
671 if r.Denom <= 0 {
672 t.Errorf("New(%d,%d) has non-positive denom: %s", tc[0], tc[1], r)
673 }
674 // Check GCD is 1 (unless numerator is 0).
675 if r.Num != 0 {
676 g := gcd(abs64(r.Num), abs64(r.Denom))
677 if g != 1 {
678 t.Errorf("New(%d,%d) = %s not fully reduced (gcd=%d)", tc[0], tc[1], r, g)
679 }
680 }
681 }
682 }
683
684 // ---- Sign/Verify Determinism ----
685
686 func TestSignDeterministicChallenge(t *testing.T) {
687 // The challenge is Hash(message) which is deterministic.
688 msg := []byte("determinism test")
689 c1 := Hash(msg)
690 c2 := Hash(msg)
691 if c1 != c2 {
692 t.Error("Hash(message) not deterministic")
693 }
694 }
695
696 func TestVerifyRejectsTamperedChallenge(t *testing.T) {
697 // Manually construct a signature with wrong challenge.
698 l := buildMatureLattice()
699 params := DefaultParams(Security128)
700 kp := GenerateKeyPair(l, params, testFactory)
701
702 msg := []byte("test")
703 sig, err := Sign(&kp.Private, msg, params)
704 if err != nil {
705 t.Fatalf("Sign: %v", err)
706 }
707
708 fp := FingerprintFromSpore(kp.Public.Spore)
709
710 // Tamper with challenge.
711 sig.Challenge[0] ^= 0xFF
712 if Verify(fp, msg, sig) {
713 t.Error("tampered challenge should not verify")
714 }
715 }
716
717 // ---- Helper functions ----
718
719 func gcd(a, b int64) int64 {
720 for b != 0 {
721 a, b = b, a%b
722 }
723 return a
724 }
725
726 func abs64(n int64) int64 {
727 if n < 0 {
728 return -n
729 }
730 return n
731 }
732