path: root/consensus/clique/snapshot.go

// 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"

    "github.com/dexon-foundation/dexon/common"
    "github.com/dexon-foundation/dexon/core/types"
    "github.com/dexon-foundation/dexon/ethdb"
    "github.com/dexon-foundation/dexon/params"
    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()

    for _, 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)
        }
    }
    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)
}