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