protocol/bbft.go

   1 package protocol
   2
   3 import (
   4         "encoding/hex"
   5         "fmt"
   6         "time"
   7
   8         "github.com/golang/groupcache/lru"
   9         log "github.com/sirupsen/logrus"
  10
  11         "github.com/vapor/crypto/ed25519"
  12         "github.com/vapor/crypto/ed25519/chainkd"
  13         "github.com/vapor/errors"
  14         "github.com/vapor/event"
  15         "github.com/vapor/math/checked"
  16         "github.com/vapor/protocol/bc"
  17         "github.com/vapor/protocol/bc/types"
  18         "github.com/vapor/protocol/state"
  19 )
  20
  21 const (
  22         maxSignatureCacheSize = 10000
  23 )
  24
  25 var (
  26         errVotingOperationOverFlow = errors.New("voting operation result overflow")
  27         errDoubleSignBlock         = errors.New("the consensus is double sign in same height of different block")
  28         errInvalidSignature        = errors.New("the signature of block is invalid")
  29 )
  30
  31 type bbft struct {
  32         consensusNodeManager *consensusNodeManager
  33         orphanManage         *OrphanManage
  34         signatureCache       *lru.Cache
  35         eventDispatcher      *event.Dispatcher
  36 }
  37
  38 func newBbft(store Store, blockIndex *state.BlockIndex, orphanManage *OrphanManage, eventDispatcher *event.Dispatcher) *bbft {
  39         return &bbft{
  40                 orphanManage:         orphanManage,
  41                 consensusNodeManager: newConsensusNodeManager(store, blockIndex),
  42                 signatureCache:       lru.New(maxSignatureCacheSize),
  43                 eventDispatcher:      eventDispatcher,
  44         }
  45 }
  46
  47 // IsConsensusPubkey determine whether a public key is a consensus node at a specified height
  48 func (b *bbft) IsConsensusPubkey(height uint64, pubkey []byte) (bool, error) {
  49         node, err := b.consensusNodeManager.getConsensusNode(height, hex.EncodeToString(pubkey))
  50         if err != nil && err != errNotFoundConsensusNode {
  51                 return false, err
  52         }
  53         return node != nil, nil
  54 }
  55
  56 func (b *bbft) isIrreversible(block *types.Block) bool {
  57         signNum, err := b.validateSign(block)
  58         if err != nil {
  59                 return false
  60         }
  61
  62         return signNum > (numOfConsensusNode * 2 / 3)
  63 }
  64
  65 // NextLeaderTime returns the start time of the specified public key as the next leader node
  66 func (b *bbft) NextLeaderTime(pubkey []byte, bestBlockTimestamp, bestBlockHeight uint64) (*time.Time, error) {
  67         return b.consensusNodeManager.nextLeaderTime(pubkey, bestBlockTimestamp, bestBlockHeight)
  68 }
  69
  70 func (b *bbft) ApplyBlock(voteResultMap map[uint64]*state.VoteResult, block *types.Block) (err error) {
  71         voteSeq := block.Height / roundVoteBlockNums
  72         voteResult := voteResultMap[voteSeq]
  73
  74         if voteResult == nil {
  75                 store := b.consensusNodeManager.store
  76                 voteResult, err = store.GetVoteResult(voteSeq)
  77                 if err != nil && err != ErrNotFoundVoteResult {
  78                         return err
  79                 }
  80         }
  81
  82         if voteResult == nil {
  83                 voteResult = &state.VoteResult{
  84                         Seq:             voteSeq,
  85                         NumOfVote:       make(map[string]uint64),
  86                         LastBlockHeight: block.Height,
  87                 }
  88         }
  89
  90         voteResultMap[voteSeq] = voteResult
  91
  92         if voteResult.LastBlockHeight+1 != block.Height {
  93                 return errors.New("bbft append block error, the block height is not equals last block height plus 1 of vote result")
  94         }
  95
  96         for _, tx := range block.Transactions {
  97                 for _, input := range tx.Inputs {
  98                         unVoteInput, ok := input.TypedInput.(*types.UnvoteInput)
  99                         if !ok {
 100                                 continue
 101                         }
 102
 103                         pubkey := hex.EncodeToString(unVoteInput.Vote)
 104                         voteResult.NumOfVote[pubkey], ok = checked.SubUint64(voteResult.NumOfVote[pubkey], unVoteInput.Amount)
 105                         if !ok {
 106                                 return errVotingOperationOverFlow
 107                         }
 108                 }
 109                 for _, output := range tx.Outputs {
 110                         voteOutput, ok := output.TypedOutput.(*types.VoteTxOutput)
 111                         if !ok {
 112                                 continue
 113                         }
 114
 115                         pubkey := hex.EncodeToString(voteOutput.Vote)
 116                         voteResult.NumOfVote[pubkey], ok = checked.AddUint64(voteResult.NumOfVote[pubkey], voteOutput.Amount)
 117                         if !ok {
 118                                 return errVotingOperationOverFlow
 119                         }
 120                 }
 121         }
 122
 123         voteResult.LastBlockHeight++
 124         voteResult.Finalized = (block.Height+1)%roundVoteBlockNums == 0
 125         return nil
 126 }
 127
 128 func (b *bbft) DetachBlock(voteResultMap map[uint64]*state.VoteResult, block *types.Block) error {
 129         voteSeq := block.Height / roundVoteBlockNums
 130         voteResult := voteResultMap[voteSeq]
 131
 132         if voteResult == nil {
 133                 store := b.consensusNodeManager.store
 134                 voteResult, err := store.GetVoteResult(voteSeq)
 135                 if err != nil {
 136                         return err
 137                 }
 138                 voteResultMap[voteSeq] = voteResult
 139         }
 140
 141         if voteResult.LastBlockHeight != block.Height {
 142                 return errors.New("bbft detach block error, the block height is not equals last block height of vote result")
 143         }
 144
 145         for _, tx := range block.Transactions {
 146                 for _, input := range tx.Inputs {
 147                         unVoteInput, ok := input.TypedInput.(*types.UnvoteInput)
 148                         if !ok {
 149                                 continue
 150                         }
 151
 152                         pubkey := hex.EncodeToString(unVoteInput.Vote)
 153                         voteResult.NumOfVote[pubkey], ok = checked.AddUint64(voteResult.NumOfVote[pubkey], unVoteInput.Amount)
 154                         if !ok {
 155                                 return errVotingOperationOverFlow
 156                         }
 157                 }
 158                 for _, output := range tx.Outputs {
 159                         voteOutput, ok := output.TypedOutput.(*types.VoteTxOutput)
 160                         if !ok {
 161                                 continue
 162                         }
 163
 164                         pubkey := hex.EncodeToString(voteOutput.Vote)
 165                         voteResult.NumOfVote[pubkey], ok = checked.SubUint64(voteResult.NumOfVote[pubkey], voteOutput.Amount)
 166                         if !ok {
 167                                 return errVotingOperationOverFlow
 168                         }
 169                 }
 170         }
 171
 172         voteResult.LastBlockHeight--
 173         voteResult.Finalized = false
 174         return nil
 175 }
 176
 177 // ProcessBlockSignature process the received block signature messages
 178 // return once a block become irreversible, whether it's height greater than best block height
 179 // if so, the chain module must update status
 180 func (b *bbft) ProcessBlockSignature(signature, pubkey []byte, blockHeight uint64, blockHash *bc.Hash) (bool, error) {
 181         consensusNode, err := b.consensusNodeManager.getConsensusNode(blockHeight, hex.EncodeToString(pubkey))
 182         if err != nil {
 183                 return false, err
 184         }
 185
 186         if !ed25519.Verify(ed25519.PublicKey(pubkey), blockHash.Bytes(), signature) {
 187                 return false, errInvalidSignature
 188         }
 189
 190         isDoubleSign, err := b.checkDoubleSign(consensusNode.order, blockHeight, *blockHash)
 191         if err != nil {
 192                 return false, err
 193         }
 194
 195         if isDoubleSign {
 196                 log.WithFields(log.Fields{"module": logModule, "blockHash": blockHash.String(), "pubkey": pubkey}).Warn("the consensus node double sign the same height of different block")
 197                 return false, errDoubleSignBlock
 198         }
 199
 200         orphanBlock, ok := b.orphanManage.Get(blockHash)
 201         if ok {
 202                 orphanBlock.Witness[consensusNode.order] = signature
 203                 return false, nil
 204         }
 205
 206         block, err := b.consensusNodeManager.store.GetBlock(blockHash)
 207         if err != nil {
 208                 // block is not exist, save the signature
 209                 key := fmt.Sprintf("%s:%s", blockHash.String(), hex.EncodeToString(pubkey))
 210                 b.signatureCache.Add(key, signature)
 211                 return false, err
 212         }
 213
 214         if err := b.updateBlockSignature(block, consensusNode.order, signature); err != nil {
 215                 return false, err
 216         }
 217
 218         return b.isIrreversible(block) && blockHeight > b.consensusNodeManager.blockIndex.BestNode().Height, nil
 219 }
 220
 221 // ValidateBlock verify whether the block is valid
 222 func (b *bbft) ValidateBlock(block *types.Block) error {
 223         signNum, err := b.validateSign(block)
 224         if err != nil {
 225                 return err
 226         }
 227
 228         if signNum == 0 {
 229                 return errors.New("no valid signature")
 230         }
 231         return nil
 232 }
 233
 234 // validateSign verify the signatures of block, and return the number of correct signature
 235 // if some signature is invalid, they will be reset to nil
 236 // if the block has not the signature of blocker, it will return error
 237 func (b *bbft) validateSign(block *types.Block) (uint64, error) {
 238         var correctSignNum uint64
 239         consensusNodeMap, err := b.consensusNodeManager.getConsensusNodesByVoteResult(block.Height)
 240         if err != nil {
 241                 return 0, err
 242         }
 243
 244         hasBlockerSign := false
 245         for pubkey, node := range consensusNodeMap {
 246                 if len(block.Witness) <= int(node.order) {
 247                         continue
 248                 }
 249
 250                 blockHash := block.Hash()
 251                 if block.Witness[node.order] == nil {
 252                         key := fmt.Sprintf("%s:%s", blockHash.String(), pubkey)
 253                         signature, ok := b.signatureCache.Get(key)
 254                         if ok {
 255                                 block.Witness[node.order] = signature.([]byte)
 256                         }
 257                 }
 258
 259                 if ed25519.Verify(ed25519.PublicKey(pubkey), blockHash.Bytes(), block.Witness[node.order]) {
 260                         isDoubleSign, err := b.checkDoubleSign(node.order, block.Height, block.Hash())
 261                         if err != nil {
 262                                 return 0, err
 263                         }
 264
 265                         if isDoubleSign {
 266                                 log.WithFields(log.Fields{"module": logModule, "blockHash": blockHash.String(), "pubkey": pubkey}).Warn("the consensus node double sign the same height of different block")
 267                                 // Consensus node is signed twice with the same block height, discard the signature
 268                                 block.Witness[node.order] = nil
 269                         } else {
 270                                 correctSignNum++
 271                                 isBlocker, err := b.consensusNodeManager.isBlocker(block.Height, block.Timestamp, pubkey)
 272                                 if err != nil {
 273                                         return 0, err
 274                                 }
 275                                 if isBlocker {
 276                                         hasBlockerSign = true
 277                                 }
 278                         }
 279                 } else {
 280                         // discard the invalid signature
 281                         block.Witness[node.order] = nil
 282                 }
 283         }
 284         if !hasBlockerSign {
 285                 return 0, errors.New("the block has no signature of the blocker")
 286         }
 287         return correctSignNum, nil
 288 }
 289
 290 func (b *bbft) checkDoubleSign(nodeOrder, blockHeight uint64, blockHash bc.Hash) (bool, error) {
 291         blockNodes := b.consensusNodeManager.blockIndex.NodesByHeight(blockHeight)
 292         for _, blockNode := range blockNodes {
 293                 if blockNode.Hash == blockHash {
 294                         continue
 295                 }
 296                 if ok, err := blockNode.BlockWitness.Test(uint32(nodeOrder)); err != nil && ok {
 297                         block, err := b.consensusNodeManager.store.GetBlock(&blockHash)
 298                         if err != nil {
 299                                 return false, err
 300                         }
 301
 302                         // reset nil to discard signature
 303                         if err := b.updateBlockSignature(block, nodeOrder, nil); err != nil {
 304                                 return false, err
 305                         }
 306                 }
 307         }
 308         return false, nil
 309 }
 310
 311 // SignBlock signing the block if current node is consensus node
 312 func (b *bbft) SignBlock(block *types.Block) ([]byte, error) {
 313         var xprv chainkd.XPrv
 314         xpub := [64]byte(xprv.XPub())
 315         node, err := b.consensusNodeManager.getConsensusNode(block.Height, hex.EncodeToString(xpub[:]))
 316         if err != nil && err != errNotFoundConsensusNode {
 317                 return nil, err
 318         }
 319
 320         if node == nil {
 321                 return nil, nil
 322         }
 323
 324         signature := xprv.Sign(block.Hash().Bytes())
 325         block.Witness[node.order] = signature
 326         return signature, nil
 327 }
 328
 329 // UpdateConsensusNodes used to update consensus node after each round of voting
 330 func (b *bbft) UpdateConsensusNodes(blockHeight uint64) error {
 331         return b.consensusNodeManager.updateConsensusNodes(blockHeight)
 332 }
 333
 334 func (b *bbft) updateBlockSignature(block *types.Block, nodeOrder uint64, signature []byte) error {
 335         blockHash := block.Hash()
 336         blockNode := b.consensusNodeManager.blockIndex.GetNode(&blockHash)
 337
 338         if len(signature) != 0 {
 339                 if err := blockNode.BlockWitness.Set(uint32(nodeOrder)); err != nil {
 340                         return err
 341                 }
 342         } else {
 343                 if err := blockNode.BlockWitness.Clean(uint32(nodeOrder)); err != nil {
 344                         return err
 345                 }
 346         }
 347
 348         block.Witness[nodeOrder] = signature
 349         txStatus, err := b.consensusNodeManager.store.GetTransactionStatus(&blockHash)
 350         if err != nil {
 351                 return err
 352         }
 353
 354         return b.consensusNodeManager.store.SaveBlock(block, txStatus)
 355 }