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         rollbackCh chan *rollbackMsg
  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, rollbackCh chan *rollbackMsg) *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                 rollbackCh:          rollbackCh,
  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 // LastFinalized return the block height and block hash which is finalized at last
  66 func (c *Casper) LastFinalized() (uint64, bc.Hash) {
  67         c.mu.RLock()
  68         defer c.mu.RUnlock()
  69
  70         root := c.tree.checkpoint
  71         return root.Height, root.Hash
  72 }
  73
  74 // LastJustified return the block height and block hash which is justified at last
  75 func (c *Casper) LastJustified() (uint64, bc.Hash) {
  76         c.mu.RLock()
  77         defer c.mu.RUnlock()
  78
  79         return lastJustified(c.tree)
  80 }
  81
  82 // Validators return the validators by specified block hash
  83 // 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
  84 func (c *Casper) Validators(blockHash *bc.Hash) (map[string]*state.Validator, error) {
  85         checkpoint, err := c.parentCheckpoint(blockHash)
  86         if err != nil {
  87                 return nil, err
  88         }
  89
  90         return checkpoint.Validators(), nil
  91 }
  92
  93 func (c *Casper) parentCheckpoint(blockHash *bc.Hash) (*state.Checkpoint, error) {
  94         hash, err := c.parentCheckpointHash(blockHash)
  95         if err != nil {
  96                 return nil, err
  97         }
  98
  99         return c.store.GetCheckpoint(hash)
 100 }
 101
 102 func (c *Casper) parentCheckpointByPrevHash(prevBlockHash *bc.Hash) (*state.Checkpoint, error) {
 103         hash, err := c.parentCheckpointHashByPrevHash(prevBlockHash)
 104         if err != nil {
 105                 return nil, err
 106         }
 107
 108         return c.store.GetCheckpoint(hash)
 109 }
 110
 111 // EvilValidator represent a validator who broadcast two distinct verification that violate the commandment
 112 type EvilValidator struct {
 113         PubKey string
 114         V1     *Verification
 115         V2     *Verification
 116 }
 117
 118 // EvilValidators return all evil validators
 119 func (c *Casper) EvilValidators() []*EvilValidator {
 120         c.mu.RLock()
 121         defer c.mu.RUnlock()
 122
 123         var validators []*EvilValidator
 124         for pubKey, verifications := range c.evilValidators {
 125                 validators = append(validators, &EvilValidator{
 126                         PubKey: pubKey,
 127                         V1:     verifications[0],
 128                         V2:     verifications[1],
 129                 })
 130         }
 131         return validators
 132 }
 133
 134 func (c *Casper) bestChain() bc.Hash {
 135         // root is init justified
 136         root := c.tree.checkpoint
 137         _, bestHash, _ := chainOfMaxJustifiedHeight(c.tree, root.Height)
 138         return bestHash
 139 }
 140
 141 func lastJustified(node *treeNode) (uint64, bc.Hash) {
 142         lastJustifiedHeight, lastJustifiedHash := uint64(0), bc.Hash{}
 143         if node.checkpoint.Status == state.Justified {
 144                 lastJustifiedHeight, lastJustifiedHash = node.checkpoint.Height, node.checkpoint.Hash
 145         }
 146
 147         for _, child := range node.children {
 148                 if justifiedHeight, justifiedHash := lastJustified(child); justifiedHeight > lastJustifiedHeight {
 149                         lastJustifiedHeight, lastJustifiedHash = justifiedHeight, justifiedHash
 150                 }
 151         }
 152         return lastJustifiedHeight, lastJustifiedHash
 153 }
 154
 155 // justifiedHeight is the max justified height of checkpoint from node to root
 156 func chainOfMaxJustifiedHeight(node *treeNode, justifiedHeight uint64) (uint64, bc.Hash, uint64) {
 157         checkpoint := node.checkpoint
 158         if checkpoint.Status == state.Justified {
 159                 justifiedHeight = checkpoint.Height
 160         }
 161
 162         bestHeight, bestHash, maxJustifiedHeight := checkpoint.Height, checkpoint.Hash, justifiedHeight
 163         for _, child := range node.children {
 164                 if height, hash, justified := chainOfMaxJustifiedHeight(child, justifiedHeight); justified > maxJustifiedHeight || height > bestHeight {
 165                         bestHeight, bestHash, maxJustifiedHeight = height, hash, justified
 166                 }
 167         }
 168         return bestHeight, bestHash, maxJustifiedHeight
 169 }
 170
 171 func (c *Casper) parentCheckpointHash(blockHash *bc.Hash) (*bc.Hash, error) {
 172         if data, ok := c.prevCheckpointCache.Get(*blockHash); ok {
 173                 return data.(*bc.Hash), nil
 174         }
 175
 176         block, err := c.store.GetBlockHeader(blockHash)
 177         if err != nil {
 178                 return nil, err
 179         }
 180
 181         result, err := c.parentCheckpointHashByPrevHash(&block.PreviousBlockHash)
 182         if err != nil {
 183                 return nil, err
 184         }
 185
 186         c.prevCheckpointCache.Add(*blockHash, result)
 187         return result, nil
 188 }
 189
 190 func (c *Casper) parentCheckpointHashByPrevHash(prevBlockHash *bc.Hash) (*bc.Hash, error) {
 191         prevHash := prevBlockHash
 192         for {
 193                 prevBlock, err := c.store.GetBlockHeader(prevHash)
 194                 if err != nil {
 195                         return nil, err
 196                 }
 197
 198                 if prevBlock.Height%state.BlocksOfEpoch == 0 {
 199                         c.prevCheckpointCache.Add(*prevBlockHash, prevHash)
 200                         return prevHash, nil
 201                 }
 202
 203                 if data, ok := c.prevCheckpointCache.Get(*prevHash); ok {
 204                         c.prevCheckpointCache.Add(*prevBlockHash, data)
 205                         return data.(*bc.Hash), nil
 206                 }
 207
 208                 prevHash = &prevBlock.PreviousBlockHash
 209         }
 210 }