...

1 files changed, 326 insertions, 0 deletions

diff --git a/consensus/clique/snapshot.go b/consensus/clique/snapshot.go
new file mode 100644
index 0000000..6660c0f
--- /dev/null
+++ b/consensus/clique/snapshot.go
@@ -0,0 +1,326 @@
+// Copyright 2017 The go-ethereum Authors
+// This file is part of the go-ethereum library.
+//
+// The go-ethereum library is free software: you can redistribute it and/or modify
+// it under the terms of the GNU Lesser General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+//
+// The go-ethereum library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU Lesser General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
+
+package clique
+
+import (
+	"bytes"
+	"encoding/json"
+	"sort"
+	"time"
+
+	"github.com/ava-labs/coreth/core/types"
+	"github.com/ava-labs/coreth/params"
+	"github.com/ava-labs/go-ethereum/common"
+	"github.com/ava-labs/go-ethereum/ethdb"
+	"github.com/ava-labs/go-ethereum/log"
+	lru "github.com/hashicorp/golang-lru"
+)
+
+// Vote represents a single vote that an authorized signer made to modify the
+// list of authorizations.
+type Vote struct {
+	Signer    common.Address `json:"signer"`    // Authorized signer that cast this vote
+	Block     uint64         `json:"block"`     // Block number the vote was cast in (expire old votes)
+	Address   common.Address `json:"address"`   // Account being voted on to change its authorization
+	Authorize bool           `json:"authorize"` // Whether to authorize or deauthorize the voted account
+}
+
+// Tally is a simple vote tally to keep the current score of votes. Votes that
+// go against the proposal aren't counted since it's equivalent to not voting.
+type Tally struct {
+	Authorize bool `json:"authorize"` // Whether the vote is about authorizing or kicking someone
+	Votes     int  `json:"votes"`     // Number of votes until now wanting to pass the proposal
+}
+
+// Snapshot is the state of the authorization voting at a given point in time.
+type Snapshot struct {
+	config   *params.CliqueConfig // Consensus engine parameters to fine tune behavior
+	sigcache *lru.ARCCache        // Cache of recent block signatures to speed up ecrecover
+
+	Number  uint64                      `json:"number"`  // Block number where the snapshot was created
+	Hash    common.Hash                 `json:"hash"`    // Block hash where the snapshot was created
+	Signers map[common.Address]struct{} `json:"signers"` // Set of authorized signers at this moment
+	Recents map[uint64]common.Address   `json:"recents"` // Set of recent signers for spam protections
+	Votes   []*Vote                     `json:"votes"`   // List of votes cast in chronological order
+	Tally   map[common.Address]Tally    `json:"tally"`   // Current vote tally to avoid recalculating
+}
+
+// signersAscending implements the sort interface to allow sorting a list of addresses
+type signersAscending []common.Address
+
+func (s signersAscending) Len() int           { return len(s) }
+func (s signersAscending) Less(i, j int) bool { return bytes.Compare(s[i][:], s[j][:]) < 0 }
+func (s signersAscending) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
+
+// newSnapshot creates a new snapshot with the specified startup parameters. This
+// method does not initialize the set of recent signers, so only ever use if for
+// the genesis block.
+func newSnapshot(config *params.CliqueConfig, sigcache *lru.ARCCache, number uint64, hash common.Hash, signers []common.Address) *Snapshot {
+	snap := &Snapshot{
+		config:   config,
+		sigcache: sigcache,
+		Number:   number,
+		Hash:     hash,
+		Signers:  make(map[common.Address]struct{}),
+		Recents:  make(map[uint64]common.Address),
+		Tally:    make(map[common.Address]Tally),
+	}
+	for _, signer := range signers {
+		snap.Signers[signer] = struct{}{}
+	}
+	return snap
+}
+
+// loadSnapshot loads an existing snapshot from the database.
+func loadSnapshot(config *params.CliqueConfig, sigcache *lru.ARCCache, db ethdb.Database, hash common.Hash) (*Snapshot, error) {
+	blob, err := db.Get(append([]byte("clique-"), hash[:]...))
+	if err != nil {
+		return nil, err
+	}
+	snap := new(Snapshot)
+	if err := json.Unmarshal(blob, snap); err != nil {
+		return nil, err
+	}
+	snap.config = config
+	snap.sigcache = sigcache
+
+	return snap, nil
+}
+
+// store inserts the snapshot into the database.
+func (s *Snapshot) store(db ethdb.Database) error {
+	blob, err := json.Marshal(s)
+	if err != nil {
+		return err
+	}
+	return db.Put(append([]byte("clique-"), s.Hash[:]...), blob)
+}
+
+// copy creates a deep copy of the snapshot, though not the individual votes.
+func (s *Snapshot) copy() *Snapshot {
+	cpy := &Snapshot{
+		config:   s.config,
+		sigcache: s.sigcache,
+		Number:   s.Number,
+		Hash:     s.Hash,
+		Signers:  make(map[common.Address]struct{}),
+		Recents:  make(map[uint64]common.Address),
+		Votes:    make([]*Vote, len(s.Votes)),
+		Tally:    make(map[common.Address]Tally),
+	}
+	for signer := range s.Signers {
+		cpy.Signers[signer] = struct{}{}
+	}
+	for block, signer := range s.Recents {
+		cpy.Recents[block] = signer
+	}
+	for address, tally := range s.Tally {
+		cpy.Tally[address] = tally
+	}
+	copy(cpy.Votes, s.Votes)
+
+	return cpy
+}
+
+// validVote returns whether it makes sense to cast the specified vote in the
+// given snapshot context (e.g. don't try to add an already authorized signer).
+func (s *Snapshot) validVote(address common.Address, authorize bool) bool {
+	_, signer := s.Signers[address]
+	return (signer && !authorize) || (!signer && authorize)
+}
+
+// cast adds a new vote into the tally.
+func (s *Snapshot) cast(address common.Address, authorize bool) bool {
+	// Ensure the vote is meaningful
+	if !s.validVote(address, authorize) {
+		return false
+	}
+	// Cast the vote into an existing or new tally
+	if old, ok := s.Tally[address]; ok {
+		old.Votes++
+		s.Tally[address] = old
+	} else {
+		s.Tally[address] = Tally{Authorize: authorize, Votes: 1}
+	}
+	return true
+}
+
+// uncast removes a previously cast vote from the tally.
+func (s *Snapshot) uncast(address common.Address, authorize bool) bool {
+	// If there's no tally, it's a dangling vote, just drop
+	tally, ok := s.Tally[address]
+	if !ok {
+		return false
+	}
+	// Ensure we only revert counted votes
+	if tally.Authorize != authorize {
+		return false
+	}
+	// Otherwise revert the vote
+	if tally.Votes > 1 {
+		tally.Votes--
+		s.Tally[address] = tally
+	} else {
+		delete(s.Tally, address)
+	}
+	return true
+}
+
+// apply creates a new authorization snapshot by applying the given headers to
+// the original one.
+func (s *Snapshot) apply(headers []*types.Header) (*Snapshot, error) {
+	// Allow passing in no headers for cleaner code
+	if len(headers) == 0 {
+		return s, nil
+	}
+	// Sanity check that the headers can be applied
+	for i := 0; i < len(headers)-1; i++ {
+		if headers[i+1].Number.Uint64() != headers[i].Number.Uint64()+1 {
+			return nil, errInvalidVotingChain
+		}
+	}
+	if headers[0].Number.Uint64() != s.Number+1 {
+		return nil, errInvalidVotingChain
+	}
+	// Iterate through the headers and create a new snapshot
+	snap := s.copy()
+
+	var (
+		start  = time.Now()
+		logged = time.Now()
+	)
+	for i, header := range headers {
+		// Remove any votes on checkpoint blocks
+		number := header.Number.Uint64()
+		if number%s.config.Epoch == 0 {
+			snap.Votes = nil
+			snap.Tally = make(map[common.Address]Tally)
+		}
+		// Delete the oldest signer from the recent list to allow it signing again
+		if limit := uint64(len(snap.Signers)/2 + 1); number >= limit {
+			delete(snap.Recents, number-limit)
+		}
+		// Resolve the authorization key and check against signers
+		signer, err := ecrecover(header, s.sigcache)
+		if err != nil {
+			return nil, err
+		}
+		if _, ok := snap.Signers[signer]; !ok {
+			return nil, errUnauthorizedSigner
+		}
+		for _, recent := range snap.Recents {
+			if recent == signer {
+				return nil, errRecentlySigned
+			}
+		}
+		snap.Recents[number] = signer
+
+		// Header authorized, discard any previous votes from the signer
+		for i, vote := range snap.Votes {
+			if vote.Signer == signer && vote.Address == header.Coinbase {
+				// Uncast the vote from the cached tally
+				snap.uncast(vote.Address, vote.Authorize)
+
+				// Uncast the vote from the chronological list
+				snap.Votes = append(snap.Votes[:i], snap.Votes[i+1:]...)
+				break // only one vote allowed
+			}
+		}
+		// Tally up the new vote from the signer
+		var authorize bool
+		switch {
+		case bytes.Equal(header.Nonce[:], nonceAuthVote):
+			authorize = true
+		case bytes.Equal(header.Nonce[:], nonceDropVote):
+			authorize = false
+		default:
+			return nil, errInvalidVote
+		}
+		if snap.cast(header.Coinbase, authorize) {
+			snap.Votes = append(snap.Votes, &Vote{
+				Signer:    signer,
+				Block:     number,
+				Address:   header.Coinbase,
+				Authorize: authorize,
+			})
+		}
+		// If the vote passed, update the list of signers
+		if tally := snap.Tally[header.Coinbase]; tally.Votes > len(snap.Signers)/2 {
+			if tally.Authorize {
+				snap.Signers[header.Coinbase] = struct{}{}
+			} else {
+				delete(snap.Signers, header.Coinbase)
+
+				// Signer list shrunk, delete any leftover recent caches
+				if limit := uint64(len(snap.Signers)/2 + 1); number >= limit {
+					delete(snap.Recents, number-limit)
+				}
+				// Discard any previous votes the deauthorized signer cast
+				for i := 0; i < len(snap.Votes); i++ {
+					if snap.Votes[i].Signer == header.Coinbase {
+						// Uncast the vote from the cached tally
+						snap.uncast(snap.Votes[i].Address, snap.Votes[i].Authorize)
+
+						// Uncast the vote from the chronological list
+						snap.Votes = append(snap.Votes[:i], snap.Votes[i+1:]...)
+
+						i--
+					}
+				}
+			}
+			// Discard any previous votes around the just changed account
+			for i := 0; i < len(snap.Votes); i++ {
+				if snap.Votes[i].Address == header.Coinbase {
+					snap.Votes = append(snap.Votes[:i], snap.Votes[i+1:]...)
+					i--
+				}
+			}
+			delete(snap.Tally, header.Coinbase)
+		}
+		// If we're taking too much time (ecrecover), notify the user once a while
+		if time.Since(logged) > 8*time.Second {
+			log.Info("Reconstructing voting history", "processed", i, "total", len(headers), "elapsed", common.PrettyDuration(time.Since(start)))
+			logged = time.Now()
+		}
+	}
+	if time.Since(start) > 8*time.Second {
+		log.Info("Reconstructed voting history", "processed", len(headers), "elapsed", common.PrettyDuration(time.Since(start)))
+	}
+	snap.Number += uint64(len(headers))
+	snap.Hash = headers[len(headers)-1].Hash()
+
+	return snap, nil
+}
+
+// signers retrieves the list of authorized signers in ascending order.
+func (s *Snapshot) signers() []common.Address {
+	sigs := make([]common.Address, 0, len(s.Signers))
+	for sig := range s.Signers {
+		sigs = append(sigs, sig)
+	}
+	sort.Sort(signersAscending(sigs))
+	return sigs
+}
+
+// inturn returns if a signer at a given block height is in-turn or not.
+func (s *Snapshot) inturn(number uint64, signer common.Address) bool {
+	signers, offset := s.signers(), 0
+	for offset < len(signers) && signers[offset] != signer {
+		offset++
+	}
+	return (number % uint64(len(signers))) == uint64(offset)
+}