protocol/bbft.go

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