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