protocol/consensus_node_manager.go

   1 package protocol
   2
   3 import (
   4         "encoding/hex"
   5         "sort"
   6
   7         "github.com/vapor/config"
   8         "github.com/vapor/consensus"
   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 var (
  17         errNotFoundConsensusNode = errors.New("can not found consensus node")
  18         errNotFoundBlockNode     = errors.New("can not find block node")
  19 )
  20
  21 type consensusNode struct {
  22         pubkey  string
  23         voteNum uint64
  24         order   uint64
  25 }
  26
  27 type consensusNodeSlice []*consensusNode
  28
  29 func (c consensusNodeSlice) Len() int           { return len(c) }
  30 func (c consensusNodeSlice) Less(i, j int) bool { return c[i].voteNum > c[j].voteNum }
  31 func (c consensusNodeSlice) Swap(i, j int)      { c[i], c[j] = c[j], c[i] }
  32
  33 type consensusNodeManager struct {
  34         store      Store
  35         blockIndex *state.BlockIndex
  36 }
  37
  38 func newConsensusNodeManager(store Store, blockIndex *state.BlockIndex) *consensusNodeManager {
  39         return &consensusNodeManager{
  40                 store:      store,
  41                 blockIndex: blockIndex,
  42         }
  43 }
  44
  45 func (c *consensusNodeManager) getConsensusNode(prevBlockHash *bc.Hash, pubkey string) (*consensusNode, error) {
  46         consensusNodeMap, err := c.getConsensusNodesByVoteResult(prevBlockHash)
  47         if err != nil {
  48                 return nil, err
  49         }
  50
  51         node, exist := consensusNodeMap[pubkey]
  52         if !exist {
  53                 return nil, errNotFoundConsensusNode
  54         }
  55         return node, nil
  56 }
  57
  58 func (c *consensusNodeManager) isBlocker(prevBlockHash *bc.Hash, pubKey string, timeStamp uint64) (bool, error) {
  59         consensusNode, err := c.getConsensusNode(prevBlockHash, pubKey)
  60         if err != nil && err != errNotFoundConsensusNode {
  61                 return false, err
  62         }
  63
  64         if consensusNode == nil {
  65                 return false, nil
  66         }
  67
  68         prevVoteRoundLastBlock, err := c.getPrevRoundVoteLastBlock(prevBlockHash)
  69         if err != nil {
  70                 return false, err
  71         }
  72
  73         startTimestamp := prevVoteRoundLastBlock.Timestamp + consensus.BlockTimeInterval
  74         begin := getLastBlockTimeInTimeRange(startTimestamp, timeStamp, consensusNode.order)
  75         end := begin + consensus.BlockNumEachNode*consensus.BlockTimeInterval
  76         return timeStamp >= begin && timeStamp < end, nil
  77 }
  78
  79 func getLastBlockTimeInTimeRange(startTimestamp, endTimestamp, order uint64) uint64 {
  80         // One round of product block time for all consensus nodes
  81         roundBlockTime := uint64(consensus.BlockNumEachNode * consensus.NumOfConsensusNode * consensus.BlockTimeInterval)
  82         // The start time of the last round of product block
  83         lastRoundStartTime := startTimestamp + (endTimestamp-startTimestamp)/roundBlockTime*roundBlockTime
  84         // The time of product block of the consensus in last round
  85         return lastRoundStartTime + order*(consensus.BlockNumEachNode*consensus.BlockTimeInterval)
  86 }
  87
  88 func (c *consensusNodeManager) getPrevRoundVoteLastBlock(prevBlockHash *bc.Hash) (*state.BlockNode, error) {
  89         prevBlockNode := c.blockIndex.GetNode(prevBlockHash)
  90         if prevBlockNode == nil {
  91                 return nil, errNotFoundBlockNode
  92         }
  93
  94         blockHeight := prevBlockNode.Height + 1
  95
  96         prevVoteRoundLastBlockHeight := blockHeight/consensus.RoundVoteBlockNums*consensus.RoundVoteBlockNums - 1
  97         // first round
  98         if blockHeight/consensus.RoundVoteBlockNums == 0 {
  99                 prevVoteRoundLastBlockHeight = 0
 100         }
 101
 102         lastBlockNode := prevBlockNode.GetParent(prevVoteRoundLastBlockHeight)
 103         if lastBlockNode == nil {
 104                 return nil, errNotFoundBlockNode
 105         }
 106         return lastBlockNode, nil
 107 }
 108
 109 func (c *consensusNodeManager) getConsensusNodesByVoteResult(prevBlockHash *bc.Hash) (map[string]*consensusNode, error) {
 110         prevBlockNode := c.blockIndex.GetNode(prevBlockHash)
 111         if prevBlockNode == nil {
 112                 return nil, errNotFoundBlockNode
 113         }
 114
 115         seq := (prevBlockNode.Height + 1) / consensus.RoundVoteBlockNums
 116         voteResult, err := c.store.GetVoteResult(seq)
 117         if err != nil {
 118                 // TODO find previous round vote
 119                 voteResult = &state.VoteResult{
 120                         Seq:       seq,
 121                         NumOfVote: make(map[string]uint64),
 122                         Finalized: false,
 123                 }
 124         }
 125
 126         lastBlockNode, err := c.getPrevRoundVoteLastBlock(prevBlockHash)
 127         if err != nil {
 128                 return nil, err
 129         }
 130
 131         if err := c.reorganizeVoteResult(voteResult, lastBlockNode); err != nil {
 132                 return nil, err
 133         }
 134
 135         if len(voteResult.NumOfVote) == 0 {
 136                 return initConsensusNodes(), nil
 137         }
 138
 139         var nodes []*consensusNode
 140         for pubkey, voteNum := range voteResult.NumOfVote {
 141                 if voteNum >= consensus.MinVoteNum {
 142                         nodes = append(nodes, &consensusNode{
 143                                 pubkey:  pubkey,
 144                                 voteNum: voteNum,
 145                         })
 146                 }
 147         }
 148         // In principle, there is no need to sort all voting nodes.
 149         // if there is a performance problem, consider the optimization later.
 150         // TODO not consider the same number of votes
 151         sort.Sort(consensusNodeSlice(nodes))
 152
 153         result := make(map[string]*consensusNode)
 154         for i := 0; i < len(nodes) && i < consensus.NumOfConsensusNode; i++ {
 155                 node := nodes[i]
 156                 node.order = uint64(i)
 157                 result[node.pubkey] = node
 158         }
 159         return result, nil
 160 }
 161
 162 func (c *consensusNodeManager) reorganizeVoteResult(voteResult *state.VoteResult, forkChainNode *state.BlockNode) error {
 163         genesisBlockHash := config.GenesisBlock().Hash()
 164         mainChainNode := c.blockIndex.GetNode(&genesisBlockHash)
 165
 166         emptyHash := bc.Hash{}
 167         if voteResult.LastBlockHash != emptyHash {
 168                 mainChainNode = c.blockIndex.GetNode(&voteResult.LastBlockHash)
 169                 if mainChainNode == nil {
 170                         return errNotFoundBlockNode
 171                 }
 172         }
 173
 174         var attachNodes []*state.BlockNode
 175         var detachNodes []*state.BlockNode
 176
 177         for forkChainNode != nil && mainChainNode != nil && forkChainNode.Hash != mainChainNode.Hash {
 178                 if forkChainNode.Height == mainChainNode.Height {
 179                         detachNodes = append(detachNodes, mainChainNode)
 180                         mainChainNode = mainChainNode.Parent
 181                 }
 182                 attachNodes = append([]*state.BlockNode{forkChainNode}, attachNodes...)
 183                 forkChainNode = forkChainNode.Parent
 184         }
 185
 186         for _, node := range detachNodes {
 187                 block, err := c.store.GetBlock(&node.Hash)
 188                 if err != nil {
 189                         return err
 190                 }
 191
 192                 if err := c.detachBlock(map[uint64]*state.VoteResult{voteResult.Seq: voteResult}, block); err != nil {
 193                         return err
 194                 }
 195         }
 196
 197         for _, node := range attachNodes {
 198                 block, err := c.store.GetBlock(&node.Hash)
 199                 if err != nil {
 200                         return err
 201                 }
 202
 203                 if err := c.applyBlock(map[uint64]*state.VoteResult{voteResult.Seq: voteResult}, block); err != nil {
 204                         return err
 205                 }
 206         }
 207         return nil
 208 }
 209
 210 func (c *consensusNodeManager) applyBlock(voteResultMap map[uint64]*state.VoteResult, block *types.Block) (err error) {
 211         voteResult, err := c.getVoteResult(voteResultMap, block.Height)
 212         if err != nil {
 213                 return err
 214         }
 215
 216         emptyHash := bc.Hash{}
 217         if voteResult.LastBlockHash != emptyHash && voteResult.LastBlockHash != block.PreviousBlockHash {
 218                 return errors.New("bbft append block error, the block parent hash is not equals last block hash of vote result")
 219         }
 220
 221         for _, tx := range block.Transactions {
 222                 for _, input := range tx.Inputs {
 223                         unVoteInput, ok := input.TypedInput.(*types.UnvoteInput)
 224                         if !ok {
 225                                 continue
 226                         }
 227
 228                         pubkey := hex.EncodeToString(unVoteInput.Vote)
 229                         voteResult.NumOfVote[pubkey], ok = checked.SubUint64(voteResult.NumOfVote[pubkey], unVoteInput.Amount)
 230                         if !ok {
 231                                 return errVotingOperationOverFlow
 232                         }
 233                 }
 234                 for _, output := range tx.Outputs {
 235                         voteOutput, ok := output.TypedOutput.(*types.VoteTxOutput)
 236                         if !ok {
 237                                 continue
 238                         }
 239
 240                         pubkey := hex.EncodeToString(voteOutput.Vote)
 241                         voteResult.NumOfVote[pubkey], ok = checked.AddUint64(voteResult.NumOfVote[pubkey], voteOutput.Amount)
 242                         if !ok {
 243                                 return errVotingOperationOverFlow
 244                         }
 245                 }
 246         }
 247
 248         voteResult.Finalized = (block.Height+1)%consensus.RoundVoteBlockNums == 0
 249         return nil
 250 }
 251
 252 func (c *consensusNodeManager) getVoteResult(voteResultMap map[uint64]*state.VoteResult, blockHeight uint64) (*state.VoteResult, error) {
 253         var err error
 254         // This round of voting prepares for the next round
 255         seq := blockHeight/consensus.RoundVoteBlockNums + 1
 256         voteResult := voteResultMap[seq]
 257         if blockHeight == 0 {
 258                 voteResult = &state.VoteResult{
 259                         Seq:       seq,
 260                         NumOfVote: make(map[string]uint64),
 261                         Finalized: false,
 262                 }
 263         }
 264
 265         if voteResult == nil {
 266                 prevVoteResult := voteResultMap[seq-1]
 267                 if prevVoteResult != nil {
 268                         voteResult = &state.VoteResult{
 269                                 Seq:       seq,
 270                                 NumOfVote: prevVoteResult.NumOfVote,
 271                                 Finalized: false,
 272                         }
 273                 }
 274         }
 275
 276         if voteResult == nil {
 277                 voteResult, err = c.store.GetVoteResult(seq)
 278                 if err != nil && err != ErrNotFoundVoteResult {
 279                         return nil, err
 280                 }
 281         }
 282
 283         if voteResult == nil {
 284                 voteResult, err = c.store.GetVoteResult(seq - 1)
 285                 if err != nil && err != ErrNotFoundVoteResult {
 286                         return nil, err
 287                 }
 288
 289                 if voteResult != nil {
 290                         // previous round voting must have finalized
 291                         if !voteResult.Finalized {
 292                                 return nil, errors.New("previous round voting has not finalized")
 293                         }
 294
 295                         voteResult.Seq = seq
 296                         voteResult.Finalized = false
 297                         voteResult.LastBlockHash = bc.Hash{}
 298                 }
 299         }
 300
 301         if voteResult == nil {
 302                 return nil, errors.New("fail to get vote result")
 303         }
 304
 305         voteResultMap[seq] = voteResult
 306         return voteResult, nil
 307 }
 308
 309 func (c *consensusNodeManager) detachBlock(voteResultMap map[uint64]*state.VoteResult, block *types.Block) error {
 310         voteSeq := block.Height / consensus.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 initConsensusNodes() 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 }