peoplecoin

  1// Package state is the ledger: the seven tries, the seed and the period,
  2// and the rules by which a block moves them forward.
  3//
  4// A State is immutable. Applying a block returns a new State that shares
  5// unchanged subtrees with the old one, so any State ever produced stays
  6// valid — that is what makes validating a block against pre-block state,
  7// and switching between forks, straightforward.
  8//
  9// The rotating tries hold the current period in [0] and the next in [1]:
 10// the registry being paired now and the one being registered for next
 11// month; the votes producing blocks now and the votes for next month; the
 12// numbers being revealed now and the commits for next month. At the period
 13// boundary the reveals are tallied into the seed, [1] rotates into [0], and
 14// [1] and the token trie are cleared.
 15package state
 16
 17import (
 18	"errors"
 19
 20	"peoplecoin/feistel"
 21	"peoplecoin/params"
 22	"peoplecoin/period"
 23	"peoplecoin/rng"
 24	"peoplecoin/trie"
 25	"peoplecoin/wire"
 26)
 27
 28// Address is a 32-byte public key; Hash a 32-byte digest.
 29type (
 30	Address = [32]byte
 31	Hash    = [32]byte
 32)
 33
 34// State is the ledger at the tip of a chain.
 35type State struct {
 36	Number   uint64 // last block number; 0 at genesis
 37	Slot     uint64 // last block slot; 0 at genesis
 38	Time     uint64 // Unix time of that slot's start; genesis time at genesis
 39	Period   uint64 // period the rotating tries describe
 40	PrevHash Hash   // hash of the last block; zero at genesis
 41	Seed     Hash   // this period's seed
 42
 43	Coin     *trie.Trie    // plain, keyed by UTXO ID
 44	Token    *trie.Trie    // plain, keyed by UTXO ID
 45	Election [2]*trie.Trie // storage, keyed by voter
 46	Rng      [2]*trie.Trie // storage, keyed by address
 47	Reg      [2]*trie.Trie // storage, keyed by address
 48
 49	Tally *rng.Tally // this period's reveals; side state, not committed
 50}
 51
 52// Roots are the trie roots committed in a header.
 53type Roots struct {
 54	Coin, Token trie.Hash
 55	Election    [2]trie.Hash
 56	Rng         [2]trie.Hash
 57	Reg         [2]trie.Hash
 58}
 59
 60// Empty returns a state with no entries at slot 0 of period 0, starting at
 61// Unix time genesisTime, which by convention is 07:00 UTC on a Saturday.
 62func Empty(genesisTime uint64) *State {
 63	return &State{
 64		Time:     genesisTime,
 65		Coin:     trie.NewPlain(),
 66		Token:    trie.NewPlain(),
 67		Election: [2]*trie.Trie{trie.NewStorage(), trie.NewStorage()},
 68		Rng:      [2]*trie.Trie{trie.NewStorage(), trie.NewStorage()},
 69		Reg:      [2]*trie.Trie{trie.NewStorage(), trie.NewStorage()},
 70		Tally:    rng.NewTally(),
 71	}
 72}
 73
 74// GenesisVote is a vote present in election_trie[0] at genesis.
 75type GenesisVote struct {
 76	Voter  Address
 77	Commit Hash // SHA256(validator ‖ nonce)
 78}
 79
 80// GenesisToken is a token present at genesis, keyed by an arbitrary ID.
 81type GenesisToken struct {
 82	ID    Hash
 83	Entry wire.TokenEntry
 84}
 85
 86var ErrGenesis = errors.New("state: invalid genesis")
 87
 88// Genesis builds the state the chain starts from at Unix time genesisTime:
 89// a registry to be paired in period 0, at least one vote for period 0's
 90// blocks, and the tokens — at least one election token — from which period
 91// 1's votes and registry are made. The coin trie is empty; the first UBI is
 92// paid by the first reveals, in period 1.
 93func Genesis(genesisTime uint64, registry []Address, votes []GenesisVote, tokens []GenesisToken) (*State, error) {
 94	s := Empty(genesisTime)
 95	var err error
 96	for _, a := range registry {
 97		if s.Reg[0], err = s.Reg[0].Insert(a, (&wire.RegEntry{}).Bytes()); err != nil {
 98			return nil, ErrGenesis
 99		}
100	}
101	for _, v := range votes {
102		if s.Election[0], err = s.Election[0].Insert(v.Voter, (&wire.ElectionEntry{Commit: v.Commit}).Bytes()); err != nil {
103			return nil, ErrGenesis
104		}
105	}
106	for _, t := range tokens {
107		if s.Token, err = s.Token.Insert(t.ID, t.Entry.Bytes()); err != nil {
108			return nil, ErrGenesis
109		}
110	}
111	if s.Election[0].Count() == 0 {
112		return nil, ErrGenesis
113	}
114	return s, nil
115}
116
117// Roots returns the trie roots of the state.
118func (s *State) Roots() Roots {
119	return Roots{
120		Coin:     s.Coin.Root(),
121		Token:    s.Token.Root(),
122		Election: [2]trie.Hash{s.Election[0].Root(), s.Election[1].Root()},
123		Rng:      [2]trie.Hash{s.Rng[0].Root(), s.Rng[1].Root()},
124		Reg:      [2]trie.Hash{s.Reg[0].Root(), s.Reg[1].Root()},
125	}
126}
127
128// rotate crosses one period boundary.
129func (s *State) rotate() *State {
130	n := *s
131	n.Period = s.Period + 1
132	n.Seed = s.Tally.NextSeed()
133	n.Election = [2]*trie.Trie{s.Election[1], trie.NewStorage()}
134	n.Rng = [2]*trie.Trie{s.Rng[1], trie.NewStorage()}
135	n.Reg = [2]*trie.Trie{s.Reg[1], trie.NewStorage()}
136	n.Token = trie.NewPlain()
137	n.Tally = rng.NewTally()
138	return &n
139}
140
141// AtSlot returns the state as it stands at slot: rotated through every
142// period boundary between the tip and slot. The tip itself is unchanged.
143func (s *State) AtSlot(slot uint64) *State {
144	cur := s
145	for cur.Period < period.Of(slot) {
146		cur = cur.rotate()
147	}
148	return cur
149}
150
151// TimeOf returns the Unix time at which slot begins, from the tip's own
152// clock: no genesis constant is needed, every header carries the time.
153func (s *State) TimeOf(slot uint64) uint64 {
154	return s.Time + (slot-s.Slot)*params.SlotSeconds
155}
156
157// SlotAt returns the slot containing Unix time t, or the tip's slot for
158// earlier times.
159func (s *State) SlotAt(t uint64) uint64 {
160	if t < s.Time {
161		return s.Slot
162	}
163	return s.Slot + (t-s.Time)/params.SlotSeconds
164}
165
166// Partner returns the address paired with addr in this period's registry,
167// or false if addr is not registered or is the odd one out.
168func (s *State) Partner(addr Address) (Address, bool) {
169	idx, ok := s.Reg[0].Rank(addr)
170	if !ok {
171		return Address{}, false
172	}
173	p, ok := feistel.Partner(idx, s.Reg[0].Count(), s.Seed)
174	if !ok {
175		return Address{}, false
176	}
177	key, _, _ := s.Reg[0].Select(p)
178	return Address(key), true
179}
180
181// Validator returns the voter whose election entry owns slot, and the
182// commit that hides the validator; false if there are no votes, in which
183// case no block can be produced.
184func (s *State) Validator(slot uint64) (voter Address, commit Hash, ok bool) {
185	n := s.Election[0].Count()
186	if n == 0 {
187		return Address{}, Hash{}, false
188	}
189	key, val, _ := s.Election[0].Select(rng.ValidatorIndex(s.Seed, slot, n))
190	e, err := wire.DecodeElectionEntry(val)
191	if err != nil {
192		return Address{}, Hash{}, false
193	}
194	return Address(key), e.Commit, true
195}
196
197// CoinEntry returns the decoded coin entry at id.
198func (s *State) CoinEntry(id Hash) (*wire.CoinEntry, bool) {
199	v, ok := s.Coin.Get(id)
200	if !ok {
201		return nil, false
202	}
203	e, err := wire.DecodeCoinEntry(v)
204	return e, err == nil
205}
206
207// TokenEntry returns the decoded token entry at id.
208func (s *State) TokenEntry(id Hash) (*wire.TokenEntry, bool) {
209	v, ok := s.Token.Get(id)
210	if !ok {
211		return nil, false
212	}
213	e, err := wire.DecodeTokenEntry(v)
214	return e, err == nil
215}
216
217// RegEntry returns the decoded registration at addr in reg_trie[which].
218func (s *State) RegEntry(which int, addr Address) (*wire.RegEntry, bool) {
219	v, ok := s.Reg[which].Get(addr)
220	if !ok {
221		return nil, false
222	}
223	e, err := wire.DecodeRegEntry(v)
224	return e, err == nil
225}
226
227// RngEntry returns the decoded RNG entry at addr in rng_trie[which].
228func (s *State) RngEntry(which int, addr Address) (*wire.RngEntry, bool) {
229	v, ok := s.Rng[which].Get(addr)
230	if !ok {
231		return nil, false
232	}
233	e, err := wire.DecodeRngEntry(v)
234	return e, err == nil
235}