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 := voteResultMap[voteSeq]
 258
 259         if voteResult == nil {
 260                 voteResult, err = c.store.GetVoteResult(voteSeq)
 261                 if err != nil && err != ErrNotFoundVoteResult {
 262                         return err
 263                 }
 264         }
 265
 266         if voteResult == nil {
 267                 voteResult = &state.VoteResult{
 268                         Seq:       voteSeq,
 269                         NumOfVote: make(map[string]uint64),
 270                 }
 271         }
 272
 273         voteResultMap[voteSeq] = voteResult
 274
 275         emptyHash := bc.Hash{}
 276         if voteResult.LastBlockHash != emptyHash && voteResult.LastBlockHash != block.PreviousBlockHash {
 277                 return errors.New("bbft append block error, the block parent hash is not equals last block hash of vote result")
 278         }
 279
 280         for _, tx := range block.Transactions {
 281                 for _, input := range tx.Inputs {
 282                         unVoteInput, ok := input.TypedInput.(*types.UnvoteInput)
 283                         if !ok {
 284                                 continue
 285                         }
 286
 287                         pubkey := hex.EncodeToString(unVoteInput.Vote)
 288                         voteResult.NumOfVote[pubkey], ok = checked.SubUint64(voteResult.NumOfVote[pubkey], unVoteInput.Amount)
 289                         if !ok {
 290                                 return errVotingOperationOverFlow
 291                         }
 292                 }
 293                 for _, output := range tx.Outputs {
 294                         voteOutput, ok := output.TypedOutput.(*types.VoteTxOutput)
 295                         if !ok {
 296                                 continue
 297                         }
 298
 299                         pubkey := hex.EncodeToString(voteOutput.Vote)
 300                         voteResult.NumOfVote[pubkey], ok = checked.AddUint64(voteResult.NumOfVote[pubkey], voteOutput.Amount)
 301                         if !ok {
 302                                 return errVotingOperationOverFlow
 303                         }
 304                 }
 305         }
 306
 307         voteResult.Finalized = (block.Height+1)%roundVoteBlockNums == 0
 308         return nil
 309 }
 310
 311 func (c *consensusNodeManager) detachBlock(voteResultMap map[uint64]*state.VoteResult, block *types.Block) error {
 312         voteSeq := block.Height / roundVoteBlockNums
 313         voteResult := voteResultMap[voteSeq]
 314
 315         if voteResult == nil {
 316                 voteResult, err := c.store.GetVoteResult(voteSeq)
 317                 if err != nil {
 318                         return err
 319                 }
 320                 voteResultMap[voteSeq] = voteResult
 321         }
 322
 323         if voteResult.LastBlockHash != block.Hash() {
 324                 return errors.New("bbft detach block error, the block hash is not equals last block hash of vote result")
 325         }
 326
 327         for _, tx := range block.Transactions {
 328                 for _, input := range tx.Inputs {
 329                         unVoteInput, ok := input.TypedInput.(*types.UnvoteInput)
 330                         if !ok {
 331                                 continue
 332                         }
 333
 334                         pubkey := hex.EncodeToString(unVoteInput.Vote)
 335                         voteResult.NumOfVote[pubkey], ok = checked.AddUint64(voteResult.NumOfVote[pubkey], unVoteInput.Amount)
 336                         if !ok {
 337                                 return errVotingOperationOverFlow
 338                         }
 339                 }
 340                 for _, output := range tx.Outputs {
 341                         voteOutput, ok := output.TypedOutput.(*types.VoteTxOutput)
 342                         if !ok {
 343                                 continue
 344                         }
 345
 346                         pubkey := hex.EncodeToString(voteOutput.Vote)
 347                         voteResult.NumOfVote[pubkey], ok = checked.SubUint64(voteResult.NumOfVote[pubkey], voteOutput.Amount)
 348                         if !ok {
 349                                 return errVotingOperationOverFlow
 350                         }
 351                 }
 352         }
 353
 354         voteResult.Finalized = false
 355         return nil
 356 }
 357
 358 func initVoteResult() map[string]*consensusNode {
 359         voteResult := map[string]*consensusNode{}
 360         for i, pubkey := range config.CommonConfig.Federation.Xpubs {
 361                 pubkeyStr := pubkey.String()
 362                 voteResult[pubkeyStr] = &consensusNode{pubkey: pubkeyStr, voteNum: 0, order: uint64(i)}
 363         }
 364         return voteResult
 365 }