peoplecoin

  1package state
  2
  3import (
  4	"crypto/sha256"
  5	"errors"
  6	"fmt"
  7	"testing"
  8	"time"
  9
 10	"peoplecoin/coin"
 11	"peoplecoin/params"
 12	"peoplecoin/period"
 13	"peoplecoin/rng"
 14	"peoplecoin/sig"
 15	"peoplecoin/wire"
 16)
 17
 18// ---------------------------------------------------------------------
 19// Harness
 20
 21type validatorInfo struct {
 22	key   *sig.Keypair
 23	nonce Hash
 24}
 25
 26type sim struct {
 27	t          *testing.T
 28	st         *State
 29	people     []*sig.Keypair
 30	validators map[uint64]map[Address]validatorInfo // period → voter → who they voted for
 31	pending    map[Address]validatorInfo            // votes in ops not yet in a block
 32	tokens     map[Address][3]Hash                  // address → election, reg, invite UTXO IDs
 33	preimages  map[uint32]map[Address]Hash          // period → address → RNG preimage committed
 34}
 35
 36func keyFor(name string) *sig.Keypair { return sig.FromSeed(sha256.Sum256([]byte(name))) }
 37
 38func genesisTimeOf(s *sim) uint64 { return s.st.Time - s.st.Slot*params.SlotSeconds }
 39
 40func addrOf(k *sig.Keypair) Address { return Address(k.Public) }
 41
 42func h(s string) Hash { return sha256.Sum256([]byte(s)) }
 43
 44func newSim(t *testing.T, n int) *sim {
 45	s := &sim{
 46		t:          t,
 47		validators: map[uint64]map[Address]validatorInfo{0: {}},
 48		pending:    map[Address]validatorInfo{},
 49		tokens:     map[Address][3]Hash{},
 50		preimages:  map[uint32]map[Address]Hash{},
 51	}
 52	registry := make([]Address, n)
 53	for i := 0; i < n; i++ {
 54		s.people = append(s.people, keyFor(fmt.Sprintf("person-%d", i)))
 55		registry[i] = addrOf(s.people[i])
 56	}
 57	// Person 0 holds the genesis vote (for validator key "val-A") and an
 58	// election token for period 1.
 59	valA := keyFor("val-A")
 60	nonce := h("nonce-genesis")
 61	s.validators[0][registry[0]] = validatorInfo{valA, nonce}
 62	tokenID := h("genesis-election-token")
 63	genesisTime := uint64(time.Date(2027, 1, 2, 7, 0, 0, 0, time.UTC).Unix()) // a Saturday 07:00 UTC
 64	st, err := Genesis(genesisTime, registry,
 65		[]GenesisVote{{Voter: registry[0], Commit: rng.ElectionCommit(Address(valA.Public), nonce)}},
 66		[]GenesisToken{{ID: tokenID, Entry: wire.TokenEntry{TokenID: params.TokenElection, Owner: registry[0]}}})
 67	if err != nil {
 68		t.Fatal(err)
 69	}
 70	s.st = st
 71	s.tokens[registry[0]] = [3]Hash{tokenID}
 72	return s
 73}
 74
 75// tryBlock assembles a block for slot with ops on top of the current state
 76// and checks that Apply accepts exactly what Assemble produced.
 77func (s *sim) tryBlock(slot uint64, ops ...Op) (*Block, *State, error) {
 78	voter, _, ok := s.st.AtSlot(slot).Validator(slot)
 79	if !ok {
 80		return nil, nil, ErrNoValidator
 81	}
 82	v, ok := s.validators[period.Of(slot)][voter]
 83	if !ok {
 84		s.t.Fatalf("slot %d: no validator key for voter %x", slot, voter[:4])
 85	}
 86	b, post, err := s.st.Assemble(slot, ops, v.key, v.nonce)
 87	if err != nil {
 88		return nil, nil, err
 89	}
 90	applied, err := s.st.Apply(b)
 91	if err != nil {
 92		s.t.Fatalf("slot %d: Apply rejected an assembled block: %v", slot, err)
 93	}
 94	if applied.Roots() != post.Roots() || applied.PrevHash != post.PrevHash || applied.Number != post.Number {
 95		s.t.Fatalf("slot %d: Apply and Assemble disagree", slot)
 96	}
 97	// Wire round trip.
 98	dec, err := DecodeBlock(b.Bytes())
 99	if err != nil {
100		s.t.Fatalf("slot %d: block decode: %v", slot, err)
101	}
102	if applied2, err := s.st.Apply(dec); err != nil || applied2.Roots() != post.Roots() {
103		s.t.Fatalf("slot %d: decoded block does not apply identically: %v", slot, err)
104	}
105	return b, post, nil
106}
107
108func (s *sim) block(slot uint64, ops ...Op) *Block {
109	b, post, err := s.tryBlock(slot, ops...)
110	if err != nil {
111		s.t.Fatalf("slot %d: %v", slot, err)
112	}
113	s.st = post
114	// Votes in this block decide next period's validators.
115	next := period.Of(slot) + 1
116	if s.validators[next] == nil {
117		s.validators[next] = map[Address]validatorInfo{}
118	}
119	for _, op := range ops {
120		if v, ok := op.(*Vote); ok {
121			for voter, info := range s.pending {
122				if rng.ElectionCommit(Address(info.key.Public), info.nonce) == v.Commit {
123					s.validators[next][voter] = info
124				}
125			}
126		}
127	}
128	s.pending = map[Address]validatorInfo{}
129	return b
130}
131
132func (s *sim) mustFail(want error, slot uint64, ops ...Op) {
133	s.t.Helper()
134	_, _, err := s.tryBlock(slot, ops...)
135	if !errors.Is(err, want) {
136		s.t.Fatalf("slot %d: got %v, want %v", slot, err, want)
137	}
138}
139
140func (s *sim) per(slot uint64) uint32 { return period.Number(slot) }
141
142func (s *sim) verify(k *sig.Keypair, slot uint64) Op {
143	op := &Verify{RegAddr: addrOf(k)}
144	m, _ := op.Message(s.per(slot))
145	op.Sig = k.Sign(m[:])
146	return op
147}
148
149func (s *sim) verified(k *sig.Keypair, slot uint64) Op {
150	op := &Verified{RegAddr: addrOf(k)}
151	m, _ := op.Message(s.per(slot))
152	op.Sig = k.Sign(m[:])
153	txh, _ := TxHash(op, s.per(slot))
154	s.tokens[addrOf(k)] = [3]Hash{wire.UTXOID(txh, 0), wire.UTXOID(txh, 1), wire.UTXOID(txh, 2)}
155	return op
156}
157
158func (s *sim) vote(k *sig.Keypair, validator *sig.Keypair, nonce Hash) Op {
159	op := &Vote{TokenUTXO: s.tokens[addrOf(k)][0], Commit: rng.ElectionCommit(Address(validator.Public), nonce)}
160	m, _ := op.Message(0)
161	op.Sig = k.Sign(m[:])
162	s.pending[addrOf(k)] = validatorInfo{validator, nonce}
163	return op
164}
165
166func (s *sim) register(k *sig.Keypair, ids ...Hash) Op {
167	op := &Register{TokenUTXOs: ids}
168	m, _ := op.Message(0)
169	op.Sig = k.Sign(m[:])
170	return op
171}
172
173// commitOp builds a Commit without recording the preimage (for ops that
174// are expected to fail).
175func (s *sim) commitOp(k *sig.Keypair, slot uint64, preimage Hash) Op {
176	op := &Commit{RngAddr: addrOf(k), Commit: rng.Commit(preimage)}
177	m, _ := op.Message(s.per(slot))
178	op.Sig = k.Sign(m[:])
179	return op
180}
181
182func (s *sim) commit(k *sig.Keypair, slot uint64, preimage Hash) Op {
183	op := s.commitOp(k, slot, preimage)
184	if s.preimages[s.per(slot)] == nil {
185		s.preimages[s.per(slot)] = map[Address]Hash{}
186	}
187	s.preimages[s.per(slot)][addrOf(k)] = preimage
188	return op
189}
190
191func (s *sim) reveal(k *sig.Keypair, slot uint64, preimage Hash) Op {
192	op := &Reveal{RngAddr: addrOf(k), Preimage: preimage}
193	m, _ := op.Message(s.per(slot))
194	op.Sig = k.Sign(m[:])
195	return op
196}
197
198// mix signs a one-to-one mix of tokens owned by signers into outputs.
199func (s *sim) mix(tokenID uint8, inputs []Hash, signers []*sig.Keypair, outputs []wire.MixOutput) Op {
200	op := &Mix{TokenID: tokenID, Inputs: inputs, Outputs: outputs}
201	m, _ := op.Message(0)
202	for _, k := range signers {
203		op.Sigs = append(op.Sigs, k.Sign(m[:]))
204	}
205	return op
206}
207
208func (s *sim) transfer(inputs []Hash, signers []*sig.Keypair, outputs []wire.TransferOutput) *Transfer {
209	op := &Transfer{Inputs: inputs, Outputs: outputs}
210	m, _ := op.Message(0)
211	for _, k := range signers {
212		op.Sigs = append(op.Sigs, k.Sign(m[:]))
213	}
214	return op
215}
216
217func single(k *sig.Keypair, amount uint64) wire.TransferOutput {
218	return wire.TransferOutput{Amount: amount, Owners: []Address{addrOf(k)}, Threshold: 1}
219}
220
221// ---------------------------------------------------------------------
222
223func TestThreePeriods(t *testing.T) {
224	const n = 9 // odd: one person has no partner each period
225	s := newSim(t, n)
226	P := s.people
227	sp := params.SlotsPerPeriod
228
229	// ---- Period 0 -------------------------------------------------------
230
231	// The first block, at slot 1 on top of the genesis state: person 0
232	// spends the genesis election token on a vote for period 1.
233	valA, valB := keyFor("val-A"), keyFor("val-B")
234	b1 := s.block(1, s.vote(P[0], valA, h("nonce-genesis")))
235	if b1.Header.Number != 1 || b1.Header.Prev != (Hash{}) || s.st.Number != 1 || s.st.Slot != 1 {
236		t.Fatal("first block")
237	}
238	if s.st.PrevHash != b1.Header.Hash() || s.st.Election[1].Count() != 1 || s.st.Token.Count() != 0 {
239		t.Fatal("tip after first block")
240	}
241	if b1.Header.Time != genesisTimeOf(s)+60 || s.st.Time != b1.Header.Time {
242		t.Fatal("time of the first block")
243	}
244	// A Verify signed for another period fails its signature.
245	s.mustFail(ErrSignature, 99, s.verify(P[3], 99+sp))
246
247	// Pairs under seed 0. Everyone attests, including the odd one out.
248	var paired []*sig.Keypair
249	var odd *sig.Keypair
250	var ops []Op
251	for _, k := range P {
252		if _, ok := s.st.Partner(addrOf(k)); ok {
253			paired = append(paired, k)
254		} else {
255			odd = k
256		}
257		ops = append(ops, s.verify(k, 100))
258	}
259	if len(paired) != n-1 || odd == nil {
260		t.Fatalf("%d paired of %d", len(paired), n)
261	}
262	// Partner symmetry through the state.
263	for _, k := range paired {
264		p, _ := s.st.Partner(addrOf(k))
265		q, _ := s.st.Partner(p)
266		if q != addrOf(k) {
267			t.Fatal("partner not symmetric")
268		}
269	}
270	s.block(100, ops...)
271	for _, k := range P {
272		e, _ := s.st.RegEntry(0, addrOf(k))
273		if !e.Verify || e.Verified {
274			t.Fatal("verify flag")
275		}
276	}
277
278	// A flag cannot be set twice.
279	s.mustFail(ErrAlreadySet, 101, s.verify(P[0], 101))
280
281	// Verified: pays tokens to everyone with a partner; the odd one out fails.
282	ops = ops[:0]
283	for _, k := range paired {
284		ops = append(ops, s.verified(k, 200))
285	}
286	s.block(200, ops...)
287	s.mustFail(ErrNoPartner, 201, s.verified(odd, 201))
288	s.mustFail(ErrAlreadySet, 201, s.verified(P[0], 201))
289	if s.st.Rng[1].Count() != uint64(n-1) || s.st.Token.Count() != uint64(3*(n-1)) {
290		t.Fatalf("after Verified: rng1=%d tokens=%d", s.st.Rng[1].Count(), s.st.Token.Count())
291	}
292	for _, k := range paired {
293		for i, id := range []uint8{params.TokenElection, params.TokenRegistration, params.TokenInvite} {
294			e, ok := s.st.TokenEntry(s.tokens[addrOf(k)][i])
295			if !ok || e.TokenID != id || e.Owner != addrOf(k) || e.MixCount != 0 {
296				t.Fatalf("minted token %d wrong", i)
297			}
298		}
299	}
300
301	// Votes for period 1: even voters pick val-A, odd pick val-B. Person 0
302	// already voted in block 1, so a second vote from the minted token is
303	// rejected: the address is occupied.
304	ops = ops[:0]
305	nVotes0 := 1
306	for i, k := range paired {
307		if k == P[0] {
308			s.mustFail(ErrOccupied, 300, s.vote(k, valB, h("second")))
309			continue
310		}
311		v := valA
312		if i%2 == 1 {
313			v = valB
314		}
315		ops = append(ops, s.vote(k, v, h(fmt.Sprintf("nonce-%d", i))))
316		nVotes0++
317	}
318	// A vote with a registration token.
319	badVote := &Vote{TokenUTXO: s.tokens[addrOf(paired[0])][1]}
320	m, _ := badVote.Message(0)
321	badVote.Sig = paired[0].Sign(m[:])
322	s.mustFail(ErrTokenType, 300, badVote)
323	s.block(300, ops...)
324	if s.st.Election[1].Count() != uint64(nVotes0) {
325		t.Fatalf("votes: %d, want %d", s.st.Election[1].Count(), nVotes0)
326	}
327	// Voting twice with the (spent) token: input gone.
328	s.mustFail(ErrMissingInput, 301, s.vote(paired[1], valA, h("x")))
329
330	// Registration. One person (anon) mixes the registration token to a
331	// fresh key first — the anonymization the spec describes; the others
332	// register directly. Three people give their invite tokens to the odd
333	// one out.
334	anon := paired[0]
335	fresh1 := keyFor("fresh-1")
336	mixOp := s.mix(params.TokenRegistration, []Hash{s.tokens[addrOf(anon)][1]}, []*sig.Keypair{anon},
337		[]wire.MixOutput{{MixCount: 1, Owner: addrOf(fresh1)}})
338	mixTx, _ := TxHash(mixOp, 0)
339	fresh1Reg := wire.UTXOID(mixTx, 0)
340
341	// Wrong mix count sum is rejected; so is a count over the cap.
342	badMix := s.mix(params.TokenRegistration, []Hash{s.tokens[addrOf(paired[1])][1]}, []*sig.Keypair{paired[1]},
343		[]wire.MixOutput{{MixCount: 2, Owner: addrOf(paired[1])}})
344	s.mustFail(ErrMixCount, 400, badMix)
345	overCap := s.mix(params.TokenRegistration, []Hash{s.tokens[addrOf(paired[1])][1]}, []*sig.Keypair{paired[1]},
346		[]wire.MixOutput{{MixCount: params.MaxMixes + 1, Owner: addrOf(paired[1])}})
347	s.mustFail(ErrMixCap, 400, overCap)
348	wrongSigner := s.mix(params.TokenRegistration, []Hash{s.tokens[addrOf(paired[1])][1]}, []*sig.Keypair{paired[2]},
349		[]wire.MixOutput{{MixCount: 1, Owner: addrOf(paired[1])}})
350	s.mustFail(ErrSignature, 400, wrongSigner)
351
352	givers := paired[len(paired)-3:]
353	var inviteIn []Hash
354	for _, g := range givers {
355		inviteIn = append(inviteIn, s.tokens[addrOf(g)][2])
356	}
357	giveOp := s.mix(params.TokenInvite, inviteIn, givers, []wire.MixOutput{
358		{MixCount: 1, Owner: addrOf(odd)}, {MixCount: 1, Owner: addrOf(odd)}, {MixCount: 1, Owner: addrOf(odd)}})
359	giveTx, _ := TxHash(giveOp, 0)
360	s.block(400, mixOp, giveOp)
361	if e, ok := s.st.TokenEntry(fresh1Reg); !ok || e.Owner != addrOf(fresh1) || e.MixCount != 1 || e.TokenID != params.TokenRegistration {
362		t.Fatal("mixed registration token")
363	}
364
365	ops = ops[:0]
366	ops = append(ops, s.register(fresh1, fresh1Reg))
367	for _, k := range paired {
368		if k == anon {
369			continue
370		}
371		ops = append(ops, s.register(k, s.tokens[addrOf(k)][1]))
372	}
373	invites := []Hash{wire.UTXOID(giveTx, 0), wire.UTXOID(giveTx, 1), wire.UTXOID(giveTx, 2)}
374	ops = append(ops, s.register(odd, invites...))
375	// Two invites are not enough; an invite plus a registration token is
376	// the wrong type.
377	s.mustFail(ErrTokenCount, 500, s.register(odd, invites[:2]...))
378	s.mustFail(ErrTokenType, 500, s.register(odd, invites[0]))
379	s.block(500, ops...)
380	if s.st.Reg[1].Count() != uint64(n) {
381		t.Fatalf("registry for period 1: %d", s.st.Reg[1].Count())
382	}
383	if !s.st.Reg[1].Has(addrOf(fresh1)) || s.st.Reg[1].Has(addrOf(anon)) {
384		t.Fatal("anon should be registered under the fresh key")
385	}
386	// Registering again: entry occupied — but the token is gone first.
387	s.mustFail(ErrMissingInput, 501, s.register(odd, invites...))
388
389	// RNG commits for period 1. A commit signed for the wrong period fails.
390	replay := &Commit{RngAddr: addrOf(paired[0]), Commit: h("c")}
391	m, _ = replay.Message(1)
392	replay.Sig = paired[0].Sign(m[:])
393	s.mustFail(ErrSignature, 599, replay)
394	ops = ops[:0]
395	for i, k := range paired {
396		ops = append(ops, s.commit(k, 600, h(fmt.Sprintf("preimage-0-%d", i))))
397	}
398	s.mustFail(ErrCommitZero, 600, func() Op {
399		op := &Commit{RngAddr: addrOf(paired[0])}
400		m, _ := op.Message(0)
401		op.Sig = paired[0].Sign(m[:])
402		return op
403	}())
404	s.block(600, ops...)
405	s.mustFail(ErrCommitSet, 601, s.commitOp(paired[0], 601, h("again")))
406	s.mustFail(ErrNotRegistered, 601, s.commitOp(odd, 601, h("odd")))
407
408	// Phase 1: Verify is over, Verified still possible (but everyone is done).
409	s.mustFail(ErrPhase, params.SlotsPerPhase+5, s.verify(P[0], params.SlotsPerPhase+5))
410	// Phase 2: nothing to reveal yet — rng_trie[0] is empty at genesis.
411	s.mustFail(ErrNotRegistered, 2*params.SlotsPerPhase+5, s.reveal(paired[0], 2*params.SlotsPerPhase+5, s.preimages[0][addrOf(paired[0])]))
412	s.mustFail(ErrPhase, 2*params.SlotsPerPhase+5, s.commitOp(paired[0], 2*params.SlotsPerPhase+5, h("late")))
413	s.block(2*params.SlotsPerPhase + 5)
414
415	// ---- Period 1 -------------------------------------------------------
416
417	// Seed 0 (nobody revealed). Validators are now the eight period-0 voters.
418	p1 := sp + 10
419	pre := s.st.AtSlot(p1)
420	if pre.Period != 1 || pre.Seed != (Hash{}) || pre.Election[0].Count() != uint64(nVotes0) || pre.Reg[0].Count() != uint64(n) || pre.Rng[0].Count() != uint64(n-1) {
421		t.Fatalf("period 1 pre-state: period=%d elections=%d reg=%d rng=%d", pre.Period, pre.Election[0].Count(), pre.Reg[0].Count(), pre.Rng[0].Count())
422	}
423	if pre.Token.Count() != 0 || pre.Reg[1].Count() != 0 || pre.Rng[1].Count() != 0 || pre.Election[1].Count() != 0 {
424		t.Fatal("rotation should clear [1] and the tokens")
425	}
426	// Different slots are owned by different voters.
427	owners := map[Address]bool{}
428	for slot := p1; slot < p1+100; slot++ {
429		v, _, _ := pre.Validator(slot)
430		owners[v] = true
431	}
432	if len(owners) < 4 {
433		t.Fatalf("only %d voters own the first 100 slots", len(owners))
434	}
435	s.block(p1)
436	if s.st.Period != 1 {
437		t.Fatal("tip period")
438	}
439
440	// New registry: paired minus anon plus fresh1 plus odd. New pairs.
441	people1 := []*sig.Keypair{fresh1, odd}
442	for _, k := range paired {
443		if k != anon {
444			people1 = append(people1, k)
445		}
446	}
447	ops = ops[:0]
448	var paired1 []*sig.Keypair
449	for _, k := range people1 {
450		ops = append(ops, s.verify(k, p1+50))
451		if _, ok := s.st.AtSlot(p1).Partner(addrOf(k)); ok {
452			paired1 = append(paired1, k)
453		}
454	}
455	s.block(p1+50, ops...)
456	ops = ops[:0]
457	for i, k := range paired1 {
458		ops = append(ops, s.verified(k, p1+60))
459		ops = append(ops, s.commitOp(k, p1+60, h(fmt.Sprintf("preimage-1-%d", i))))
460	}
461	// Commit before Verified in the same block fails: it validates against
462	// pre-block state, where the RNG entry does not exist yet.
463	s.mustFail(ErrNotRegistered, p1+60, ops...)
464	ops = ops[:0]
465	for _, k := range paired1 {
466		ops = append(ops, s.verified(k, p1+60))
467	}
468	s.block(p1+60, ops...)
469	ops = ops[:0]
470	for i, k := range paired1 {
471		ops = append(ops, s.commit(k, p1+61, h(fmt.Sprintf("preimage-1-%d", i))))
472	}
473	s.block(p1+61, ops...)
474	// Everyone votes again, and registers, so the chain continues.
475	ops = ops[:0]
476	for i, k := range paired1 {
477		v := valA
478		if i%2 == 0 {
479			v = valB
480		}
481		ops = append(ops, s.vote(k, v, h(fmt.Sprintf("nonce-1-%d", i))))
482		ops = append(ops, s.register(k, s.tokens[addrOf(k)][1]))
483	}
484	s.block(p1+70, ops...)
485
486	// Phase 2 of period 1: the eight period-0 commits are revealed; the
487	// UBI is paid; the tally fills.
488	r1 := sp + 2*params.SlotsPerPhase + 10
489	ops = ops[:0]
490	for _, k := range paired {
491		ops = append(ops, s.reveal(k, r1, s.preimages[0][addrOf(k)]))
492	}
493	s.mustFail(ErrPreimage, r1, s.reveal(paired[0], r1, h("wrong")))
494	// Revealing a period-1 commit (still in rng_trie[1]) is not possible.
495	s.mustFail(ErrNotRegistered, r1, s.reveal(odd, r1, h("preimage-1-0")))
496	s.block(r1, ops...)
497	s.mustFail(ErrNoCommit, r1+1, s.reveal(paired[0], r1+1, s.preimages[0][addrOf(paired[0])]))
498	if s.st.Coin.Count() != uint64(n-1) || s.st.Tally.Total() != uint64(n-1) {
499		t.Fatalf("after reveals: coins=%d votes=%d", s.st.Coin.Count(), s.st.Tally.Total())
500	}
501	ubi := map[Address]Hash{}
502	for _, k := range paired {
503		txh, _ := TxHash(s.reveal(k, r1, s.preimages[0][addrOf(k)]), s.per(r1))
504		id := wire.UTXOID(txh, 0)
505		e, ok := s.st.CoinEntry(id)
506		if !ok || e.Amount != params.UBIPerPeriod || e.Slot != uint32(r1) || len(e.Owners) != 1 || e.Owners[0] != addrOf(k) {
507			t.Fatal("UBI entry")
508		}
509		ubi[addrOf(k)] = id
510	}
511	// Reveal is a phase-2 operation.
512	s.mustFail(ErrPhase, sp+3*params.SlotsPerPhase+1, s.reveal(paired[1], sp+3*params.SlotsPerPhase+1, h("x")))
513
514	// ---- Period 2 -------------------------------------------------------
515
516	winner, _ := s.st.Tally.Winner()
517	p2 := 2*sp + 5
518	pre = s.st.AtSlot(p2)
519	if pre.Seed != rng.Seed(winner) {
520		t.Fatal("seed should be the tally winner")
521	}
522	t.Logf("period 2 seed number: %d (from %d reveals)", winner, s.st.Tally.Total())
523
524	// Transfers. paired[0] pays paired[1] 1 000 000, keeping the rest; the
525	// remainder after outputs is the fee, split between validator and voter.
526	a, b := paired[0], paired[1]
527	spend, _ := s.st.CoinEntry(ubi[addrOf(a)])
528	tt := coin.Elapsed(spend.Slot, p2)
529	spendable := coin.Spendable(spend.Amount, tt)
530	tx := s.transfer([]Hash{ubi[addrOf(a)]}, []*sig.Keypair{a}, []wire.TransferOutput{single(b, 1_000_000), single(a, spendable-1_000_000-500)})
531	blk := s.block(p2, tx)
532	txh, _ := TxHash(tx, 0)
533	if _, ok := s.st.CoinEntry(ubi[addrOf(a)]); ok {
534		t.Fatal("input not spent")
535	}
536	if e, ok := s.st.CoinEntry(wire.UTXOID(txh, 0)); !ok || e.Amount != 1_000_000 || e.Owners[0] != addrOf(b) || e.Slot != uint32(p2) {
537		t.Fatal("output 0")
538	}
539	fee := coin.Effective(spend.Amount, tt) - (spendable - 500)
540	valFee, ok := s.st.CoinEntry(wire.FeeUTXOID(blk.Header.Number, 0))
541	voterFee, ok2 := s.st.CoinEntry(wire.FeeUTXOID(blk.Header.Number, 1))
542	if !ok || !ok2 || valFee.Amount+voterFee.Amount != fee || valFee.Amount < voterFee.Amount || valFee.Amount-voterFee.Amount > 1 {
543		t.Fatalf("fee split: %v %v of %d", valFee, voterFee, fee)
544	}
545	if valFee.Owners[0] != blk.Header.Validator {
546		t.Fatal("validator fee owner")
547	}
548	voter, _, _ := s.st.Validator(p2)
549	if voterFee.Owners[0] != voter {
550		t.Fatal("voter fee owner")
551	}
552
553	// Overspend, zero output, double spend within a block, bad signer.
554	s.mustFail(ErrInsufficient, p2+1, s.transfer([]Hash{ubi[addrOf(b)]}, []*sig.Keypair{b}, []wire.TransferOutput{single(a, params.UBIPerPeriod)}))
555	s.mustFail(ErrAmount, p2+1, s.transfer([]Hash{ubi[addrOf(b)]}, []*sig.Keypair{b}, []wire.TransferOutput{single(a, 0)}))
556	s.mustFail(ErrSignature, p2+1, s.transfer([]Hash{ubi[addrOf(b)]}, []*sig.Keypair{a}, []wire.TransferOutput{single(a, 10)}))
557	s.mustFail(ErrSignature, p2+1, s.transfer([]Hash{ubi[addrOf(b)]}, []*sig.Keypair{b, b}, []wire.TransferOutput{single(a, 10)}))
558	s.mustFail(ErrConflict, p2+1,
559		s.transfer([]Hash{ubi[addrOf(b)]}, []*sig.Keypair{b}, []wire.TransferOutput{single(a, 10)}),
560		s.transfer([]Hash{ubi[addrOf(b)]}, []*sig.Keypair{b}, []wire.TransferOutput{single(a, 11)}))
561	s.mustFail(ErrDuplicate, p2+1, s.transfer([]Hash{ubi[addrOf(b)], ubi[addrOf(b)]}, []*sig.Keypair{b, b}, []wire.TransferOutput{single(a, 10)}))
562	// The same transaction twice in one block.
563	dup := s.transfer([]Hash{ubi[addrOf(b)]}, []*sig.Keypair{b}, []wire.TransferOutput{single(a, 10)})
564	s.mustFail(ErrDuplicateTx, p2+1, dup, dup)
565
566	// Multisig: 2-of-3 output, spent with signatures in owner order.
567	c := paired[2]
568	msig := wire.TransferOutput{Amount: 500_000, Owners: []Address{addrOf(a), addrOf(b), addrOf(c)}, Threshold: 2}
569	tx2 := s.transfer([]Hash{ubi[addrOf(b)]}, []*sig.Keypair{b}, []wire.TransferOutput{msig})
570	s.block(p2+1, tx2)
571	tx2h, _ := TxHash(tx2, 0)
572	msigID := wire.UTXOID(tx2h, 0)
573	// One signature is too few; two out of order fail (b then a); a and c work.
574	s.mustFail(ErrSignature, p2+2, s.transfer([]Hash{msigID}, []*sig.Keypair{a}, []wire.TransferOutput{single(c, 10)}))
575	s.mustFail(ErrSignature, p2+2, s.transfer([]Hash{msigID}, []*sig.Keypair{b, a}, []wire.TransferOutput{single(c, 10)}))
576	s.mustFail(ErrSignature, p2+2, s.transfer([]Hash{msigID}, []*sig.Keypair{a, b, c}, []wire.TransferOutput{single(c, 10)}))
577	dustTx := s.transfer([]Hash{msigID}, []*sig.Keypair{a, c}, []wire.TransferOutput{single(c, 400_000), single(c, 10)})
578	s.block(p2+2, dustTx)
579	dustH, _ := TxHash(dustTx, 0)
580	dustID := wire.UTXOID(dustH, 1)
581
582	// Prune. Ten base units are gone long before rent reaches ten: each
583	// multiplication in the decay chain floors, so a tiny amount loses a
584	// unit per set bit of t, and at t = 1023 (ten bits) it is worth zero,
585	// which rent 0 meets. Find the first prunable slot from the coin rules
586	// rather than assuming one.
587	var tMin uint64
588	for tMin = 1; !coin.Prunable(10, tMin); tMin++ {
589	}
590	t.Logf("10 base units prunable from t = %d", tMin)
591	s.mustFail(ErrNotPrunable, p2+2+1, &Prune{UTXO: dustID})
592	s.mustFail(ErrNotPrunable, p2+2+tMin-1, &Prune{UTXO: dustID})
593	s.block(p2+2+tMin, &Prune{UTXO: dustID})
594	if s.st.Coin.Has(dustID) {
595		t.Fatal("dust not pruned")
596	}
597	s.mustFail(ErrMissingInput, p2+2+tMin+1, &Prune{UTXO: dustID})
598	// The pruned value went to the block's fees.
599	if _, ok := s.st.CoinEntry(wire.FeeUTXOID(s.st.Number, 0)); ok {
600		t.Fatal("pruning a zero-value entry should pay no fee")
601	}
602
603	// Period 2's validators and registry are period 1's votes and
604	// registrations; nobody voted in period 2, so period 3 has no
605	// validators and the chain ends there.
606	if s.st.Election[0].Count() != uint64(len(paired1)) || s.st.Reg[0].Count() != uint64(len(paired1)) || s.st.Rng[0].Count() != uint64(len(paired1)) {
607		t.Fatalf("period 2: elections=%d reg=%d rng=%d, want %d", s.st.Election[0].Count(), s.st.Reg[0].Count(), s.st.Rng[0].Count(), len(paired1))
608	}
609	p3 := 3*sp + 1
610	if pre := s.st.AtSlot(p3); pre.Period != 3 || pre.Election[0].Count() != 0 {
611		t.Fatal("period 3 should have no validators")
612	}
613	if _, _, err := s.tryBlock(p3); !errors.Is(err, ErrNoValidator) {
614		t.Fatalf("period 3: %v", err)
615	}
616	t.Logf("tip: block %d, slot %d, %d coins, %d tokens", s.st.Number, s.st.Slot, s.st.Coin.Count(), s.st.Token.Count())
617}
618
619// ---------------------------------------------------------------------
620// Header rules
621
622func TestHeaderRules(t *testing.T) {
623	s := newSim(t, 4)
624	good := s.block(5)
625	base := s.st
626
627	// Build a valid next block, then break it in every way.
628	voter, _, _ := base.Validator(6)
629	v := s.validators[0][voter]
630	fresh := func() *Block {
631		b, _, err := base.Assemble(6, []Op{s.verify(s.people[0], 6)}, v.key, v.nonce)
632		if err != nil {
633			t.Fatal(err)
634		}
635		return b
636	}
637	expect := func(want error, mutate func(b *Block)) {
638		t.Helper()
639		b := fresh()
640		mutate(b)
641		if _, err := base.Apply(b); !errors.Is(err, want) {
642			t.Fatalf("got %v, want %v", err, want)
643		}
644	}
645	resign := func(b *Block) {
646		sh := b.Header.SigningHash()
647		b.Header.Sig = v.key.Sign(sh[:])
648	}
649	if _, err := base.Apply(fresh()); err != nil {
650		t.Fatal(err)
651	}
652	// time is exactly the slot's start, one minute after block 5's.
653	if fresh().Header.Time != good.Header.Time+60 {
654		t.Fatal("time")
655	}
656	expect(ErrNumber, func(b *Block) { b.Header.Number = 3; resign(b) })
657	expect(ErrSlot, func(b *Block) { b.Header.Slot = 5; resign(b) })
658	expect(ErrTime, func(b *Block) { b.Header.Time += 60; resign(b) })
659	expect(ErrTime, func(b *Block) { b.Header.Time += 1; resign(b) })
660	expect(ErrTime, func(b *Block) { b.Header.Time -= 1; resign(b) })
661	expect(ErrPrev, func(b *Block) { b.Header.Prev = h("x"); resign(b) })
662	expect(ErrValidator, func(b *Block) { b.Header.Nonce = h("x"); resign(b) })
663	expect(ErrValidator, func(b *Block) {
664		other := keyFor("other")
665		b.Header.Validator = addrOf(other)
666		sh := b.Header.SigningHash()
667		b.Header.Sig = other.Sign(sh[:])
668	})
669	expect(ErrRoots, func(b *Block) { b.Header.Coin = h("x"); resign(b) })
670	expect(ErrRoots, func(b *Block) { b.Header.TxTrie = h("x"); resign(b) })
671	expect(ErrHeaderSig, func(b *Block) { b.Header.Sig[3] ^= 1 })
672	expect(ErrHeaderSig, func(b *Block) {
673		other := keyFor("other")
674		sh := b.Header.SigningHash()
675		b.Header.Sig = other.Sign(sh[:])
676	})
677	// Ops missing from the block but in the roots, and vice versa.
678	expect(ErrRoots, func(b *Block) { b.Ops = nil })
679	expect(ErrRoots, func(b *Block) { b.Ops = append(b.Ops, s.verify(s.people[1], 6)) })
680	expect(ErrMissingInput, func(b *Block) { b.Ops = append(b.Ops, &Prune{UTXO: h("nothing")}) })
681
682	// Applying the previous block again on the new tip.
683	if _, err := base.Apply(good); !errors.Is(err, ErrNumber) {
684		t.Fatalf("replayed block: %v", err)
685	}
686
687	// Header wire round trip and hash stability.
688	b := fresh()
689	dec, err := DecodeHeader(b.Header.Bytes())
690	if err != nil || *dec != b.Header || dec.Hash() != b.Header.Hash() {
691		t.Fatal("header round trip")
692	}
693	if _, err := DecodeHeader(b.Header.Bytes()[:HeaderSize-1]); err == nil {
694		t.Fatal("short header accepted")
695	}
696	if len(b.Header.Bytes()) != HeaderSize {
697		t.Fatal("header size")
698	}
699}
700
701func TestNoValidatorsEndsChain(t *testing.T) {
702	// Nobody votes in period 0, so period 1 has no validators.
703	s := newSim(t, 4)
704	s.block(7)
705	if _, _, err := s.tryBlock(params.SlotsPerPeriod + 1); !errors.Is(err, ErrNoValidator) {
706		t.Fatalf("got %v", err)
707	}
708	if _, _, ok := s.st.AtSlot(params.SlotsPerPeriod + 1).Validator(params.SlotsPerPeriod + 1); ok {
709		t.Fatal("no validator expected")
710	}
711}
712
713func TestGenesisRules(t *testing.T) {
714	if _, err := Genesis(1000, nil, nil, nil); !errors.Is(err, ErrGenesis) {
715		t.Fatal("genesis without votes should fail")
716	}
717	a := addrOf(keyFor("a"))
718	if _, err := Genesis(1000, []Address{a, a}, []GenesisVote{{Voter: a}}, nil); !errors.Is(err, ErrGenesis) {
719		t.Fatal("duplicate registry entry should fail")
720	}
721	st, err := Genesis(1000, []Address{a}, []GenesisVote{{Voter: a}}, nil)
722	if err != nil || st.Reg[0].Count() != 1 || st.Period != 0 || st.Slot != 0 || st.Number != 0 || st.Time != 1000 {
723		t.Fatal("genesis")
724	}
725	if st.TimeOf(10) != 1600 || st.SlotAt(1600) != 10 || st.SlotAt(1659) != 10 || st.SlotAt(500) != 0 {
726		t.Fatal("tip clock")
727	}
728	if _, ok := st.Partner(a); ok {
729		t.Fatal("a registry of one has no pairs")
730	}
731	// State is immutable across AtSlot.
732	rot := st.AtSlot(2 * params.SlotsPerPeriod)
733	if rot.Period != 2 || rot.Election[0].Count() != 0 || st.Election[0].Count() != 1 || st.Period != 0 {
734		t.Fatal("rotation must not touch the original")
735	}
736}
737
738func TestOpEncoding(t *testing.T) {
739	k := keyFor("k")
740	var sg [64]byte
741	sg[0] = 7
742	ops := []Op{
743		&Transfer{Inputs: []Address{h("i")}, Outputs: []wire.TransferOutput{{Amount: 5, Owners: []Address{addrOf(k), h("o")}, Threshold: 2}}, Sigs: [][64]byte{sg, sg}},
744		&Mix{TokenID: 2, Inputs: []Address{h("i"), h("j")}, Outputs: []wire.MixOutput{{MixCount: 1, Owner: h("a")}, {MixCount: 3, Owner: h("b")}}, Sigs: [][64]byte{sg, sg}},
745		&Vote{TokenUTXO: h("t"), Commit: h("c"), Sig: sg},
746		&Register{TokenUTXOs: []Address{h("1"), h("2"), h("3")}, Sig: sg},
747		&Verify{RegAddr: h("r"), Sig: sg},
748		&Verified{RegAddr: h("r"), Sig: sg},
749		&Commit{RngAddr: h("r"), Commit: h("c"), Sig: sg},
750		&Reveal{RngAddr: h("r"), Preimage: h("p"), Sig: sg},
751		&Prune{UTXO: h("u")},
752	}
753	for _, op := range ops {
754		enc := op.Bytes()
755		if enc[0] != op.Opcode() {
756			t.Fatal("opcode prefix")
757		}
758		dec, err := DecodeOp(enc)
759		if err != nil {
760			t.Fatalf("decode 0x%02x: %v", op.Opcode(), err)
761		}
762		if string(dec.Bytes()) != string(enc) {
763			t.Fatalf("round trip 0x%02x", op.Opcode())
764		}
765		if _, err := DecodeOp(append(enc, 0)); err == nil {
766			t.Fatalf("trailing byte accepted for 0x%02x", op.Opcode())
767		}
768		if _, err := DecodeOp(enc[:len(enc)-1]); err == nil {
769			t.Fatalf("truncation accepted for 0x%02x", op.Opcode())
770		}
771		m0, _ := op.Message(0)
772		m1, _ := op.Message(1)
773		// The tx hash is the message, and signatures are not part of it.
774		if txh, _ := TxHash(op, 0); txh != m0 {
775			t.Fatal("tx hash must be the signing message")
776		}
777		resigned, _ := DecodeOp(enc)
778		if sigs := resigned.Signatures(); len(sigs) > 0 {
779			tampered := resigned.Bytes()
780			tampered[len(tampered)-1] ^= 0xff // last byte of the last signature
781			r2, err := DecodeOp(tampered)
782			if err != nil {
783				t.Fatal(err)
784			}
785			if h2, _ := TxHash(r2, 0); h2 != m0 {
786				t.Fatal("tx hash must not depend on signatures")
787			}
788		}
789		switch op.(type) {
790		case *Verify, *Verified, *Commit, *Reveal:
791			if m0 == m1 {
792				t.Fatal("period must be part of the message")
793			}
794		default:
795			if m0 != m1 {
796				t.Fatal("period must not affect the message")
797			}
798		}
799	}
800	if _, err := DecodeOp([]byte{0x42}); !errors.Is(err, ErrOpcode) {
801		t.Fatal("unknown opcode")
802	}
803	if _, err := DecodeOp(nil); err == nil {
804		t.Fatal("empty")
805	}
806	blk := &Block{Ops: ops}
807	dec, err := DecodeBlock(blk.Bytes())
808	if err != nil || len(dec.Ops) != len(ops) || string(dec.Bytes()) != string(blk.Bytes()) {
809		t.Fatalf("block round trip: %v", err)
810	}
811}
812
813func TestForkChoice(t *testing.T) {
814	a, b := &State{Number: 5, Slot: 50}, &State{Number: 5, Slot: 52}
815	if !Better(a, b) || Better(b, a) {
816		t.Fatal("fewer skipped slots wins at equal number")
817	}
818	c := &State{Number: 6, Slot: 90}
819	if !Better(c, a) || Better(a, c) {
820		t.Fatal("higher number wins")
821	}
822	if Better(a, a) {
823		t.Fatal("a tip is not better than itself")
824	}
825}
826
827// BenchmarkApplyTransfers measures validating a block of single-signature
828// transfers; the cost is dominated by Ed25519 verification.
829func BenchmarkApplyTransfers(b *testing.B) {
830	const nTx = 1000
831	s := newSim(&testing.T{}, 4)
832	// Seed the coin trie directly with nTx UTXOs owned by distinct keys.
833	st := s.st
834	keys := make([]*sig.Keypair, nTx)
835	ids := make([]Hash, nTx)
836	for i := range keys {
837		keys[i] = keyFor(fmt.Sprintf("bench-%d", i))
838		ids[i] = h(fmt.Sprintf("utxo-%d", i))
839		e := wire.CoinEntry{Owners: []Address{addrOf(keys[i])}, Threshold: 1, Amount: params.TOKEN, Slot: 0}
840		st.Coin, _ = st.Coin.Insert(ids[i], e.Bytes())
841	}
842	ops := make([]Op, nTx)
843	for i := range ops {
844		ops[i] = s.transfer([]Hash{ids[i]}, []*sig.Keypair{keys[i]}, []wire.TransferOutput{single(keys[(i+1)%nTx], params.TOKEN/2)})
845	}
846	voter, _, _ := st.Validator(1)
847	v := s.validators[0][voter]
848	blk, _, err := st.Assemble(1, ops, v.key, v.nonce)
849	if err != nil {
850		b.Fatal(err)
851	}
852	b.ResetTimer()
853	for i := 0; i < b.N; i++ {
854		if _, err := st.Apply(blk); err != nil {
855			b.Fatal(err)
856		}
857	}
858	b.ReportMetric(float64(nTx)*float64(b.N)/b.Elapsed().Seconds(), "tx/s")
859}