protocol/consensus_node_manager.go

   1 package protocol
   2
   3 import (
   4         "encoding/hex"
   5         "sort"
   6         "time"
   7
   8         "github.com/vapor/config"
   9         "github.com/vapor/errors"
  10         "github.com/vapor/math/checked"
  11         "github.com/vapor/protocol/bc"
  12         "github.com/vapor/protocol/bc/types"
  13         "github.com/vapor/protocol/state"
  14 )
  15
  16 const (
  17         NumOfConsensusNode = 21
  18         roundVoteBlockNums = 1000
  19
  20         // BlockTimeInterval indicate product one block per 500 milliseconds
  21         BlockTimeInterval = 500
  22         // BlockNumEachNode indicate product three blocks per node in succession
  23         BlockNumEachNode = 3
  24 )
  25
  26 var (
  27         errNotFoundConsensusNode = errors.New("can not found consensus node")
  28         errNotFoundBlockNode     = errors.New("can not find block node")
  29 )
  30
  31 type consensusNode struct {
  32         pubkey  string
  33         voteNum uint64
  34         order   uint64
  35 }
  36
  37 type consensusNodeSlice []*consensusNode
  38
  39 func (c consensusNodeSlice) Len() int           { return len(c) }
  40 func (c consensusNodeSlice) Less(i, j int) bool { return c[i].voteNum > c[j].voteNum }
  41 func (c consensusNodeSlice) Swap(i, j int)      { c[i], c[j] = c[j], c[i] }
  42
  43 type consensusNodeManager struct {
  44         store      Store
  45         blockIndex *state.BlockIndex
  46 }
  47
  48 func newConsensusNodeManager(store Store, blockIndex *state.BlockIndex) *consensusNodeManager {
  49         return &consensusNodeManager{
  50                 store:      store,
  51                 blockIndex: blockIndex,
  52         }
  53 }
  54
  55 func (c *consensusNodeManager) getConsensusNode(prevBlockHash *bc.Hash, pubkey string) (*consensusNode, error) {
  56         consensusNodeMap, err := c.getConsensusNodesByVoteResult(prevBlockHash)
  57         if err != nil {
  58                 return nil, err
  59         }
  60
  61         node, exist := consensusNodeMap[pubkey]
  62         if !exist {
  63                 return nil, errNotFoundConsensusNode
  64         }
  65         return node, nil
  66 }
  67
  68 func (c *consensusNodeManager) isBlocker(block *types.Block, pubKey string) (bool, error) {
  69         consensusNode, err := c.getConsensusNode(&block.PreviousBlockHash, pubKey)
  70         if err != nil && err != errNotFoundConsensusNode {
  71                 return false, err
  72         }
  73
  74         if consensusNode == nil {
  75                 return false, nil
  76         }
  77
  78         prevVoteRoundLastBlock, err := c.getPrevRoundVoteLastBlock(&block.PreviousBlockHash)
  79         if err != nil {
  80                 return false, err
  81         }
  82
  83         startTimestamp := prevVoteRoundLastBlock.Timestamp + BlockTimeInterval
  84
  85         begin := getLastBlockTimeInTimeRange(startTimestamp, block.Timestamp, consensusNode.order)
  86         end := begin + BlockNumEachNode*BlockTimeInterval
  87         return block.Timestamp >= begin && block.Timestamp < end, nil
  88 }
  89
  90 func (c *consensusNodeManager) nextLeaderTimeRange(pubkey []byte, bestBlockHash *bc.Hash) (uint64, uint64, error) {
  91         bestBlockNode := c.blockIndex.GetNode(bestBlockHash)
  92         if bestBlockNode == nil {
  93                 return 0, 0, errNotFoundBlockNode
  94         }
  95
  96         consensusNode, err := c.getConsensusNode(&bestBlockNode.Parent.Hash, hex.EncodeToString(pubkey))
  97         if err != nil {
  98                 return 0, 0, err
  99         }
 100
 101         prevRoundLastBlock, err := c.getPrevRoundVoteLastBlock(&bestBlockNode.Parent.Hash)
 102         if err != nil {
 103                 return 0, 0, err
 104         }
 105
 106         startTime := prevRoundLastBlock.Timestamp + BlockTimeInterval
 107
 108         nextLeaderTime, err := nextLeaderTimeHelper(startTime, uint64(time.Now().UnixNano()/1e6), consensusNode.order)
 109         if err != nil {
 110                 return 0, 0, err
 111         }
 112
 113         return nextLeaderTime, nextLeaderTime + BlockNumEachNode*BlockTimeInterval, nil
 114 }
 115
 116 func nextLeaderTimeHelper(startTime, now, nodeOrder uint64) (uint64, error) {
 117         nextLeaderTimestamp := getLastBlockTimeInTimeRange(startTime, now, nodeOrder)
 118         roundBlockTime := uint64(BlockNumEachNode * NumOfConsensusNode * BlockTimeInterval)
 119
 120         if now > nextLeaderTimestamp {
 121                 nextLeaderTimestamp += roundBlockTime
 122         }
 123
 124         return nextLeaderTimestamp, nil
 125 }
 126
 127 func getLastBlockTimeInTimeRange(startTimestamp, endTimestamp, order uint64) uint64 {
 128         // One round of product block time for all consensus nodes
 129         roundBlockTime := uint64(BlockNumEachNode * NumOfConsensusNode * BlockTimeInterval)
 130         // The start time of the last round of product block
 131         lastRoundStartTime := startTimestamp + (endTimestamp-startTimestamp)/roundBlockTime*roundBlockTime
 132         // The time of product block of the consensus in last round
 133         return lastRoundStartTime + order*(BlockNumEachNode*BlockTimeInterval)
 134 }
 135
 136 func (c *consensusNodeManager) getPrevRoundVoteLastBlock(prevBlockHash *bc.Hash) (*state.BlockNode, error) {
 137         prevBlockNode := c.blockIndex.GetNode(prevBlockHash)
 138         if prevBlockNode == nil {
 139                 return nil, errNotFoundBlockNode
 140         }
 141
 142         blockHeight := prevBlockNode.Height + 1
 143
 144         prevVoteRoundLastBlockHeight := blockHeight/roundVoteBlockNums*roundVoteBlockNums - 1
 145         // first round
 146         if blockHeight/roundVoteBlockNums == 0 {
 147                 prevVoteRoundLastBlockHeight = 0
 148         }
 149
 150         lastBlockNode := prevBlockNode.GetParent(prevVoteRoundLastBlockHeight)
 151         if lastBlockNode == nil {
 152                 return nil, errNotFoundBlockNode
 153         }
 154         return lastBlockNode, nil
 155 }
 156
 157 func (c *consensusNodeManager) getConsensusNodesByVoteResult(prevBlockHash *bc.Hash) (map[string]*consensusNode, error) {
 158         prevBlockNode := c.blockIndex.GetNode(prevBlockHash)
 159         if prevBlockNode == nil {
 160                 return nil, errNotFoundBlockNode
 161         }
 162
 163         seq := (prevBlockNode.Height + 1) / roundVoteBlockNums
 164         if seq == 0 {
 165                 return initVoteResult(), nil
 166         }
 167
 168         voteResult, err := c.store.GetVoteResult(seq)
 169         if err != nil {
 170                 // fail to find vote result, try to construct
 171                 voteResult = &state.VoteResult{
 172                         Seq:       seq,
 173                         NumOfVote: make(map[string]uint64),
 174                         Finalized: false,
 175                 }
 176         }
 177
 178         lastBlockNode, err := c.getPrevRoundVoteLastBlock(prevBlockHash)
 179         if err != nil {
 180                 return nil, err
 181         }
 182
 183         if err := c.reorganizeVoteResult(voteResult, lastBlockNode); err != nil {
 184                 return nil, err
 185         }
 186
 187         var nodes []*consensusNode
 188         for pubkey, voteNum := range voteResult.NumOfVote {
 189                 nodes = append(nodes, &consensusNode{
 190                         pubkey:  pubkey,
 191                         voteNum: voteNum,
 192                 })
 193         }
 194         // In principle, there is no need to sort all voting nodes.
 195         // if there is a performance problem, consider the optimization later.
 196         // TODO not consider the same number of votes
 197         sort.Sort(consensusNodeSlice(nodes))
 198
 199         result := make(map[string]*consensusNode)
 200         for i := 0; i < len(nodes) && i < NumOfConsensusNode; i++ {
 201                 node := nodes[i]
 202                 node.order = uint64(i)
 203                 result[node.pubkey] = node
 204         }
 205         return result, nil
 206 }
 207
 208 func (c *consensusNodeManager) reorganizeVoteResult(voteResult *state.VoteResult, forkChainNode *state.BlockNode) error {
 209         var mainChainNode *state.BlockNode
 210         emptyHash := bc.Hash{}
 211         if voteResult.LastBlockHash != emptyHash {
 212                 mainChainNode = c.blockIndex.GetNode(&voteResult.LastBlockHash)
 213                 if mainChainNode == nil {
 214                         return errNotFoundBlockNode
 215                 }
 216         }
 217
 218         var attachNodes []*state.BlockNode
 219         var detachNodes []*state.BlockNode
 220
 221         for forkChainNode.Hash != mainChainNode.Hash && forkChainNode.Height >= (voteResult.Seq-1)*roundVoteBlockNums {
 222                 attachNodes = append([]*state.BlockNode{forkChainNode}, attachNodes...)
 223                 forkChainNode = forkChainNode.Parent
 224
 225                 if mainChainNode != nil && forkChainNode.Height == mainChainNode.Height {
 226                         detachNodes = append(detachNodes, mainChainNode)
 227                         mainChainNode = mainChainNode.Parent
 228                 }
 229         }
 230
 231         for _, node := range detachNodes {
 232                 block, err := c.store.GetBlock(&node.Hash)
 233                 if err != nil {
 234                         return err
 235                 }
 236
 237                 if err := c.detachBlock(map[uint64]*state.VoteResult{voteResult.Seq: voteResult}, block); err != nil {
 238                         return err
 239                 }
 240         }
 241
 242         for _, node := range attachNodes {
 243                 block, err := c.store.GetBlock(&node.Hash)
 244                 if err != nil {
 245                         return err
 246                 }
 247
 248                 if err := c.applyBlock(map[uint64]*state.VoteResult{voteResult.Seq: voteResult}, block); err != nil {
 249                         return err
 250                 }
 251         }
 252         return nil
 253 }
 254
 255 func (c *consensusNodeManager) applyBlock(voteResultMap map[uint64]*state.VoteResult, block *types.Block) (err error) {
 256         voteSeq := block.Height / roundVoteBlockNums
 257         voteResult, err := c.getVoteResult(voteResultMap, voteSeq)
 258         if err != nil {
 259                 return err
 260         }
 261
 262         emptyHash := bc.Hash{}
 263         if voteResult.LastBlockHash != emptyHash && voteResult.LastBlockHash != block.PreviousBlockHash {
 264                 return errors.New("bbft append block error, the block parent hash is not equals last block hash of vote result")
 265         }
 266
 267         for _, tx := range block.Transactions {
 268                 for _, input := range tx.Inputs {
 269                         unVoteInput, ok := input.TypedInput.(*types.UnvoteInput)
 270                         if !ok {
 271                                 continue
 272                         }
 273
 274                         pubkey := hex.EncodeToString(unVoteInput.Vote)
 275                         voteResult.NumOfVote[pubkey], ok = checked.SubUint64(voteResult.NumOfVote[pubkey], unVoteInput.Amount)
 276                         if !ok {
 277                                 return errVotingOperationOverFlow
 278                         }
 279                 }
 280                 for _, output := range tx.Outputs {
 281                         voteOutput, ok := output.TypedOutput.(*types.VoteTxOutput)
 282                         if !ok {
 283                                 continue
 284                         }
 285
 286                         pubkey := hex.EncodeToString(voteOutput.Vote)
 287                         voteResult.NumOfVote[pubkey], ok = checked.AddUint64(voteResult.NumOfVote[pubkey], voteOutput.Amount)
 288                         if !ok {
 289                                 return errVotingOperationOverFlow
 290                         }
 291                 }
 292         }
 293
 294         voteResult.Finalized = (block.Height+1)%roundVoteBlockNums == 0
 295         return nil
 296 }
 297
 298 func (c *consensusNodeManager) getVoteResult(voteResultMap map[uint64]*state.VoteResult, seq uint64) (*state.VoteResult, error) {
 299         var err error
 300         voteResult := voteResultMap[seq]
 301         if voteResult == nil {
 302                 prevVoteResult := voteResultMap[seq - 1]
 303                 voteResult = &state.VoteResult {
 304                         Seq: seq,
 305                         NumOfVote: prevVoteResult.NumOfVote,
 306                         Finalized: false,
 307                 }
 308         }
 309
 310         if voteResult == nil {
 311                 voteResult, err = c.store.GetVoteResult(seq)
 312                 if err != nil && err != ErrNotFoundVoteResult {
 313                         return nil, err
 314                 }
 315         }
 316
 317         if voteResult == nil {
 318                 voteResult, err := c.store.GetVoteResult(seq - 1)
 319                 if err != nil && err != ErrNotFoundVoteResult {
 320                         return nil, err
 321                 }
 322                 // previous round voting must have finalized
 323                 if !voteResult.Finalized {
 324                         return nil, errors.New("previous round voting has not finalized")
 325                 }
 326
 327                 voteResult.Finalized = false
 328                 voteResult.LastBlockHash = bc.Hash{}
 329         }
 330         voteResultMap[seq] = voteResult
 331         return voteResult, nil
 332 }
 333
 334 func (c *consensusNodeManager) detachBlock(voteResultMap map[uint64]*state.VoteResult, block *types.Block) error {
 335         voteSeq := block.Height / roundVoteBlockNums
 336         voteResult := voteResultMap[voteSeq]
 337
 338         if voteResult == nil {
 339                 voteResult, err := c.store.GetVoteResult(voteSeq)
 340                 if err != nil {
 341                         return err
 342                 }
 343                 voteResultMap[voteSeq] = voteResult
 344         }
 345
 346         if voteResult.LastBlockHash != block.Hash() {
 347                 return errors.New("bbft detach block error, the block hash is not equals last block hash of vote result")
 348         }
 349
 350         for _, tx := range block.Transactions {
 351                 for _, input := range tx.Inputs {
 352                         unVoteInput, ok := input.TypedInput.(*types.UnvoteInput)
 353                         if !ok {
 354                                 continue
 355                         }
 356
 357                         pubkey := hex.EncodeToString(unVoteInput.Vote)
 358                         voteResult.NumOfVote[pubkey], ok = checked.AddUint64(voteResult.NumOfVote[pubkey], unVoteInput.Amount)
 359                         if !ok {
 360                                 return errVotingOperationOverFlow
 361                         }
 362                 }
 363                 for _, output := range tx.Outputs {
 364                         voteOutput, ok := output.TypedOutput.(*types.VoteTxOutput)
 365                         if !ok {
 366                                 continue
 367                         }
 368
 369                         pubkey := hex.EncodeToString(voteOutput.Vote)
 370                         voteResult.NumOfVote[pubkey], ok = checked.SubUint64(voteResult.NumOfVote[pubkey], voteOutput.Amount)
 371                         if !ok {
 372                                 return errVotingOperationOverFlow
 373                         }
 374                 }
 375         }
 376
 377         voteResult.Finalized = false
 378         return nil
 379 }
 380
 381 func initVoteResult() map[string]*consensusNode {
 382         voteResult := map[string]*consensusNode{}
 383         for i, pubkey := range config.CommonConfig.Federation.Xpubs {
 384                 pubkeyStr := pubkey.String()
 385                 voteResult[pubkeyStr] = &consensusNode{pubkey: pubkeyStr, voteNum: 0, order: uint64(i)}
 386         }
 387         return voteResult
 388 }