protocol/casper.go

   1 package protocol
   2
   3 import (
   4         "sync"
   5
   6         log "github.com/sirupsen/logrus"
   7
   8         "github.com/bytom/bytom/common"
   9         "github.com/bytom/bytom/errors"
  10         "github.com/bytom/bytom/protocol/bc"
  11         "github.com/bytom/bytom/protocol/state"
  12 )
  13
  14 var (
  15         errPubKeyIsNotValidator     = errors.New("pub key is not in validators of target checkpoint")
  16         errVoteToGrowingCheckpoint  = errors.New("validator publish vote to growing checkpoint")
  17         errVoteToSameCheckpoint     = errors.New("source height and target height in verification is equals")
  18         errSameHeightInVerification = errors.New("validator publish two distinct votes for the same target height")
  19         errSpanHeightInVerification = errors.New("validator publish vote within the span of its other votes")
  20         errVoteToNonValidator       = errors.New("pubKey of vote is not validator")
  21         errGuarantyLessThanMinimum  = errors.New("guaranty less than minimum")
  22         errOverflow                 = errors.New("arithmetic overflow/underflow")
  23 )
  24
  25 const minGuaranty = 1E14
  26
  27 // Casper is BFT based proof of stack consensus algorithm, it provides safety and liveness in theory,
  28 // it's design mainly refers to https://github.com/ethereum/research/blob/master/papers/casper-basics/casper_basics.pdf
  29 type Casper struct {
  30         mu               sync.RWMutex
  31         tree             *treeNode
  32         rollbackNotifyCh chan bc.Hash
  33         newEpochCh       chan bc.Hash
  34         store            Store
  35         // pubKey -> conflicting verifications
  36         evilValidators map[string][]*Verification
  37         // block hash -> previous checkpoint hash
  38         prevCheckpointCache *common.Cache
  39         // block hash + pubKey -> verification
  40         verificationCache *common.Cache
  41 }
  42
  43 // NewCasper create a new instance of Casper
  44 // argument checkpoints load the checkpoints from leveldb
  45 // the first element of checkpoints must genesis checkpoint or the last finalized checkpoint in order to reduce memory space
  46 // the others must be successors of first one
  47 func NewCasper(store Store, checkpoints []*state.Checkpoint, rollbackNotifyCh chan bc.Hash) *Casper {
  48         if checkpoints[0].Height != 0 && checkpoints[0].Status != state.Finalized {
  49                 log.Panic("first element of checkpoints must genesis or in finalized status")
  50         }
  51
  52         casper := &Casper{
  53                 tree:                  makeTree(checkpoints[0], checkpoints[1:]),
  54                 rollbackNotifyCh:      rollbackNotifyCh,
  55                 newEpochCh:            make(chan bc.Hash),
  56                 store:                 store,
  57                 evilValidators:        make(map[string][]*Verification),
  58                 prevCheckpointCache:   common.NewCache(1024),
  59                 verificationCache:     common.NewCache(1024),
  60         }
  61         go casper.authVerificationLoop()
  62         return casper
  63 }
  64
  65 // Best chain return the chain containing the justified checkpoint of the largest height
  66 func (c *Casper) BestChain() (uint64, bc.Hash) {
  67         c.mu.RLock()
  68         defer c.mu.RUnlock()
  69
  70         return c.bestChain()
  71 }
  72
  73 func (c *Casper) bestChain() (uint64, bc.Hash) {
  74         // root is init justified
  75         root := c.tree.checkpoint
  76         bestHeight, bestHash, _ := chainOfMaxJustifiedHeight(c.tree, root.Height)
  77         return bestHeight, bestHash
  78 }
  79
  80 // LastFinalized return the block height and block hash which is finalized ast last
  81 func (c *Casper) LastFinalized() (uint64, bc.Hash) {
  82         c.mu.RLock()
  83         defer c.mu.RUnlock()
  84
  85         root := c.tree.checkpoint
  86         return root.Height, root.Hash
  87 }
  88
  89 // Validators return the validators by specified block hash
  90 // e.g. if the block num of epoch is 100, and the block height corresponding to the block hash is 130, then will return the voting results of height in 0~100
  91 func (c *Casper) Validators(blockHash *bc.Hash) (map[string]*state.Validator, error) {
  92         checkpoint, err := c.prevCheckpoint(blockHash)
  93         if err != nil {
  94                 return nil, err
  95         }
  96
  97         return checkpoint.Validators(), nil
  98 }
  99
 100 func (c *Casper) prevCheckpoint(blockHash *bc.Hash) (*state.Checkpoint, error) {
 101         hash, err := c.prevCheckpointHash(blockHash)
 102         if err != nil {
 103                 return nil, err
 104         }
 105
 106         return c.store.GetCheckpoint(hash)
 107 }
 108
 109 func (c *Casper) prevCheckpointByPrevHash(prevBlockHash *bc.Hash) (*state.Checkpoint, error) {
 110         hash, err := c.prevCheckpointHashByPrevHash(prevBlockHash)
 111         if err != nil {
 112                 return nil, err
 113         }
 114
 115         return c.store.GetCheckpoint(hash)
 116 }
 117
 118 // EvilValidator represent a validator who broadcast two distinct verification that violate the commandment
 119 type EvilValidator struct {
 120         PubKey string
 121         V1     *Verification
 122         V2     *Verification
 123 }
 124
 125 // EvilValidators return all evil validators
 126 func (c *Casper) EvilValidators() []*EvilValidator {
 127         c.mu.RLock()
 128         defer c.mu.RUnlock()
 129
 130         var validators []*EvilValidator
 131         for pubKey, verifications := range c.evilValidators {
 132                 validators = append(validators, &EvilValidator{
 133                         PubKey: pubKey,
 134                         V1:     verifications[0],
 135                         V2:     verifications[1],
 136                 })
 137         }
 138         return validators
 139 }
 140
 141 // justifiedHeight is the max justified height of checkpoint from node to root
 142 func chainOfMaxJustifiedHeight(node *treeNode, justifiedHeight uint64) (uint64, bc.Hash, uint64) {
 143         checkpoint := node.checkpoint
 144         if checkpoint.Status == state.Justified {
 145                 justifiedHeight = checkpoint.Height
 146         }
 147
 148         bestHeight, bestHash, maxJustifiedHeight := checkpoint.Height, checkpoint.Hash, justifiedHeight
 149         for _, child := range node.children {
 150                 if height, hash, justified := chainOfMaxJustifiedHeight(child, justifiedHeight); justified >= maxJustifiedHeight {
 151                         bestHeight, bestHash, maxJustifiedHeight = height, hash, justified
 152                 }
 153         }
 154         return bestHeight, bestHash, maxJustifiedHeight
 155 }
 156
 157 func (c *Casper) prevCheckpointHash(blockHash *bc.Hash) (*bc.Hash, error) {
 158         if data, ok := c.prevCheckpointCache.Get(*blockHash); ok {
 159                 return data.(*bc.Hash), nil
 160         }
 161
 162         block, err := c.store.GetBlockHeader(blockHash)
 163         if err != nil {
 164                 return nil, err
 165         }
 166
 167         result, err := c.prevCheckpointHashByPrevHash(&block.PreviousBlockHash)
 168         if err != nil {
 169                 return nil, err
 170         }
 171
 172         c.prevCheckpointCache.Add(*blockHash, result)
 173         return result, nil
 174 }
 175
 176 func (c *Casper) prevCheckpointHashByPrevHash(prevBlockHash *bc.Hash) (*bc.Hash, error) {
 177         prevHash := prevBlockHash
 178         for {
 179                 prevBlock, err := c.store.GetBlockHeader(prevHash)
 180                 if err != nil {
 181                         return nil, err
 182                 }
 183
 184                 if prevBlock.Height%state.BlocksOfEpoch == 0 {
 185                         c.prevCheckpointCache.Add(*prevBlockHash, prevHash)
 186                         return prevHash, nil
 187                 }
 188
 189                 if data, ok := c.prevCheckpointCache.Get(*prevHash); ok {
 190                         c.prevCheckpointCache.Add(*prevBlockHash, data)
 191                         return data.(*bc.Hash), nil
 192                 }
 193
 194                 prevHash = &prevBlock.PreviousBlockHash
 195         }
 196 }