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         parentHash := bestBlockNode.Hash
  97         if bestBlockNode.Height > 0 {
  98                 parentHash = bestBlockNode.Parent.Hash
  99         }
 100
 101         consensusNode, err := c.getConsensusNode(&parentHash, hex.EncodeToString(pubkey))
 102         if err != nil {
 103                 return 0, 0, err
 104         }
 105
 106         prevRoundLastBlock, err := c.getPrevRoundVoteLastBlock(&parentHash)
 107         if err != nil {
 108                 return 0, 0, err
 109         }
 110
 111         startTime := prevRoundLastBlock.Timestamp + BlockTimeInterval
 112
 113         nextLeaderTime, err := nextLeaderTimeHelper(startTime, uint64(time.Now().UnixNano()/1e6), consensusNode.order)
 114         if err != nil {
 115                 return 0, 0, err
 116         }
 117
 118         return nextLeaderTime, nextLeaderTime + BlockNumEachNode*BlockTimeInterval, nil
 119 }
 120
 121 func nextLeaderTimeHelper(startTime, now, nodeOrder uint64) (uint64, error) {
 122         nextLeaderTimestamp := getLastBlockTimeInTimeRange(startTime, now, nodeOrder)
 123         roundBlockTime := uint64(BlockNumEachNode * NumOfConsensusNode * BlockTimeInterval)
 124
 125         if now > nextLeaderTimestamp {
 126                 nextLeaderTimestamp += roundBlockTime
 127         }
 128
 129         return nextLeaderTimestamp, nil
 130 }
 131
 132 func getLastBlockTimeInTimeRange(startTimestamp, endTimestamp, order uint64) uint64 {
 133         // One round of product block time for all consensus nodes
 134         roundBlockTime := uint64(BlockNumEachNode * NumOfConsensusNode * BlockTimeInterval)
 135         // The start time of the last round of product block
 136         lastRoundStartTime := startTimestamp + (endTimestamp-startTimestamp)/roundBlockTime*roundBlockTime
 137         // The time of product block of the consensus in last round
 138         return lastRoundStartTime + order*(BlockNumEachNode*BlockTimeInterval)
 139 }
 140
 141 func (c *consensusNodeManager) getPrevRoundVoteLastBlock(prevBlockHash *bc.Hash) (*state.BlockNode, error) {
 142         prevBlockNode := c.blockIndex.GetNode(prevBlockHash)
 143         if prevBlockNode == nil {
 144                 return nil, errNotFoundBlockNode
 145         }
 146
 147         blockHeight := prevBlockNode.Height + 1
 148
 149         prevVoteRoundLastBlockHeight := blockHeight/roundVoteBlockNums*roundVoteBlockNums - 1
 150         // first round
 151         if blockHeight/roundVoteBlockNums == 0 {
 152                 prevVoteRoundLastBlockHeight = 0
 153         }
 154
 155         lastBlockNode := prevBlockNode.GetParent(prevVoteRoundLastBlockHeight)
 156         if lastBlockNode == nil {
 157                 return nil, errNotFoundBlockNode
 158         }
 159         return lastBlockNode, nil
 160 }
 161
 162 func (c *consensusNodeManager) getConsensusNodesByVoteResult(prevBlockHash *bc.Hash) (map[string]*consensusNode, error) {
 163         prevBlockNode := c.blockIndex.GetNode(prevBlockHash)
 164         if prevBlockNode == nil {
 165                 return nil, errNotFoundBlockNode
 166         }
 167
 168         seq := (prevBlockNode.Height + 1) / roundVoteBlockNums
 169         if seq == 0 {
 170                 return initVoteResult(), nil
 171         }
 172
 173         voteResult, err := c.store.GetVoteResult(seq)
 174         if err != nil {
 175                 // fail to find vote result, try to construct
 176                 voteResult = &state.VoteResult{
 177                         Seq:       seq,
 178                         NumOfVote: make(map[string]uint64),
 179                         Finalized: false,
 180                 }
 181         }
 182
 183         lastBlockNode, err := c.getPrevRoundVoteLastBlock(prevBlockHash)
 184         if err != nil {
 185                 return nil, err
 186         }
 187
 188         if err := c.reorganizeVoteResult(voteResult, lastBlockNode); err != nil {
 189                 return nil, err
 190         }
 191
 192         var nodes []*consensusNode
 193         for pubkey, voteNum := range voteResult.NumOfVote {
 194                 nodes = append(nodes, &consensusNode{
 195                         pubkey:  pubkey,
 196                         voteNum: voteNum,
 197                 })
 198         }
 199         // In principle, there is no need to sort all voting nodes.
 200         // if there is a performance problem, consider the optimization later.
 201         // TODO not consider the same number of votes
 202         sort.Sort(consensusNodeSlice(nodes))
 203
 204         result := make(map[string]*consensusNode)
 205         for i := 0; i < len(nodes) && i < NumOfConsensusNode; i++ {
 206                 node := nodes[i]
 207                 node.order = uint64(i)
 208                 result[node.pubkey] = node
 209         }
 210         return result, nil
 211 }
 212
 213 func (c *consensusNodeManager) reorganizeVoteResult(voteResult *state.VoteResult, forkChainNode *state.BlockNode) error {
 214         var mainChainNode *state.BlockNode
 215         emptyHash := bc.Hash{}
 216         if voteResult.LastBlockHash != emptyHash {
 217                 mainChainNode = c.blockIndex.GetNode(&voteResult.LastBlockHash)
 218                 if mainChainNode == nil {
 219                         return errNotFoundBlockNode
 220                 }
 221         }
 222
 223         var attachNodes []*state.BlockNode
 224         var detachNodes []*state.BlockNode
 225
 226         for forkChainNode.Hash != mainChainNode.Hash && forkChainNode.Height >= (voteResult.Seq-1)*roundVoteBlockNums {
 227                 attachNodes = append([]*state.BlockNode{forkChainNode}, attachNodes...)
 228                 forkChainNode = forkChainNode.Parent
 229
 230                 if mainChainNode != nil && forkChainNode.Height == mainChainNode.Height {
 231                         detachNodes = append(detachNodes, mainChainNode)
 232                         mainChainNode = mainChainNode.Parent
 233                 }
 234         }
 235
 236         for _, node := range detachNodes {
 237                 block, err := c.store.GetBlock(&node.Hash)
 238                 if err != nil {
 239                         return err
 240                 }
 241
 242                 if err := c.detachBlock(map[uint64]*state.VoteResult{voteResult.Seq: voteResult}, block); err != nil {
 243                         return err
 244                 }
 245         }
 246
 247         for _, node := range attachNodes {
 248                 block, err := c.store.GetBlock(&node.Hash)
 249                 if err != nil {
 250                         return err
 251                 }
 252
 253                 if err := c.applyBlock(map[uint64]*state.VoteResult{voteResult.Seq: voteResult}, block); err != nil {
 254                         return err
 255                 }
 256         }
 257         return nil
 258 }
 259
 260 func (c *consensusNodeManager) applyBlock(voteResultMap map[uint64]*state.VoteResult, block *types.Block) (err error) {
 261         voteResult, err := c.getVoteResult(voteResultMap, block.Height)
 262         if err != nil {
 263                 return err
 264         }
 265
 266         emptyHash := bc.Hash{}
 267         if voteResult.LastBlockHash != emptyHash && voteResult.LastBlockHash != block.PreviousBlockHash {
 268                 return errors.New("bbft append block error, the block parent hash is not equals last block hash of vote result")
 269         }
 270
 271         for _, tx := range block.Transactions {
 272                 for _, input := range tx.Inputs {
 273                         unVoteInput, ok := input.TypedInput.(*types.UnvoteInput)
 274                         if !ok {
 275                                 continue
 276                         }
 277
 278                         pubkey := hex.EncodeToString(unVoteInput.Vote)
 279                         voteResult.NumOfVote[pubkey], ok = checked.SubUint64(voteResult.NumOfVote[pubkey], unVoteInput.Amount)
 280                         if !ok {
 281                                 return errVotingOperationOverFlow
 282                         }
 283                 }
 284                 for _, output := range tx.Outputs {
 285                         voteOutput, ok := output.TypedOutput.(*types.VoteTxOutput)
 286                         if !ok {
 287                                 continue
 288                         }
 289
 290                         pubkey := hex.EncodeToString(voteOutput.Vote)
 291                         voteResult.NumOfVote[pubkey], ok = checked.AddUint64(voteResult.NumOfVote[pubkey], voteOutput.Amount)
 292                         if !ok {
 293                                 return errVotingOperationOverFlow
 294                         }
 295                 }
 296         }
 297
 298         voteResult.Finalized = (block.Height+1)%roundVoteBlockNums == 0
 299         return nil
 300 }
 301
 302 func (c *consensusNodeManager) getVoteResult(voteResultMap map[uint64]*state.VoteResult, blockHeight uint64) (*state.VoteResult, error) {
 303         var err error
 304         seq := blockHeight / roundVoteBlockNums
 305         voteResult := voteResultMap[seq]
 306         if blockHeight == 0 {
 307                 voteResult = &state.VoteResult{
 308                         Seq:       seq,
 309                         NumOfVote: make(map[string]uint64),
 310                         Finalized: false,
 311                 }
 312         }
 313
 314         if voteResult == nil {
 315                 prevVoteResult := voteResultMap[seq-1]
 316                 if prevVoteResult != nil {
 317                         voteResult = &state.VoteResult{
 318                                 Seq:       seq,
 319                                 NumOfVote: prevVoteResult.NumOfVote,
 320                                 Finalized: false,
 321                         }
 322                 }
 323         }
 324
 325         if voteResult == nil {
 326                 voteResult, err = c.store.GetVoteResult(seq)
 327                 if err != nil && err != ErrNotFoundVoteResult {
 328                         return nil, err
 329                 }
 330         }
 331
 332         if voteResult == nil {
 333                 voteResult, err := c.store.GetVoteResult(seq - 1)
 334                 if err != nil && err != ErrNotFoundVoteResult {
 335                         return nil, err
 336                 }
 337
 338                 if voteResult != nil {
 339                         // previous round voting must have finalized
 340                         if !voteResult.Finalized {
 341                                 return nil, errors.New("previous round voting has not finalized")
 342                         }
 343
 344                         voteResult.Finalized = false
 345                         voteResult.LastBlockHash = bc.Hash{}
 346                 }
 347         }
 348
 349         if voteResult == nil {
 350                 return nil, errors.New("fail to get vote result")
 351         }
 352
 353         voteResultMap[seq] = voteResult
 354         return voteResult, nil
 355 }
 356
 357 func (c *consensusNodeManager) detachBlock(voteResultMap map[uint64]*state.VoteResult, block *types.Block) error {
 358         voteSeq := block.Height / roundVoteBlockNums
 359         voteResult := voteResultMap[voteSeq]
 360
 361         if voteResult == nil {
 362                 voteResult, err := c.store.GetVoteResult(voteSeq)
 363                 if err != nil {
 364                         return err
 365                 }
 366                 voteResultMap[voteSeq] = voteResult
 367         }
 368
 369         if voteResult.LastBlockHash != block.Hash() {
 370                 return errors.New("bbft detach block error, the block hash is not equals last block hash of vote result")
 371         }
 372
 373         for _, tx := range block.Transactions {
 374                 for _, input := range tx.Inputs {
 375                         unVoteInput, ok := input.TypedInput.(*types.UnvoteInput)
 376                         if !ok {
 377                                 continue
 378                         }
 379
 380                         pubkey := hex.EncodeToString(unVoteInput.Vote)
 381                         voteResult.NumOfVote[pubkey], ok = checked.AddUint64(voteResult.NumOfVote[pubkey], unVoteInput.Amount)
 382                         if !ok {
 383                                 return errVotingOperationOverFlow
 384                         }
 385                 }
 386                 for _, output := range tx.Outputs {
 387                         voteOutput, ok := output.TypedOutput.(*types.VoteTxOutput)
 388                         if !ok {
 389                                 continue
 390                         }
 391
 392                         pubkey := hex.EncodeToString(voteOutput.Vote)
 393                         voteResult.NumOfVote[pubkey], ok = checked.SubUint64(voteResult.NumOfVote[pubkey], voteOutput.Amount)
 394                         if !ok {
 395                                 return errVotingOperationOverFlow
 396                         }
 397                 }
 398         }
 399
 400         voteResult.Finalized = false
 401         return nil
 402 }
 403
 404 func initVoteResult() map[string]*consensusNode {
 405         voteResult := map[string]*consensusNode{}
 406         for i, pubkey := range config.CommonConfig.Federation.Xpubs {
 407                 pubkeyStr := pubkey.String()
 408                 voteResult[pubkeyStr] = &consensusNode{pubkey: pubkeyStr, voteNum: 0, order: uint64(i)}
 409         }
 410         return voteResult
 411 }