peoplecoin

  1// Package rng holds the random number and what it drives: the votes cast
  2// by reveals, the tally that turns them into a seed, and the seeded choice
  3// of block producer for each slot.
  4//
  5// Every Verified creates an RNG entry that commits to a number in phases
  6// 0–1 and reveals it in phase 2 of the following period. A reveal casts a
  7// vote,
  8//
  9//	SHA256(address ‖ preimage ‖ seed) mod rngEntryCount
 10//
 11// with the seed of the period the reveal takes place in, which was unknown
 12// when the preimage was chosen. At the period boundary the number with the
 13// most votes wins, the lowest on a tie, and becomes the seed as a
 14// big-endian uint64 zero-padded to 32 bytes; 0 if nobody revealed.
 15//
 16// The slot's validator is the election entry at index
 17//
 18//	SHA256(seed ‖ uint64(slot)) mod electionEntryCount
 19//
 20// hidden until block production by the commit SHA256(validator ‖ nonce).
 21package rng
 22
 23import (
 24	"crypto/sha256"
 25	"encoding/binary"
 26	"math/big"
 27	"sort"
 28)
 29
 30// HashMod interprets h as a big-endian integer and reduces it mod n. It
 31// panics if n is zero.
 32func HashMod(h [32]byte, n uint64) uint64 {
 33	if n == 0 {
 34		panic("rng: modulus zero")
 35	}
 36	return new(big.Int).Mod(new(big.Int).SetBytes(h[:]), new(big.Int).SetUint64(n)).Uint64()
 37}
 38
 39// Commit is the commitment to a preimage.
 40func Commit(preimage [32]byte) [32]byte { return sha256.Sum256(preimage[:]) }
 41
 42// Vote returns the number a reveal votes for, given the entry's address,
 43// the revealed preimage, the current seed and the number of RNG entries.
 44func Vote(addr, preimage, seed [32]byte, entries uint64) uint64 {
 45	h := sha256.New()
 46	h.Write(addr[:])
 47	h.Write(preimage[:])
 48	h.Write(seed[:])
 49	var sum [32]byte
 50	copy(sum[:], h.Sum(nil))
 51	return HashMod(sum, entries)
 52}
 53
 54// Seed encodes a winning number as a seed: big-endian uint64 in the last
 55// eight bytes.
 56func Seed(number uint64) [32]byte {
 57	var s [32]byte
 58	binary.BigEndian.PutUint64(s[24:], number)
 59	return s
 60}
 61
 62// SeedNumber recovers the number from a seed.
 63func SeedNumber(seed [32]byte) uint64 { return binary.BigEndian.Uint64(seed[24:]) }
 64
 65// Tally counts votes over a period's reveals. It is auxiliary state, not
 66// committed in any trie: it is recomputed from the Reveal operations in the
 67// period's phase 2 blocks, and only its outcome, the seed, persists.
 68type Tally struct {
 69	votes map[uint64]uint64
 70}
 71
 72// NewTally returns an empty tally.
 73func NewTally() *Tally { return &Tally{votes: map[uint64]uint64{}} }
 74
 75// Add records one vote for number.
 76func (t *Tally) Add(number uint64) { t.votes[number]++ }
 77
 78// Clone returns an independent copy.
 79func (t *Tally) Clone() *Tally {
 80	c := NewTally()
 81	for n, v := range t.votes {
 82		c.votes[n] = v
 83	}
 84	return c
 85}
 86
 87// Total returns the number of votes cast.
 88func (t *Tally) Total() uint64 {
 89	var n uint64
 90	for _, c := range t.votes {
 91		n += c
 92	}
 93	return n
 94}
 95
 96// Winner returns the number with the most votes, the lowest on a tie, and
 97// false if no votes were cast.
 98func (t *Tally) Winner() (uint64, bool) {
 99	var best, bestCount uint64
100	found := false
101	for n, c := range t.votes {
102		if !found || c > bestCount || (c == bestCount && n < best) {
103			best, bestCount, found = n, c, true
104		}
105	}
106	return best, found
107}
108
109// NextSeed is the seed for the following period: the winner, or 0.
110func (t *Tally) NextSeed() [32]byte {
111	n, _ := t.Winner()
112	return Seed(n)
113}
114
115// Counts returns (number, votes) pairs sorted by number, for inspection.
116func (t *Tally) Counts() [][2]uint64 {
117	out := make([][2]uint64, 0, len(t.votes))
118	for n, c := range t.votes {
119		out = append(out, [2]uint64{n, c})
120	}
121	sort.Slice(out, func(i, j int) bool { return out[i][0] < out[j][0] })
122	return out
123}
124
125// ValidatorIndex returns the index in election_trie[0] of the entry whose
126// validator owns slot. entries must be non-zero: a period without votes has
127// no validators and the chain ends.
128func ValidatorIndex(seed [32]byte, slot, entries uint64) uint64 {
129	h := sha256.New()
130	h.Write(seed[:])
131	var b [8]byte
132	binary.BigEndian.PutUint64(b[:], slot)
133	h.Write(b[:])
134	var sum [32]byte
135	copy(sum[:], h.Sum(nil))
136	return HashMod(sum, entries)
137}
138
139// ElectionCommit is SHA256(validator_pubkey ‖ nonce), the content of a
140// Vote, revealed in the header of every block the validator produces.
141func ElectionCommit(validator, nonce [32]byte) [32]byte {
142	h := sha256.New()
143	h.Write(validator[:])
144	h.Write(nonce[:])
145	var sum [32]byte
146	copy(sum[:], h.Sum(nil))
147	return sum
148}