peoplecoin

  1package rng
  2
  3import (
  4	"crypto/sha256"
  5	"math"
  6	"math/big"
  7	"testing"
  8)
  9
 10func TestHashMod(t *testing.T) {
 11	h := sha256.Sum256([]byte("x"))
 12	for _, n := range []uint64{1, 2, 3, 1000, 1 << 40, math.MaxUint64} {
 13		want := new(big.Int).Mod(new(big.Int).SetBytes(h[:]), new(big.Int).SetUint64(n)).Uint64()
 14		if got := HashMod(h, n); got != want {
 15			t.Fatalf("HashMod(n=%d) = %d, want %d", n, got, want)
 16		}
 17	}
 18	if HashMod(h, 1) != 0 {
 19		t.Fatal("mod 1")
 20	}
 21	defer func() {
 22		if recover() == nil {
 23			t.Fatal("mod 0 should panic")
 24		}
 25	}()
 26	HashMod(h, 0)
 27}
 28
 29func TestSeedRoundTrip(t *testing.T) {
 30	s := Seed(0x0102030405060708)
 31	want := [32]byte{}
 32	copy(want[24:], []byte{1, 2, 3, 4, 5, 6, 7, 8})
 33	if s != want {
 34		t.Fatalf("seed encoding %x", s)
 35	}
 36	if SeedNumber(s) != 0x0102030405060708 {
 37		t.Fatal("round trip")
 38	}
 39	if Seed(0) != ([32]byte{}) {
 40		t.Fatal("zero seed")
 41	}
 42}
 43
 44func TestTally(t *testing.T) {
 45	ta := NewTally()
 46	if _, ok := ta.Winner(); ok {
 47		t.Fatal("empty tally has no winner")
 48	}
 49	if ta.NextSeed() != ([32]byte{}) {
 50		t.Fatal("no reveals → seed 0")
 51	}
 52	ta.Add(7)
 53	ta.Add(3)
 54	ta.Add(7)
 55	ta.Add(3)
 56	ta.Add(9)
 57	if w, ok := ta.Winner(); !ok || w != 3 {
 58		t.Fatalf("tie must go to the lowest number, got %d", w)
 59	}
 60	ta.Add(7)
 61	if w, _ := ta.Winner(); w != 7 {
 62		t.Fatalf("most votes wins, got %d", w)
 63	}
 64	if ta.Total() != 6 || len(ta.Counts()) != 3 || ta.Counts()[0] != [2]uint64{3, 2} {
 65		t.Fatal("counts")
 66	}
 67	if SeedNumber(ta.NextSeed()) != 7 {
 68		t.Fatal("next seed")
 69	}
 70	c := ta.Clone()
 71	c.Add(3)
 72	c.Add(3)
 73	if w, _ := c.Winner(); w != 3 {
 74		t.Fatal("clone should tally independently")
 75	}
 76	if w, _ := ta.Winner(); w != 7 || ta.Total() != 6 {
 77		t.Fatal("clone mutated the original")
 78	}
 79}
 80
 81// Votes over N numbers are spread roughly uniformly per vote, so the
 82// maximum count over N voters is small (Poisson e^-1/k!): with 10 000
 83// entries the winner has ~5–7 votes.
 84func TestVoteSpread(t *testing.T) {
 85	const n = 10000
 86	seed := Seed(12345)
 87	ta := NewTally()
 88	for i := 0; i < n; i++ {
 89		addr := sha256.Sum256([]byte{byte(i), byte(i >> 8), 'a'})
 90		pre := sha256.Sum256([]byte{byte(i), byte(i >> 8), 'p'})
 91		v := Vote(addr, pre, seed, n)
 92		if v >= n {
 93			t.Fatalf("vote %d out of range", v)
 94		}
 95		ta.Add(v)
 96	}
 97	_, ok := ta.Winner()
 98	if !ok {
 99		t.Fatal("no winner")
100	}
101	var max uint64
102	for _, c := range ta.Counts() {
103		if c[1] > max {
104			max = c[1]
105		}
106	}
107	if max < 3 || max > 12 {
108		t.Fatalf("max votes on one number = %d, expected ~5–7 for N=10000", max)
109	}
110	if len(ta.Counts()) < 6000 || len(ta.Counts()) > 6700 {
111		t.Fatalf("%d distinct numbers hit, expected ~63%% of N", len(ta.Counts()))
112	}
113	// The seed changes every vote.
114	changed := 0
115	other := Seed(12346)
116	for i := 0; i < 100; i++ {
117		addr := sha256.Sum256([]byte{byte(i), 'a'})
118		pre := sha256.Sum256([]byte{byte(i), 'p'})
119		if Vote(addr, pre, seed, n) != Vote(addr, pre, other, n) {
120			changed++
121		}
122	}
123	if changed < 90 {
124		t.Fatalf("seed barely affects votes: %d/100 changed", changed)
125	}
126}
127
128func TestValidatorIndex(t *testing.T) {
129	seed := Seed(99)
130	const entries = 37
131	hits := make([]int, entries)
132	for slot := uint64(0); slot < 37*200; slot++ {
133		i := ValidatorIndex(seed, slot, entries)
134		if i >= entries {
135			t.Fatalf("index %d out of range", i)
136		}
137		hits[i]++
138	}
139	for i, h := range hits {
140		if h < 120 || h > 300 {
141			t.Fatalf("entry %d selected %d times of ~200", i, h)
142		}
143	}
144	if ValidatorIndex(seed, 5, entries) != ValidatorIndex(seed, 5, entries) {
145		t.Fatal("not deterministic")
146	}
147	if ValidatorIndex(seed, 5, 1) != 0 {
148		t.Fatal("single validator")
149	}
150}
151
152func TestCommits(t *testing.T) {
153	pre := sha256.Sum256([]byte("p"))
154	if Commit(pre) != sha256.Sum256(pre[:]) {
155		t.Fatal("commit")
156	}
157	v := sha256.Sum256([]byte("v"))
158	nonce := sha256.Sum256([]byte("n"))
159	want := sha256.Sum256(append(append([]byte{}, v[:]...), nonce[:]...))
160	if ElectionCommit(v, nonce) != want {
161		t.Fatal("election commit")
162	}
163	if ElectionCommit(v, nonce) == ElectionCommit(v, [32]byte{}) {
164		t.Fatal("nonce must matter")
165	}
166}