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