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         MinVoteNum         = 5000000
  20
  21         // BlockTimeInterval indicate product one block per 500 milliseconds
  22         BlockTimeInterval = 500
  23         // BlockNumEachNode indicate product three blocks per node in succession
  24         BlockNumEachNode = 3
  25 )
  26
  27 var (
  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(prevBlockHash *bc.Hash, pubkey string) (*consensusNode, error) {
  57         consensusNodeMap, err := c.getConsensusNodesByVoteResult(prevBlockHash)
  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(block *types.Block, pubKey string) (bool, error) {
  70         consensusNode, err := c.getConsensusNode(&block.PreviousBlockHash, pubKey)
  71         if err != nil && err != errNotFoundConsensusNode {
  72                 return false, err
  73         }
  74
  75         if consensusNode == nil {
  76                 return false, nil
  77         }
  78
  79         prevVoteRoundLastBlock, err := c.getPrevRoundVoteLastBlock(&block.PreviousBlockHash)
  80         if err != nil {
  81                 return false, err
  82         }
  83
  84         startTimestamp := prevVoteRoundLastBlock.Timestamp + BlockTimeInterval
  85
  86         begin := getLastBlockTimeInTimeRange(startTimestamp, block.Timestamp, consensusNode.order)
  87         end := begin + BlockNumEachNode*BlockTimeInterval
  88         return block.Timestamp >= begin && block.Timestamp < end, nil
  89 }
  90
  91 func (c *consensusNodeManager) nextLeaderTimeRange(pubkey []byte, prevBlockHash *bc.Hash) (uint64, uint64, error) {
  92         consensusNode, err := c.getConsensusNode(prevBlockHash, hex.EncodeToString(pubkey))
  93         if err != nil {
  94                 return 0, 0, err
  95         }
  96
  97         prevRoundLastBlock, err := c.getPrevRoundVoteLastBlock(prevBlockHash)
  98         if err != nil {
  99                 return 0, 0, err
 100         }
 101
 102         startTime := prevRoundLastBlock.Timestamp + BlockTimeInterval
 103
 104         nextLeaderTime, err := nextLeaderTimeHelper(startTime, uint64(time.Now().UnixNano()/1e6), consensusNode.order)
 105         if err != nil {
 106                 return 0, 0, err
 107         }
 108
 109         return nextLeaderTime, nextLeaderTime + BlockNumEachNode*BlockTimeInterval, nil
 110 }
 111
 112 func nextLeaderTimeHelper(startTime, now, nodeOrder uint64) (uint64, error) {
 113         nextLeaderTimestamp := getLastBlockTimeInTimeRange(startTime, now, nodeOrder)
 114         roundBlockTime := uint64(BlockNumEachNode * NumOfConsensusNode * BlockTimeInterval)
 115
 116         if now > nextLeaderTimestamp {
 117                 nextLeaderTimestamp += roundBlockTime
 118         }
 119
 120         return nextLeaderTimestamp, nil
 121 }
 122
 123 func getLastBlockTimeInTimeRange(startTimestamp, endTimestamp, order uint64) uint64 {
 124         // One round of product block time for all consensus nodes
 125         roundBlockTime := uint64(BlockNumEachNode * NumOfConsensusNode * BlockTimeInterval)
 126         // The start time of the last round of product block
 127         lastRoundStartTime := startTimestamp + (endTimestamp-startTimestamp)/roundBlockTime*roundBlockTime
 128         // The time of product block of the consensus in last round
 129         return lastRoundStartTime + order*(BlockNumEachNode*BlockTimeInterval)
 130 }
 131
 132 func (c *consensusNodeManager) getPrevRoundVoteLastBlock(prevBlockHash *bc.Hash) (*state.BlockNode, error) {
 133         prevBlockNode := c.blockIndex.GetNode(prevBlockHash)
 134         if prevBlockNode == nil {
 135                 return nil, errNotFoundBlockNode
 136         }
 137
 138         blockHeight := prevBlockNode.Height + 1
 139
 140         prevVoteRoundLastBlockHeight := blockHeight/RoundVoteBlockNums*RoundVoteBlockNums - 1
 141         // first round
 142         if blockHeight/RoundVoteBlockNums == 0 {
 143                 prevVoteRoundLastBlockHeight = 0
 144         }
 145
 146         lastBlockNode := prevBlockNode.GetParent(prevVoteRoundLastBlockHeight)
 147         if lastBlockNode == nil {
 148                 return nil, errNotFoundBlockNode
 149         }
 150         return lastBlockNode, nil
 151 }
 152
 153 func (c *consensusNodeManager) getConsensusNodesByVoteResult(prevBlockHash *bc.Hash) (map[string]*consensusNode, error) {
 154         prevBlockNode := c.blockIndex.GetNode(prevBlockHash)
 155         if prevBlockNode == nil {
 156                 return nil, errNotFoundBlockNode
 157         }
 158
 159         seq := (prevBlockNode.Height + 1) / RoundVoteBlockNums
 160         voteResult, err := c.store.GetVoteResult(seq)
 161         if err != nil {
 162                 // TODO find previous round vote
 163                 voteResult = &state.VoteResult{
 164                         Seq:       seq,
 165                         NumOfVote: make(map[string]uint64),
 166                         Finalized: false,
 167                 }
 168         }
 169
 170         lastBlockNode, err := c.getPrevRoundVoteLastBlock(prevBlockHash)
 171         if err != nil {
 172                 return nil, err
 173         }
 174
 175         if err := c.reorganizeVoteResult(voteResult, lastBlockNode); err != nil {
 176                 return nil, err
 177         }
 178
 179         if len(voteResult.NumOfVote) == 0 {
 180                 return initConsensusNodes(), nil
 181         }
 182
 183         var nodes []*consensusNode
 184         for pubkey, voteNum := range voteResult.NumOfVote {
 185                 if voteNum >= MinVoteNum {
 186                         nodes = append(nodes, &consensusNode{
 187                                 pubkey:  pubkey,
 188                                 voteNum: voteNum,
 189                         })
 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 < len(nodes) && 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         genesisBlockHash := config.GenesisBlock().Hash()
 208         mainChainNode := c.blockIndex.GetNode(&genesisBlockHash)
 209
 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 != nil && mainChainNode != nil && forkChainNode.Hash != mainChainNode.Hash {
 222                 if forkChainNode.Height == mainChainNode.Height {
 223                         detachNodes = append(detachNodes, mainChainNode)
 224                         mainChainNode = mainChainNode.Parent
 225                 }
 226                 attachNodes = append([]*state.BlockNode{forkChainNode}, attachNodes...)
 227                 forkChainNode = forkChainNode.Parent
 228         }
 229
 230         for _, node := range detachNodes {
 231                 block, err := c.store.GetBlock(&node.Hash)
 232                 if err != nil {
 233                         return err
 234                 }
 235
 236                 if err := c.detachBlock(map[uint64]*state.VoteResult{voteResult.Seq: voteResult}, block); err != nil {
 237                         return err
 238                 }
 239         }
 240
 241         for _, node := range attachNodes {
 242                 block, err := c.store.GetBlock(&node.Hash)
 243                 if err != nil {
 244                         return err
 245                 }
 246
 247                 if err := c.applyBlock(map[uint64]*state.VoteResult{voteResult.Seq: voteResult}, block); err != nil {
 248                         return err
 249                 }
 250         }
 251         return nil
 252 }
 253
 254 func (c *consensusNodeManager) applyBlock(voteResultMap map[uint64]*state.VoteResult, block *types.Block) (err error) {
 255         voteResult, err := c.getVoteResult(voteResultMap, block.Height)
 256         if err != nil {
 257                 return err
 258         }
 259
 260         emptyHash := bc.Hash{}
 261         if voteResult.LastBlockHash != emptyHash && voteResult.LastBlockHash != block.PreviousBlockHash {
 262                 return errors.New("bbft append block error, the block parent hash is not equals last block hash of vote result")
 263         }
 264
 265         for _, tx := range block.Transactions {
 266                 for _, input := range tx.Inputs {
 267                         unVoteInput, ok := input.TypedInput.(*types.UnvoteInput)
 268                         if !ok {
 269                                 continue
 270                         }
 271
 272                         pubkey := hex.EncodeToString(unVoteInput.Vote)
 273                         voteResult.NumOfVote[pubkey], ok = checked.SubUint64(voteResult.NumOfVote[pubkey], unVoteInput.Amount)
 274                         if !ok {
 275                                 return errVotingOperationOverFlow
 276                         }
 277                 }
 278                 for _, output := range tx.Outputs {
 279                         voteOutput, ok := output.TypedOutput.(*types.VoteTxOutput)
 280                         if !ok {
 281                                 continue
 282                         }
 283
 284                         pubkey := hex.EncodeToString(voteOutput.Vote)
 285                         voteResult.NumOfVote[pubkey], ok = checked.AddUint64(voteResult.NumOfVote[pubkey], voteOutput.Amount)
 286                         if !ok {
 287                                 return errVotingOperationOverFlow
 288                         }
 289                 }
 290         }
 291
 292         voteResult.Finalized = (block.Height+1)%RoundVoteBlockNums == 0
 293         return nil
 294 }
 295
 296 func (c *consensusNodeManager) getVoteResult(voteResultMap map[uint64]*state.VoteResult, blockHeight uint64) (*state.VoteResult, error) {
 297         var err error
 298         // This round of voting prepares for the next round
 299         seq := blockHeight/RoundVoteBlockNums + 1
 300         voteResult := voteResultMap[seq]
 301         if blockHeight == 0 {
 302                 voteResult = &state.VoteResult{
 303                         Seq:       seq,
 304                         NumOfVote: make(map[string]uint64),
 305                         Finalized: false,
 306                 }
 307         }
 308
 309         if voteResult == nil {
 310                 prevVoteResult := voteResultMap[seq-1]
 311                 if prevVoteResult != nil {
 312                         voteResult = &state.VoteResult{
 313                                 Seq:       seq,
 314                                 NumOfVote: prevVoteResult.NumOfVote,
 315                                 Finalized: false,
 316                         }
 317                 }
 318         }
 319
 320         if voteResult == nil {
 321                 voteResult, err = c.store.GetVoteResult(seq)
 322                 if err != nil && err != ErrNotFoundVoteResult {
 323                         return nil, err
 324                 }
 325         }
 326
 327         if voteResult == nil {
 328                 voteResult, err = c.store.GetVoteResult(seq - 1)
 329                 if err != nil && err != ErrNotFoundVoteResult {
 330                         return nil, err
 331                 }
 332
 333                 if voteResult != nil {
 334                         // previous round voting must have finalized
 335                         if !voteResult.Finalized {
 336                                 return nil, errors.New("previous round voting has not finalized")
 337                         }
 338
 339                         voteResult.Seq = seq
 340                         voteResult.Finalized = false
 341                         voteResult.LastBlockHash = bc.Hash{}
 342                 }
 343         }
 344
 345         if voteResult == nil {
 346                 return nil, errors.New("fail to get vote result")
 347         }
 348
 349         voteResultMap[seq] = voteResult
 350         return voteResult, nil
 351 }
 352
 353 func (c *consensusNodeManager) detachBlock(voteResultMap map[uint64]*state.VoteResult, block *types.Block) error {
 354         voteSeq := block.Height / RoundVoteBlockNums
 355         voteResult := voteResultMap[voteSeq]
 356
 357         if voteResult == nil {
 358                 voteResult, err := c.store.GetVoteResult(voteSeq)
 359                 if err != nil {
 360                         return err
 361                 }
 362                 voteResultMap[voteSeq] = voteResult
 363         }
 364
 365         if voteResult.LastBlockHash != block.Hash() {
 366                 return errors.New("bbft detach block error, the block hash is not equals last block hash of vote result")
 367         }
 368
 369         for _, tx := range block.Transactions {
 370                 for _, input := range tx.Inputs {
 371                         unVoteInput, ok := input.TypedInput.(*types.UnvoteInput)
 372                         if !ok {
 373                                 continue
 374                         }
 375
 376                         pubkey := hex.EncodeToString(unVoteInput.Vote)
 377                         voteResult.NumOfVote[pubkey], ok = checked.AddUint64(voteResult.NumOfVote[pubkey], unVoteInput.Amount)
 378                         if !ok {
 379                                 return errVotingOperationOverFlow
 380                         }
 381                 }
 382                 for _, output := range tx.Outputs {
 383                         voteOutput, ok := output.TypedOutput.(*types.VoteTxOutput)
 384                         if !ok {
 385                                 continue
 386                         }
 387
 388                         pubkey := hex.EncodeToString(voteOutput.Vote)
 389                         voteResult.NumOfVote[pubkey], ok = checked.SubUint64(voteResult.NumOfVote[pubkey], voteOutput.Amount)
 390                         if !ok {
 391                                 return errVotingOperationOverFlow
 392                         }
 393                 }
 394         }
 395
 396         voteResult.Finalized = false
 397         return nil
 398 }
 399
 400 func initConsensusNodes() map[string]*consensusNode {
 401         voteResult := map[string]*consensusNode{}
 402         for i, pubkey := range config.CommonConfig.Federation.Xpubs {
 403                 pubkeyStr := pubkey.String()
 404                 voteResult[pubkeyStr] = &consensusNode{pubkey: pubkeyStr, voteNum: 0, order: uint64(i)}
 405         }
 406         return voteResult
 407 }