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