protocol/consensus/casper.go

   1 package consensus
   2
   3 import (
   4         "encoding/hex"
   5         "sync"
   6
   7         "github.com/bytom/bytom/errors"
   8         "github.com/bytom/bytom/math/checked"
   9         "github.com/bytom/bytom/protocol"
  10         "github.com/bytom/bytom/protocol/bc"
  11         "github.com/bytom/bytom/protocol/bc/types"
  12         "github.com/bytom/bytom/protocol/state"
  13 )
  14
  15 var (
  16         errVerifySignature          = errors.New("signature of verification message is invalid")
  17         errPubKeyIsNotValidator     = errors.New("pub key is not in validators of target checkpoint")
  18         errVoteToGrowingCheckpoint  = errors.New("validator publish vote to growing checkpoint")
  19         errSameHeightInVerification = errors.New("validator publish two distinct votes for the same target height")
  20         errSpanHeightInVerification = errors.New("validator publish vote within the span of its other votes")
  21         errVoteToNonValidator       = errors.New("pubKey of vote is not validator")
  22         errGuarantyLessThanMinimum  = errors.New("guaranty less than minimum")
  23         errOverflow                 = errors.New("arithmetic overflow/underflow")
  24 )
  25
  26 const minGuaranty = 1E14
  27
  28 // Casper is BFT based proof of stack consensus algorithm, it provides safety and liveness in theory,
  29 // it's design mainly refers to https://github.com/ethereum/research/blob/master/papers/casper-basics/casper_basics.pdf
  30 type Casper struct {
  31         mu               sync.RWMutex
  32         tree             *treeNode
  33         rollbackNotifyCh chan bc.Hash
  34         store            protocol.Store
  35
  36         // pubKey -> conflicting verifications
  37         evilValidators map[string][]*Verification
  38 }
  39
  40 // Best chain return the chain containing the justified checkpoint of the largest height
  41 func (c *Casper) BestChain() (uint64, bc.Hash) {
  42         c.mu.RLock()
  43         defer c.mu.RUnlock()
  44
  45         // root is init justified
  46         root := c.tree.checkpoint
  47         bestHeight, bestHash, _ := chainOfMaxJustifiedHeight(c.tree, root.Height)
  48         return bestHeight, bestHash
  49 }
  50
  51 // Validators return the validators by specified block hash
  52 // 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
  53 func (c *Casper) Validators(blockHash *bc.Hash) ([]*state.Validator, error) {
  54         hash, err := c.prevCheckpointHash(blockHash)
  55         if err != nil {
  56                 return nil, err
  57         }
  58
  59         c.mu.RLock()
  60         defer c.mu.RUnlock()
  61
  62         checkpoint, err := c.store.GetCheckpoint(hash)
  63         if err != nil {
  64                 return nil, err
  65         }
  66
  67         return checkpoint.Validators(), nil
  68 }
  69
  70 // AuthVerification verify whether the Verification is legal.
  71 // the status of source checkpoint must justified, and an individual validator ν must not publish two distinct Verification
  72 // ⟨ν,s1,t1,h(s1),h(t1)⟩ and ⟨ν,s2,t2,h(s2),h(t2)⟩, such that either:
  73 // h(t1) = h(t2) OR h(s1) < h(s2) < h(t2) < h(t1)
  74 func (c *Casper) AuthVerification(v *Verification) error {
  75         if err := v.VerifySignature(); err != nil {
  76                 return err
  77         }
  78
  79         c.mu.Lock()
  80         defer c.mu.Unlock()
  81
  82         target, err := c.store.GetCheckpoint(&v.TargetHash)
  83         if err != nil {
  84                 return err
  85         }
  86
  87         // root of tree is the last finalized checkpoint
  88         if target.Height < c.tree.checkpoint.Height {
  89                 // discard the verification message which height of target less than height of last finalized checkpoint
  90                 // is for simplify check the vote within the span of its other votes
  91                 return nil
  92         }
  93
  94         source, err := c.store.GetCheckpoint(&v.SourceHash)
  95         if err != nil {
  96                 // the synchronization block is later than the arrival of the verification message
  97                 return err
  98         }
  99
 100         if source.Status == state.Growing || target.Status == state.Growing {
 101                 return errVoteToGrowingCheckpoint
 102         }
 103
 104         if !target.ContainsValidator(v.PubKey) {
 105                 return errPubKeyIsNotValidator
 106         }
 107
 108         if err := c.verifyVerification(v); err != nil {
 109                 return err
 110         }
 111
 112         supLink := target.AddSupLink(v.SourceHeight, v.SourceHash, v.PubKey, v.Signature)
 113         if source.Status == state.Justified && supLink.Confirmed() {
 114                 c.setJustified(target)
 115                 // must direct child
 116                 if target.PrevHash == source.Hash {
 117                         if err := c.setFinalized(source); err != nil {
 118                                 return err
 119                         }
 120                 }
 121         }
 122         return c.store.SaveCheckpoints(source, target)
 123 }
 124
 125 func (c *Casper) setJustified(checkpoint *state.Checkpoint) {
 126         _, oldBestHash := c.BestChain()
 127         checkpoint.Status = state.Justified
 128         if _, bestHash := c.BestChain(); bestHash != oldBestHash {
 129                 c.rollbackNotifyCh <- bestHash
 130         }
 131 }
 132
 133 func (c *Casper) setFinalized(checkpoint *state.Checkpoint) error {
 134         checkpoint.Status = state.Finalized
 135         newRoot, err := c.tree.nodeByHash(checkpoint.Hash)
 136         if err != nil {
 137                 return err
 138         }
 139
 140         c.tree = newRoot
 141         return nil
 142 }
 143
 144 // EvilValidator represent a validator who broadcast two distinct verification that violate the commandment
 145 type EvilValidator struct {
 146         PubKey string
 147         V1     *Verification
 148         V2     *Verification
 149 }
 150
 151 // EvilValidators return all evil validators
 152 func (c *Casper) EvilValidators() []*EvilValidator {
 153         c.mu.RLock()
 154         defer c.mu.RUnlock()
 155
 156         var validators []*EvilValidator
 157         for pubKey, verifications := range c.evilValidators {
 158                 validators = append(validators, &EvilValidator{
 159                         PubKey: pubKey,
 160                         V1:     verifications[0],
 161                         V2:     verifications[1],
 162                 })
 163         }
 164         return validators
 165 }
 166
 167 // ApplyBlock used to receive a new block from upper layer, it provides idempotence
 168 // and parse the vote and mortgage from the transactions, then save to the checkpoint
 169 // the tree of checkpoint will grow with the arrival of new blocks
 170 func (c *Casper) ApplyBlock(block *types.Block) error {
 171         c.mu.Lock()
 172         defer c.mu.Unlock()
 173
 174         if _, err := c.tree.nodeByHash(block.Hash()); err == nil {
 175                 // already processed
 176                 return nil
 177         }
 178
 179         checkpoint, err := c.applyBlockToCheckpoint(block)
 180         if err != nil {
 181                 return errors.Wrap(err, "apply block to checkpoint")
 182         }
 183
 184         for _, tx := range block.Transactions {
 185                 for _, input := range tx.Inputs {
 186                         if vetoInput, ok := input.TypedInput.(*types.VetoInput); ok {
 187                                 if err := processVeto(vetoInput, checkpoint); err != nil {
 188                                         return err
 189                                 }
 190                         }
 191
 192                         if isGuarantyProgram(input.ControlProgram()) {
 193                                 if err := processWithdrawal(decodeGuarantyArgs(input.ControlProgram()), checkpoint); err != nil {
 194                                         return err
 195                                 }
 196                         }
 197                 }
 198
 199                 for _, output := range tx.Outputs {
 200                         if _, ok := output.TypedOutput.(*types.VoteOutput); ok {
 201                                 if err := processVote(output, checkpoint); err != nil {
 202                                         return err
 203                                 }
 204                         }
 205
 206                         if isGuarantyProgram(output.ControlProgram) {
 207                                 if err := processGuaranty(decodeGuarantyArgs(output.ControlProgram), checkpoint); err != nil {
 208                                         return err
 209                                 }
 210                         }
 211                 }
 212         }
 213         return c.store.SaveCheckpoints(checkpoint)
 214 }
 215
 216 type guarantyArgs struct {
 217         Amount uint64
 218         PubKey []byte
 219 }
 220
 221 func isGuarantyProgram(program []byte) bool {
 222         return false
 223 }
 224
 225 func decodeGuarantyArgs(program []byte) *guarantyArgs {
 226         return nil
 227 }
 228
 229 func processWithdrawal(guarantyArgs *guarantyArgs, checkpoint *state.Checkpoint) error {
 230         pubKey := hex.EncodeToString(guarantyArgs.PubKey)
 231         guarantyNum := checkpoint.Guaranties[pubKey]
 232         guarantyNum, ok := checked.SubUint64(guarantyNum, guarantyArgs.Amount)
 233         if !ok {
 234                 return errOverflow
 235         }
 236
 237         checkpoint.Guaranties[pubKey] = guarantyNum
 238         // TODO delete the evil validator when receive the confiscate transaction
 239         return nil
 240 }
 241
 242 func processGuaranty(guarantyArgs *guarantyArgs, checkpoint *state.Checkpoint) error {
 243         if guarantyArgs.Amount < minGuaranty {
 244                 return errGuarantyLessThanMinimum
 245         }
 246
 247         pubKey := hex.EncodeToString(guarantyArgs.PubKey)
 248         guarantyNum := checkpoint.Guaranties[pubKey]
 249         guarantyNum, ok := checked.AddUint64(guarantyNum, guarantyArgs.Amount)
 250         if !ok {
 251                 return errOverflow
 252         }
 253
 254         checkpoint.Guaranties[pubKey] = guarantyNum
 255         return nil
 256 }
 257
 258 func processVeto(input *types.VetoInput, checkpoint *state.Checkpoint) error {
 259         pubKey := hex.EncodeToString(input.Vote)
 260         voteNum := checkpoint.Votes[pubKey]
 261         voteNum, ok := checked.SubUint64(voteNum, input.Amount)
 262         if !ok {
 263                 return errOverflow
 264         }
 265
 266         checkpoint.Votes[pubKey] = voteNum
 267         return nil
 268 }
 269
 270 func processVote(output *types.TxOutput, checkpoint *state.Checkpoint) error {
 271         voteOutput := output.TypedOutput.(*types.VoteOutput)
 272         pubKey := hex.EncodeToString(voteOutput.Vote)
 273         if checkpoint.Guaranties[pubKey] < minGuaranty {
 274                 return errVoteToNonValidator
 275         }
 276
 277         voteNum := checkpoint.Votes[pubKey]
 278         voteNum, ok := checked.AddUint64(voteNum, output.Amount)
 279         if !ok {
 280                 return errOverflow
 281         }
 282
 283         checkpoint.Votes[pubKey] = voteNum
 284         return nil
 285 }
 286
 287 func (c *Casper) applyBlockToCheckpoint(block *types.Block) (*state.Checkpoint, error) {
 288         node, err := c.tree.nodeByHash(block.PreviousBlockHash)
 289         if err != nil {
 290                 return nil, err
 291         }
 292
 293         checkpoint := node.checkpoint
 294         if mod := block.Height % state.BlocksOfEpoch; mod == 1 {
 295                 parent := checkpoint
 296                 checkpoint = &state.Checkpoint{
 297                         PrevHash:       parent.Hash,
 298                         StartTimestamp: block.Timestamp,
 299                         Status:         state.Growing,
 300                         Votes:          make(map[string]uint64),
 301                         Guaranties:     make(map[string]uint64),
 302                 }
 303                 node.children = append(node.children, &treeNode{checkpoint: checkpoint})
 304         } else if mod == 0 {
 305                 checkpoint.Status = state.Unverified
 306         }
 307
 308         checkpoint.Height = block.Height
 309         checkpoint.Hash = block.Hash()
 310         return checkpoint, nil
 311 }
 312
 313 func (c *Casper) verifyVerification(v *Verification) error {
 314         if err := c.verifySameHeight(v); err != nil {
 315                 return err
 316         }
 317
 318         return c.verifySpanHeight(v)
 319 }
 320
 321 // a validator must not publish two distinct votes for the same target height
 322 func (c *Casper) verifySameHeight(v *Verification) error {
 323         checkpoints, err := c.store.GetCheckpointsByHeight(v.TargetHeight)
 324         if err != nil {
 325                 return err
 326         }
 327
 328         for _, checkpoint := range checkpoints {
 329                 for _, supLink := range checkpoint.SupLinks {
 330                         if signature, ok := supLink.Signatures[v.PubKey]; ok {
 331                                 c.evilValidators[v.PubKey] = []*Verification{v, makeVerification(supLink, checkpoint, signature, v.PubKey)}
 332                                 return errSameHeightInVerification
 333                         }
 334                 }
 335         }
 336         return nil
 337 }
 338
 339 // a validator must not vote within the span of its other votes.
 340 func (c *Casper) verifySpanHeight(v *Verification) error {
 341         if c.tree.findOnlyOne(func(checkpoint *state.Checkpoint) bool {
 342                 if checkpoint.Height == v.TargetHeight {
 343                         return false
 344                 }
 345
 346                 for _, supLink := range checkpoint.SupLinks {
 347                         if signature, ok := supLink.Signatures[v.PubKey]; ok {
 348                                 if (checkpoint.Height < v.TargetHeight && supLink.SourceHeight > v.SourceHeight) ||
 349                                         (checkpoint.Height > v.TargetHeight && supLink.SourceHeight < v.SourceHeight) {
 350                                         c.evilValidators[v.PubKey] = []*Verification{v, makeVerification(supLink, checkpoint, signature, v.PubKey)}
 351                                         return true
 352                                 }
 353                         }
 354                 }
 355                 return false
 356         }) != nil {
 357                 return errSpanHeightInVerification
 358         }
 359         return nil
 360 }
 361
 362 func makeVerification(supLink *state.SupLink, checkpoint *state.Checkpoint, signature, pubKey string) *Verification {
 363         return &Verification{
 364                 SourceHash:   supLink.SourceHash,
 365                 TargetHash:   checkpoint.Hash,
 366                 SourceHeight: supLink.SourceHeight,
 367                 TargetHeight: checkpoint.Height,
 368                 Signature:    signature,
 369                 PubKey:       pubKey,
 370         }
 371 }
 372
 373 // justifiedHeight is the max justified height of checkpoint from node to root
 374 func chainOfMaxJustifiedHeight(node *treeNode, justifiedHeight uint64) (uint64, bc.Hash, uint64) {
 375         checkpoint := node.checkpoint
 376         if checkpoint.Status == state.Justified {
 377                 justifiedHeight = checkpoint.Height
 378         }
 379
 380         bestHeight, bestHash, maxJustifiedHeight := checkpoint.Height, checkpoint.Hash, justifiedHeight
 381         for _, child := range node.children {
 382                 if height, hash, justified := chainOfMaxJustifiedHeight(child, justifiedHeight); justified >= maxJustifiedHeight {
 383                         bestHeight, bestHash, maxJustifiedHeight = height, hash, justified
 384                 }
 385         }
 386         return bestHeight, bestHash, maxJustifiedHeight
 387 }
 388
 389 func (c *Casper) prevCheckpointHash(blockHash *bc.Hash) (*bc.Hash, error) {
 390         for {
 391                 block, err := c.store.GetBlockHeader(blockHash)
 392                 if err != nil {
 393                         return nil, err
 394                 }
 395
 396                 height := block.Height - 1
 397                 blockHash = &block.PreviousBlockHash
 398                 if height%state.BlocksOfEpoch == 0 {
 399                         return blockHash, nil
 400                 }
 401         }
 402 }