peoplecoin

  1package state
  2
  3import (
  4	"errors"
  5	"fmt"
  6	"math"
  7
  8	"peoplecoin/coin"
  9	"peoplecoin/params"
 10	"peoplecoin/period"
 11	"peoplecoin/rng"
 12	"peoplecoin/sig"
 13	"peoplecoin/trie"
 14	"peoplecoin/wire"
 15)
 16
 17// Validation errors. Each identifies the rule that failed.
 18var (
 19	ErrPhase            = errors.New("state: operation not allowed in this phase")
 20	ErrSignature        = errors.New("state: bad signature")
 21	ErrMissingInput     = errors.New("state: input not found")
 22	ErrDuplicate        = errors.New("state: duplicate input")
 23	ErrAmount           = errors.New("state: bad amount")
 24	ErrOwners           = errors.New("state: bad owners or threshold")
 25	ErrInsufficient     = errors.New("state: outputs exceed spendable inputs")
 26	ErrOverflow         = errors.New("state: arithmetic overflow")
 27	ErrTokenType        = errors.New("state: wrong token type")
 28	ErrTokenOwner       = errors.New("state: tokens have different owners")
 29	ErrTokenCount       = errors.New("state: wrong number of tokens")
 30	ErrMixCount         = errors.New("state: mix counts do not add up")
 31	ErrMixCap           = errors.New("state: mix count over cap")
 32	ErrOccupied         = errors.New("state: address already has an entry")
 33	ErrNotRegistered    = errors.New("state: no registration")
 34	ErrAlreadySet       = errors.New("state: flag already set")
 35	ErrNoPartner        = errors.New("state: no partner this period")
 36	ErrPartnerNotVerify = errors.New("state: pair has not both verified")
 37	ErrCommitZero       = errors.New("state: commit is zero")
 38	ErrCommitSet        = errors.New("state: commit already set")
 39	ErrNoCommit         = errors.New("state: nothing to reveal")
 40	ErrPreimage         = errors.New("state: preimage does not match commit")
 41	ErrNotPrunable      = errors.New("state: entry not prunable")
 42	ErrConflict         = errors.New("state: two operations write the same key")
 43	ErrDuplicateTx      = errors.New("state: duplicate transaction")
 44	ErrSlotTooLarge     = errors.New("state: slot does not fit a coin entry")
 45
 46	ErrNumber      = errors.New("state: wrong block number")
 47	ErrSlot        = errors.New("state: slot not after the previous block")
 48	ErrTime        = errors.New("state: time is not the slot's start")
 49	ErrPrev        = errors.New("state: prev does not match")
 50	ErrNoValidator = errors.New("state: no validators this period")
 51	ErrValidator   = errors.New("state: validator does not match the slot's vote")
 52	ErrRoots       = errors.New("state: header roots do not match state")
 53	ErrHeaderSig   = errors.New("state: bad header signature")
 54)
 55
 56type trieID uint8
 57
 58const (
 59	tCoin trieID = iota
 60	tToken
 61	tElection1
 62	tRng0
 63	tRng1
 64	tReg0
 65	tReg1
 66)
 67
 68type writeKind uint8
 69
 70const (
 71	wInsert writeKind = iota
 72	wUpdate
 73	wDelete
 74)
 75
 76// write is one change to one trie key.
 77type write struct {
 78	t     trieID
 79	key   trie.Key
 80	kind  writeKind
 81	value []byte
 82}
 83
 84// effect is what a valid operation does to the state.
 85type effect struct {
 86	writes []write
 87	fee    uint64  // added to the block's fee accumulator
 88	vote   *uint64 // RNG vote cast by a Reveal
 89}
 90
 91func (e *effect) insert(t trieID, key Hash, value []byte) {
 92	e.writes = append(e.writes, write{t, trie.Key(key), wInsert, value})
 93}
 94
 95func (e *effect) update(t trieID, key Hash, value []byte) {
 96	e.writes = append(e.writes, write{t, trie.Key(key), wUpdate, value})
 97}
 98
 99func (e *effect) del(t trieID, key Hash) {
100	e.writes = append(e.writes, write{t, trie.Key(key), wDelete, nil})
101}
102
103func (s *State) trieFor(t trieID) **trie.Trie {
104	switch t {
105	case tCoin:
106		return &s.Coin
107	case tToken:
108		return &s.Token
109	case tElection1:
110		return &s.Election[1]
111	case tRng0:
112		return &s.Rng[0]
113	case tRng1:
114		return &s.Rng[1]
115	case tReg0:
116		return &s.Reg[0]
117	default:
118		return &s.Reg[1]
119	}
120}
121
122// ctx is what an operation is validated in.
123type ctx struct {
124	slot   uint64
125	period uint32
126	txHash Hash
127}
128
129func checkSig(pub Address, msg Hash, s [64]byte) error {
130	if !sig.Verify(sig.PublicKey(pub), msg[:], sig.Signature(s)) {
131		return ErrSignature
132	}
133	return nil
134}
135
136func noDuplicates(ids []Address) error {
137	seen := make(map[Address]bool, len(ids))
138	for _, id := range ids {
139		if seen[id] {
140			return ErrDuplicate
141		}
142		seen[id] = true
143	}
144	return nil
145}
146
147func add(a, b uint64) (uint64, error) {
148	if a > math.MaxUint64-b {
149		return 0, ErrOverflow
150	}
151	return a + b, nil
152}
153
154// validate checks op against s, the pre-block state, and returns its effect.
155func (s *State) validate(op Op, c ctx) (*effect, error) {
156	switch o := op.(type) {
157	case *Transfer:
158		return s.validateTransfer(o, c)
159	case *Mix:
160		return s.validateMix(o, c)
161	case *Vote:
162		return s.validateVote(o, c)
163	case *Register:
164		return s.validateRegister(o, c)
165	case *Verify:
166		return s.validateVerify(o, c)
167	case *Verified:
168		return s.validateVerified(o, c)
169	case *Commit:
170		return s.validateCommit(o, c)
171	case *Reveal:
172		return s.validateReveal(o, c)
173	case *Prune:
174		return s.validatePrune(o, c)
175	}
176	return nil, ErrOpcode
177}
178
179func (s *State) validateTransfer(o *Transfer, c ctx) (*effect, error) {
180	if len(o.Inputs) == 0 || len(o.Inputs) > 255 || len(o.Outputs) == 0 || len(o.Outputs) > 255 {
181		return nil, ErrEncoding
182	}
183	if c.slot > math.MaxUint32 {
184		return nil, ErrSlotTooLarge
185	}
186	if err := noDuplicates(o.Inputs); err != nil {
187		return nil, err
188	}
189	msg, err := o.Message(c.period)
190	if err != nil {
191		return nil, err
192	}
193	var sumEff, sumSpend, sumOut uint64
194	sigIdx := 0
195	e := &effect{}
196	for _, id := range o.Inputs {
197		entry, ok := s.CoinEntry(id)
198		if !ok {
199			return nil, ErrMissingInput
200		}
201		t := coin.Elapsed(entry.Slot, c.slot)
202		if sumEff, err = add(sumEff, coin.Effective(entry.Amount, t)); err != nil {
203			return nil, err
204		}
205		if sumSpend, err = add(sumSpend, coin.Spendable(entry.Amount, t)); err != nil {
206			return nil, err
207		}
208		// Exactly threshold signatures, matched against the owners in
209		// ascending owner-index order; a signature that matches no owner
210		// after the previous match is a failure.
211		ownerIdx := 0
212		for k := 0; k < int(entry.Threshold); k++ {
213			if sigIdx >= len(o.Sigs) {
214				return nil, ErrSignature
215			}
216			matched := -1
217			for j := ownerIdx; j < len(entry.Owners); j++ {
218				if checkSig(entry.Owners[j], msg, o.Sigs[sigIdx]) == nil {
219					matched = j
220					break
221				}
222			}
223			if matched < 0 {
224				return nil, ErrSignature
225			}
226			ownerIdx = matched + 1
227			sigIdx++
228		}
229		e.del(tCoin, id)
230	}
231	if sigIdx != len(o.Sigs) {
232		return nil, ErrSignature // extra signatures
233	}
234	for i, out := range o.Outputs {
235		if out.Amount == 0 {
236			return nil, ErrAmount
237		}
238		if len(out.Owners) < 1 || len(out.Owners) > params.MaxOwners || out.Threshold < 1 || int(out.Threshold) > len(out.Owners) {
239			return nil, ErrOwners
240		}
241		if sumOut, err = add(sumOut, out.Amount); err != nil {
242			return nil, err
243		}
244		entry := wire.CoinEntry{Owners: out.Owners, Threshold: out.Threshold, Amount: out.Amount, Slot: uint32(c.slot)}
245		e.insert(tCoin, wire.UTXOID(c.txHash, uint8(i)), entry.Bytes())
246	}
247	if sumOut > sumSpend {
248		return nil, ErrInsufficient
249	}
250	e.fee = sumEff - sumOut
251	return e, nil
252}
253
254func (s *State) validateMix(o *Mix, c ctx) (*effect, error) {
255	if len(o.Inputs) == 0 || len(o.Inputs) > 255 || len(o.Outputs) != len(o.Inputs) || len(o.Sigs) != len(o.Inputs) {
256		return nil, ErrTokenCount
257	}
258	if err := noDuplicates(o.Inputs); err != nil {
259		return nil, err
260	}
261	msg, err := o.Message(c.period)
262	if err != nil {
263		return nil, err
264	}
265	var sumIn, sumOut uint64
266	e := &effect{}
267	for i, id := range o.Inputs {
268		entry, ok := s.TokenEntry(id)
269		if !ok {
270			return nil, ErrMissingInput
271		}
272		if entry.TokenID != o.TokenID {
273			return nil, ErrTokenType
274		}
275		if err := checkSig(entry.Owner, msg, o.Sigs[i]); err != nil {
276			return nil, err
277		}
278		sumIn += uint64(entry.MixCount) + 1
279		e.del(tToken, id)
280	}
281	for i, out := range o.Outputs {
282		if out.MixCount > params.MaxMixes {
283			return nil, ErrMixCap
284		}
285		sumOut += uint64(out.MixCount)
286		entry := wire.TokenEntry{TokenID: o.TokenID, Owner: out.Owner, MixCount: out.MixCount}
287		e.insert(tToken, wire.UTXOID(c.txHash, uint8(i)), entry.Bytes())
288	}
289	if sumIn != sumOut {
290		return nil, ErrMixCount
291	}
292	return e, nil
293}
294
295func (s *State) validateVote(o *Vote, c ctx) (*effect, error) {
296	entry, ok := s.TokenEntry(o.TokenUTXO)
297	if !ok {
298		return nil, ErrMissingInput
299	}
300	if entry.TokenID != params.TokenElection {
301		return nil, ErrTokenType
302	}
303	msg, _ := o.Message(c.period)
304	if err := checkSig(entry.Owner, msg, o.Sig); err != nil {
305		return nil, err
306	}
307	if s.Election[1].Has(entry.Owner) {
308		return nil, ErrOccupied
309	}
310	e := &effect{}
311	e.del(tToken, o.TokenUTXO)
312	e.insert(tElection1, entry.Owner, (&wire.ElectionEntry{Commit: o.Commit}).Bytes())
313	return e, nil
314}
315
316func (s *State) validateRegister(o *Register, c ctx) (*effect, error) {
317	n := len(o.TokenUTXOs)
318	if n != 1 && n != params.InviteCost {
319		return nil, ErrTokenCount
320	}
321	if err := noDuplicates(o.TokenUTXOs); err != nil {
322		return nil, err
323	}
324	want := params.TokenInvite
325	if n == 1 {
326		want = params.TokenRegistration
327	}
328	var owner Address
329	e := &effect{}
330	for i, id := range o.TokenUTXOs {
331		entry, ok := s.TokenEntry(id)
332		if !ok {
333			return nil, ErrMissingInput
334		}
335		if entry.TokenID != want {
336			return nil, ErrTokenType
337		}
338		if i == 0 {
339			owner = entry.Owner
340		} else if entry.Owner != owner {
341			return nil, ErrTokenOwner
342		}
343		e.del(tToken, id)
344	}
345	msg, err := o.Message(c.period)
346	if err != nil {
347		return nil, err
348	}
349	if err := checkSig(owner, msg, o.Sig); err != nil {
350		return nil, err
351	}
352	if s.Reg[1].Has(owner) {
353		return nil, ErrOccupied
354	}
355	e.insert(tReg1, owner, (&wire.RegEntry{}).Bytes())
356	return e, nil
357}
358
359func (s *State) validateVerify(o *Verify, c ctx) (*effect, error) {
360	entry, ok := s.RegEntry(0, o.RegAddr)
361	if !ok {
362		return nil, ErrNotRegistered
363	}
364	if entry.Verify {
365		return nil, ErrAlreadySet
366	}
367	msg, _ := o.Message(c.period)
368	if err := checkSig(o.RegAddr, msg, o.Sig); err != nil {
369		return nil, err
370	}
371	e := &effect{}
372	entry.Verify = true
373	e.update(tReg0, o.RegAddr, entry.Bytes())
374	return e, nil
375}
376
377func (s *State) validateVerified(o *Verified, c ctx) (*effect, error) {
378	entry, ok := s.RegEntry(0, o.RegAddr)
379	if !ok {
380		return nil, ErrNotRegistered
381	}
382	if entry.Verified {
383		return nil, ErrAlreadySet
384	}
385	partner, ok := s.Partner(o.RegAddr)
386	if !ok {
387		return nil, ErrNoPartner
388	}
389	pentry, _ := s.RegEntry(0, partner)
390	if !entry.Verify || pentry == nil || !pentry.Verify {
391		return nil, ErrPartnerNotVerify
392	}
393	msg, _ := o.Message(c.period)
394	if err := checkSig(o.RegAddr, msg, o.Sig); err != nil {
395		return nil, err
396	}
397	if s.Rng[1].Has(o.RegAddr) {
398		return nil, ErrOccupied
399	}
400	e := &effect{}
401	entry.Verified = true
402	e.update(tReg0, o.RegAddr, entry.Bytes())
403	for i, id := range []uint8{params.TokenElection, params.TokenRegistration, params.TokenInvite} {
404		tok := wire.TokenEntry{TokenID: id, Owner: o.RegAddr}
405		e.insert(tToken, wire.UTXOID(c.txHash, uint8(i)), tok.Bytes())
406	}
407	e.insert(tRng1, o.RegAddr, (&wire.RngEntry{}).Bytes())
408	return e, nil
409}
410
411func (s *State) validateCommit(o *Commit, c ctx) (*effect, error) {
412	entry, ok := s.RngEntry(1, o.RngAddr)
413	if !ok {
414		return nil, ErrNotRegistered
415	}
416	if entry.Commit != (Hash{}) {
417		return nil, ErrCommitSet
418	}
419	if o.Commit == (Hash{}) {
420		return nil, ErrCommitZero
421	}
422	msg, _ := o.Message(c.period)
423	if err := checkSig(o.RngAddr, msg, o.Sig); err != nil {
424		return nil, err
425	}
426	e := &effect{}
427	e.update(tRng1, o.RngAddr, (&wire.RngEntry{Commit: o.Commit}).Bytes())
428	return e, nil
429}
430
431func (s *State) validateReveal(o *Reveal, c ctx) (*effect, error) {
432	if c.slot > math.MaxUint32 {
433		return nil, ErrSlotTooLarge
434	}
435	entry, ok := s.RngEntry(0, o.RngAddr)
436	if !ok {
437		return nil, ErrNotRegistered
438	}
439	if entry.Commit == (Hash{}) {
440		return nil, ErrNoCommit
441	}
442	if rng.Commit(o.Preimage) != entry.Commit {
443		return nil, ErrPreimage
444	}
445	msg, _ := o.Message(c.period)
446	if err := checkSig(o.RngAddr, msg, o.Sig); err != nil {
447		return nil, err
448	}
449	e := &effect{}
450	e.update(tRng0, o.RngAddr, (&wire.RngEntry{}).Bytes())
451	ubi := wire.CoinEntry{Owners: []Address{o.RngAddr}, Threshold: 1, Amount: params.UBIPerPeriod, Slot: uint32(c.slot)}
452	e.insert(tCoin, wire.UTXOID(c.txHash, 0), ubi.Bytes())
453	v := rng.Vote(o.RngAddr, o.Preimage, s.Seed, s.Rng[0].Count())
454	e.vote = &v
455	return e, nil
456}
457
458func (s *State) validatePrune(o *Prune, c ctx) (*effect, error) {
459	entry, ok := s.CoinEntry(o.UTXO)
460	if !ok {
461		return nil, ErrMissingInput
462	}
463	t := coin.Elapsed(entry.Slot, c.slot)
464	if !coin.Prunable(entry.Amount, t) {
465		return nil, ErrNotPrunable
466	}
467	e := &effect{fee: coin.Effective(entry.Amount, t)}
468	e.del(tCoin, o.UTXO)
469	return e, nil
470}
471
472// ---------------------------------------------------------------------
473// Block execution
474
475type keyRef struct {
476	t   trieID
477	key trie.Key
478}
479
480// execute validates ops against pre (the state at the block's slot, before
481// the block) and returns the post state, with fees paid to validator and
482// voter, and the tx trie root.
483func execute(pre *State, number, slot uint64, validator, voter Address, ops []Op) (*State, trie.Hash, error) {
484	c := ctx{slot: slot, period: period.Number(slot)}
485	phase := period.Phase(slot)
486	txTrie := trie.NewPlain()
487	written := map[keyRef]bool{}
488	effects := make([]*effect, 0, len(ops))
489	var fee uint64
490
491	for _, op := range ops {
492		if !allowedPhase(op.Opcode(), phase) {
493			return nil, trie.Hash{}, fmt.Errorf("%w: opcode 0x%02x in phase %d", ErrPhase, op.Opcode(), phase)
494		}
495		txh, err := TxHash(op, c.period)
496		if err != nil {
497			return nil, trie.Hash{}, err
498		}
499		if txTrie, err = txTrie.Insert(trie.Key(txh), op.Bytes()); err != nil {
500			return nil, trie.Hash{}, ErrDuplicateTx
501		}
502		c.txHash = txh
503		eff, err := pre.validate(op, c)
504		if err != nil {
505			return nil, trie.Hash{}, fmt.Errorf("tx %x: %w", txh[:4], err)
506		}
507		for _, w := range eff.writes {
508			ref := keyRef{w.t, w.key}
509			if written[ref] {
510				return nil, trie.Hash{}, ErrConflict
511			}
512			written[ref] = true
513		}
514		if fee, err = add(fee, eff.fee); err != nil {
515			return nil, trie.Hash{}, err
516		}
517		effects = append(effects, eff)
518	}
519
520	post := *pre
521	post.Tally = pre.Tally.Clone()
522	for _, eff := range effects {
523		for _, w := range eff.writes {
524			tr := post.trieFor(w.t)
525			var err error
526			switch w.kind {
527			case wInsert:
528				*tr, err = (*tr).Insert(w.key, w.value)
529			case wUpdate:
530				*tr, err = (*tr).Update(w.key, w.value)
531			case wDelete:
532				*tr, err = (*tr).Delete(w.key)
533			}
534			if err != nil {
535				// Cannot happen: every write was validated against pre and
536				// no two writes share a key.
537				return nil, trie.Hash{}, fmt.Errorf("state: apply: %w", err)
538			}
539		}
540		if eff.vote != nil {
541			post.Tally.Add(*eff.vote)
542		}
543	}
544
545	// Fees: split 50-50, odd unit to the validator; only non-zero outputs.
546	if fee > 0 {
547		if slot > math.MaxUint32 {
548			return nil, trie.Hash{}, ErrSlotTooLarge
549		}
550		voterShare := fee / 2
551		validatorShare := fee - voterShare
552		for i, p := range []struct {
553			owner  Address
554			amount uint64
555		}{{validator, validatorShare}, {voter, voterShare}} {
556			if p.amount == 0 {
557				continue
558			}
559			entry := wire.CoinEntry{Owners: []Address{p.owner}, Threshold: 1, Amount: p.amount, Slot: uint32(slot)}
560			var err error
561			if post.Coin, err = post.Coin.Insert(trie.Key(wire.FeeUTXOID(number, uint8(i))), entry.Bytes()); err != nil {
562				return nil, trie.Hash{}, ErrConflict
563			}
564		}
565	}
566	return &post, txTrie.Root(), nil
567}
568
569// checkHeader validates the parts of the header that do not depend on the
570// operations, and returns the pre-block state and the slot's voter.
571func (s *State) checkHeader(h *Header) (pre *State, voter Address, err error) {
572	if h.Number != s.Number+1 {
573		return nil, Address{}, ErrNumber
574	}
575	if h.Slot <= s.Slot {
576		return nil, Address{}, ErrSlot
577	}
578	// time is the slot's start, carried forward from the previous header
579	// so that no node needs to remember the genesis time.
580	if h.Time != s.TimeOf(h.Slot) {
581		return nil, Address{}, ErrTime
582	}
583	if h.Prev != s.PrevHash {
584		return nil, Address{}, ErrPrev
585	}
586	pre = s.AtSlot(h.Slot)
587	voter, commit, ok := pre.Validator(h.Slot)
588	if !ok {
589		return nil, Address{}, ErrNoValidator
590	}
591	if rng.ElectionCommit(h.Validator, h.Nonce) != commit {
592		return nil, Address{}, ErrValidator
593	}
594	return pre, voter, nil
595}
596
597// Apply validates b on top of s and returns the resulting state.
598func (s *State) Apply(b *Block) (*State, error) {
599	h := &b.Header
600	pre, voter, err := s.checkHeader(h)
601	if err != nil {
602		return nil, err
603	}
604	post, txRoot, err := execute(pre, h.Number, h.Slot, h.Validator, voter, b.Ops)
605	if err != nil {
606		return nil, err
607	}
608	if !h.rootsMatch(txRoot, post.Roots()) {
609		return nil, ErrRoots
610	}
611	if err := checkSig(h.Validator, h.SigningHash(), h.Sig); err != nil {
612		return nil, ErrHeaderSig
613	}
614	post.Number, post.Slot, post.Time, post.PrevHash = h.Number, h.Slot, h.Time, h.Hash()
615	return post, nil
616}
617
618// Assemble produces and signs the block for slot on top of s, containing
619// ops, which must all be valid; the caller filters its mempool first. It
620// returns the block and the state after it.
621func (s *State) Assemble(slot uint64, ops []Op, validator *sig.Keypair, nonce Hash) (*Block, *State, error) {
622	h := &Header{Number: s.Number + 1, Slot: slot, Time: s.TimeOf(slot), Prev: s.PrevHash, Validator: Address(validator.Public), Nonce: nonce}
623	pre, voter, err := s.checkHeader(h)
624	if err != nil {
625		return nil, nil, err
626	}
627	post, txRoot, err := execute(pre, h.Number, h.Slot, h.Validator, voter, ops)
628	if err != nil {
629		return nil, nil, err
630	}
631	h.setRoots(txRoot, post.Roots())
632	sh := h.SigningHash()
633	h.Sig = validator.Sign(sh[:])
634	post.Number, post.Slot, post.Time, post.PrevHash = h.Number, h.Slot, h.Time, h.Hash()
635	return &Block{Header: *h, Ops: ops}, post, nil
636}