peoplecoin

  1package feistel
  2
  3import (
  4	"crypto/sha256"
  5	"encoding/binary"
  6	"testing"
  7)
  8
  9var sizes = []uint64{1, 2, 3, 4, 5, 7, 8, 9, 15, 16, 17, 31, 32, 33, 100, 255, 256, 257, 1000, 1023, 1024, 1025, 4097, 30000}
 10
 11func seedOf(s string) [32]byte { return sha256.Sum256([]byte(s)) }
 12
 13func TestWidths(t *testing.T) {
 14	cases := []struct{ n, k, l, r uint64 }{
 15		{1, 0, 0, 0}, {2, 1, 0, 1}, {3, 2, 1, 1}, {4, 2, 1, 1}, {5, 3, 1, 2},
 16		{8, 3, 1, 2}, {9, 4, 2, 2}, {1024, 10, 5, 5}, {1025, 11, 5, 6},
 17	}
 18	for _, c := range cases {
 19		k, l, r := widths(c.n)
 20		if uint64(k) != c.k || uint64(l) != c.l || uint64(r) != c.r {
 21			t.Errorf("widths(%d) = %d,%d,%d; want %d,%d,%d", c.n, k, l, r, c.k, c.l, c.r)
 22		}
 23	}
 24}
 25
 26func TestMaskWidth(t *testing.T) {
 27	seed := seedOf("m")
 28	for left := uint(0); left <= 32; left++ {
 29		for half := uint64(0); half < 50; half++ {
 30			m := mask(&seed, 3, half, left)
 31			if left < 64 && m>>left != 0 {
 32				t.Fatalf("mask wider than %d bits: %x", left, m)
 33			}
 34		}
 35	}
 36	// Spot check the definition for left = 12 (2 bytes, shifted by 4).
 37	h := sha256.New()
 38	h.Write(seed[:])
 39	h.Write([]byte{5})
 40	var b [8]byte
 41	binary.BigEndian.PutUint64(b[:], 77)
 42	h.Write(b[:])
 43	sum := h.Sum(nil)
 44	want := (uint64(sum[0])<<8 | uint64(sum[1])) >> 4
 45	if got := mask(&seed, 5, 77, 12); got != want {
 46		t.Fatalf("mask = %x, want %x", got, want)
 47	}
 48}
 49
 50func TestBijectionAndInverse(t *testing.T) {
 51	for _, n := range sizes {
 52		for _, s := range []string{"a", "b", "c"} {
 53			seed := seedOf(s)
 54			seen := make([]bool, n)
 55			for i := uint64(0); i < n; i++ {
 56				p := Permute(i, n, seed)
 57				if p >= n {
 58					t.Fatalf("n=%d: Permute(%d) = %d out of range", n, i, p)
 59				}
 60				if seen[p] {
 61					t.Fatalf("n=%d: collision at %d", n, p)
 62				}
 63				seen[p] = true
 64				if back := Invert(p, n, seed); back != i {
 65					t.Fatalf("n=%d: Invert(Permute(%d)) = %d", n, i, back)
 66				}
 67			}
 68		}
 69	}
 70}
 71
 72func TestPartnerSymmetry(t *testing.T) {
 73	for _, n := range sizes {
 74		seed := seedOf("pairs")
 75		unpaired := 0
 76		for i := uint64(0); i < n; i++ {
 77			p, ok := Partner(i, n, seed)
 78			if !ok {
 79				unpaired++
 80				continue
 81			}
 82			if p == i {
 83				t.Fatalf("n=%d: %d paired with itself", n, i)
 84			}
 85			q, ok := Partner(p, n, seed)
 86			if !ok || q != i {
 87				t.Fatalf("n=%d: partner not symmetric: %d→%d→%d", n, i, p, q)
 88			}
 89			// Adjacent in the shuffled order.
 90			if Permute(i, n, seed)^1 != Permute(p, n, seed) {
 91				t.Fatalf("n=%d: partners not adjacent", n)
 92			}
 93		}
 94		if want := int(n % 2); unpaired != want {
 95			t.Fatalf("n=%d: %d unpaired, want %d", n, unpaired, want)
 96		}
 97	}
 98}
 99
100func TestSeedMatters(t *testing.T) {
101	const n = 1000
102	a, b := seedOf("x"), seedOf("y")
103	same := 0
104	for i := uint64(0); i < n; i++ {
105		if Permute(i, n, a) == Permute(i, n, b) {
106			same++
107		}
108	}
109	// Two random permutations agree at ~1 position on average.
110	if same > 20 {
111		t.Fatalf("permutations under different seeds agree at %d/%d positions", same, n)
112	}
113	// And the seed spreads: no long run of fixed points.
114	fixed := 0
115	for i := uint64(0); i < n; i++ {
116		if Permute(i, n, a) == i {
117			fixed++
118		}
119	}
120	if fixed > 20 {
121		t.Fatalf("%d fixed points", fixed)
122	}
123}
124
125func TestOutOfRangePanics(t *testing.T) {
126	defer func() {
127		if recover() == nil {
128			t.Fatal("expected panic")
129		}
130	}()
131	Permute(5, 5, seedOf("z"))
132}
133
134// Fixed vectors so that other implementations can be checked against this
135// one. Regenerate deliberately if the algorithm is ever changed.
136func TestVectors(t *testing.T) {
137	seed := seedOf("peoplecoin")
138	const n = 1000
139	got := [8]uint64{}
140	for i := range got {
141		got[i] = Permute(uint64(i), n, seed)
142	}
143	t.Logf("Permute(0..7, 1000, SHA256(\"peoplecoin\")) = %v", got)
144	// Self-consistency of the vector with the inverse.
145	for i, p := range got {
146		if Invert(p, n, seed) != uint64(i) {
147			t.Fatal("vector inconsistent")
148		}
149	}
150}
151
152func BenchmarkPartner(b *testing.B) {
153	seed := seedOf("bench")
154	const n = 1_000_000
155	for i := 0; i < b.N; i++ {
156		Partner(uint64(i)%n, n, seed)
157	}
158}