protocol/consensus_node_manager.go

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