blockPrefix = []byte("B:")
blockHeaderPrefix = []byte("BH:")
txStatusPrefix = []byte("BTS:")
+ voteResultPrefix = []byte("VR:")
)
func loadBlockStoreStateJSON(db dbm.DB) *protocol.BlockStoreState {
return append(txStatusPrefix, hash.Bytes()...)
}
+func calcVoteResultKey(seq uint64) []byte {
+ buf := [8]byte{}
+ binary.BigEndian.PutUint64(buf[:], seq)
+ return append(voteResultPrefix, buf[:]...)
+}
+
// GetBlock return the block by given hash
func GetBlock(db dbm.DB, hash *bc.Hash) (*types.Block, error) {
bytez := db.Get(calcBlockKey(hash))
return loadBlockStoreStateJSON(s.db)
}
+// GetVoteResult retrive the voting result in specified vote sequence
+func (s *Store) GetVoteResult(seq uint64) (*state.VoteResult, error) {
+ data := s.db.Get(calcVoteResultKey(seq))
+ if data == nil {
+ return nil, errors.New("can't find the vote result by given sequence")
+ }
+
+ vr := &state.VoteResult{}
+ if err := json.Unmarshal(data, vr); err != nil {
+ return nil, errors.Wrap(err, "unmarshaling vote result")
+ }
+ return vr, nil
+}
+
func (s *Store) LoadBlockIndex(stateBestHeight uint64) (*state.BlockIndex, error) {
startTime := time.Now()
blockIndex := state.NewBlockIndex()
batch.Write()
return nil
}
+
+// SaveVoteResult update the voting results generated by each irreversible block
+func (s *Store) SaveVoteResult(vr *state.VoteResult) error {
+ bytes, err := json.Marshal(vr)
+ if err != nil {
+ return err
+ }
+
+ s.db.Set(calcVoteResultKey(vr.Seq), bytes)
+ return nil
+}
--- /dev/null
+package bbft
+
+import (
+ "time"
+
+ "github.com/vapor/crypto/ed25519"
+ "github.com/vapor/errors"
+ "github.com/vapor/protocol/bc"
+ "github.com/vapor/protocol"
+ "github.com/vapor/database"
+)
+
+type bbft struct {
+ consensusNodeManager *consensusNodeManager
+}
+
+func newBbft(store *database.Store, chain *protocol.Chain) *bbft {
+ return &bbft{
+ consensusNodeManager: newConsensusNodeManager(store, chain),
+ }
+}
+
+// IsConsensusPubkey determine whether a public key is a consensus node at a specified height
+func (b *bbft) IsConsensusPubkey(height uint64, pubkey []byte) (bool, error) {
+ return b.consensusNodeManager.isConsensusPubkey(height, pubkey)
+}
+
+// NextLeaderTime returns the start time of the specified public key as the next leader node
+func (b *bbft) NextLeaderTime(pubkey []byte) (*time.Time, error) {
+ return b.consensusNodeManager.nextLeaderTime(pubkey)
+}
+
+// ValidateSign verify the signature of block id
+func (b *bbft) ValidateSign(blockID bc.Hash, pubkey, sign []byte) error {
+ if ok := ed25519.Verify(ed25519.PublicKey(pubkey), blockID.Bytes(), sign); !ok {
+ return errors.New("validate block signature fail")
+ }
+ return nil
+}
--- /dev/null
+package bbft
+
+import (
+ "encoding/hex"
+ "fmt"
+ "sort"
+ "sync"
+ "time"
+
+ "github.com/vapor/database"
+ "github.com/vapor/errors"
+ "github.com/vapor/protocol"
+)
+
+const (
+ numOfConsensusNode = 21
+ roundVoteBlockNums = 1000
+
+ // product one block per 500 milliseconds
+ blockTimeInterval = 500
+ blockNumEachNode = 3
+)
+
+var (
+ errHasNoChanceProductBlock = errors.New("the node has no chance to product a block in this round of voting")
+)
+
+type consensusNode struct {
+ pubkey string
+ voteNum uint64
+ order uint64
+}
+
+type consensusNodeSlice []*consensusNode
+
+func (c consensusNodeSlice) Len() int { return len(c) }
+func (c consensusNodeSlice) Less(i, j int) bool { return c[i].voteNum > c[j].voteNum }
+func (c consensusNodeSlice) Swap(i, j int) { c[i], c[j] = c[j], c[i] }
+
+type consensusNodeManager struct {
+ consensusNodeMap map[string]*consensusNode
+ effectiveStartHeight uint64
+ store *database.Store
+ chain *protocol.Chain
+ sync.RWMutex
+}
+
+func newConsensusNodeManager(store *database.Store, chain *protocol.Chain) *consensusNodeManager {
+ return &consensusNodeManager{
+ consensusNodeMap: make(map[string]*consensusNode),
+ effectiveStartHeight: 1,
+ chain: chain,
+ store: store,
+ }
+}
+
+func (c *consensusNodeManager) isConsensusPubkey(height uint64, pubkey []byte) (bool, error) {
+ defer c.RUnlock()
+ c.RLock()
+ if height >= c.effectiveStartHeight + roundVoteBlockNums {
+ return false, errors.New("the vote has not been completed for the specified block height ")
+ }
+
+ var err error
+ consensusNodeMap := c.consensusNodeMap
+ // query history vote result
+ if height < c.effectiveStartHeight {
+ consensusNodeMap, err = c.getConsensusNodesByVoteResult(height / roundVoteBlockNums)
+ if err != nil {
+ return false, err
+ }
+ }
+
+ encodePubkey := hex.EncodeToString(pubkey)
+ _, exist := consensusNodeMap[encodePubkey]
+ return exist, nil
+}
+
+func (c *consensusNodeManager) nextLeaderTime(pubkey []byte) (*time.Time, error) {
+ defer c.RLock()
+ c.RLock()
+
+ encodePubkey := hex.EncodeToString(pubkey)
+ consensusNode, ok := c.consensusNodeMap[encodePubkey]
+ if !ok {
+ return nil, fmt.Errorf("pubkey:%s is not consensus node", encodePubkey)
+ }
+
+ startBlockHeight := c.effectiveStartHeight
+ bestBlockHeight := c.chain.BestBlockHeight()
+
+ prevRoundLastBlock, err := c.chain.GetHeaderByHeight(startBlockHeight - 1)
+ if err != nil {
+ return nil, err
+ }
+
+ startTime := prevRoundLastBlock.Timestamp * 1000 + blockTimeInterval
+ return nextLeaderTimeHelper(startBlockHeight, bestBlockHeight, startTime, consensusNode.order)
+}
+
+func nextLeaderTimeHelper(startBlockHeight, bestBlockHeight, startTime, nodeOrder uint64) (*time.Time, error) {
+ endBlockHeight := startBlockHeight + roundVoteBlockNums
+ // exclude genesis block
+ if startBlockHeight == 1 {
+ endBlockHeight--
+ }
+
+ roundBlockNums := uint64(blockNumEachNode * numOfConsensusNode)
+ latestRoundBlockHeight := startBlockHeight + (bestBlockHeight - startBlockHeight) / roundBlockNums * roundBlockNums
+ nextBlockHeight := latestRoundBlockHeight + blockNumEachNode * nodeOrder
+
+ if int64(bestBlockHeight - nextBlockHeight) >= blockNumEachNode {
+ nextBlockHeight += roundBlockNums
+ if nextBlockHeight > endBlockHeight {
+ return nil, errHasNoChanceProductBlock
+ }
+ }
+
+ nextLeaderTimestamp := int64(startTime + (nextBlockHeight - startBlockHeight) * blockTimeInterval)
+ nextLeaderTime := time.Unix(nextLeaderTimestamp / 1000, (nextLeaderTimestamp % 1000) * 1e6)
+ return &nextLeaderTime, nil
+}
+
+// UpdateConsensusNodes used to update consensus node after each round of voting
+func (c *consensusNodeManager) UpdateConsensusNodes(voteSeq uint64) error {
+ defer c.Unlock()
+ c.Lock()
+ if voteSeq <= c.effectiveStartHeight / roundVoteBlockNums {
+ return nil
+ }
+
+ consensusNodeMap, err := c.getConsensusNodesByVoteResult(voteSeq)
+ if err != nil {
+ return err
+ }
+
+ c.consensusNodeMap = consensusNodeMap
+ c.effectiveStartHeight = voteSeq * roundVoteBlockNums
+ return nil
+}
+
+func (c *consensusNodeManager) getConsensusNodesByVoteResult(voteSeq uint64) (map[string]*consensusNode, error) {
+ voteResult, err := c.store.GetVoteResult(voteSeq)
+ if err != nil {
+ return nil, err
+ }
+
+ if !voteResult.Finalized {
+ return nil, errors.New("vote result is not finalized")
+ }
+
+ var nodes []*consensusNode
+ for pubkey, voteNum := range voteResult.NumOfVote {
+ nodes = append(nodes, &consensusNode{
+ pubkey: pubkey,
+ voteNum: voteNum,
+ })
+ }
+ // In principle, there is no need to sort all voting nodes.
+ // if there is a performance problem, consider the optimization later.
+ // TODO not consider the same number of votes
+ sort.Sort(consensusNodeSlice(nodes))
+
+ result := make(map[string]*consensusNode)
+ for i, node := range nodes {
+ node.order = uint64(i)
+ result[node.pubkey] = node
+ }
+ return result, nil
+}
--- /dev/null
+package bbft
+
+import (
+ "testing"
+)
+
+func TestNextLeaderTime(t *testing.T) {
+ cases := []struct {
+ desc string
+ startBlockHeight uint64
+ bestBlockHeight uint64
+ startTime uint64
+ nodeOrder uint64
+ wantError error
+ wantNextLeaderTime int64
+ }{
+ {
+ desc: "normal case",
+ startBlockHeight: 1000,
+ bestBlockHeight: 1500,
+ startTime: 1557906284061,
+ nodeOrder: 1,
+ wantError: nil,
+ wantNextLeaderTime: 1557906537561,
+ },
+ {
+ desc: "best block height equals to start block height",
+ startBlockHeight: 1000,
+ bestBlockHeight: 1000,
+ startTime: 1557906284061,
+ nodeOrder: 0,
+ wantError: nil,
+ wantNextLeaderTime: 1557906284061,
+ },
+ {
+ desc: "best block height equals to start block height",
+ startBlockHeight: 1000,
+ bestBlockHeight: 1000,
+ startTime: 1557906284061,
+ nodeOrder: 1,
+ wantError: nil,
+ wantNextLeaderTime: 1557906284061 + blockNumEachNode * blockTimeInterval,
+ },
+ {
+ desc: "has no chance product block in this round of voting",
+ startBlockHeight: 1000,
+ bestBlockHeight: 1995,
+ startTime: 1557906284061,
+ nodeOrder: 1,
+ wantError: errHasNoChanceProductBlock,
+ wantNextLeaderTime: 0,
+ },
+ {
+ desc: "the node is producting block",
+ startBlockHeight: 1000,
+ bestBlockHeight: 1001,
+ startTime: 1557906284061,
+ nodeOrder: 0,
+ wantError: nil,
+ wantNextLeaderTime: 1557906284061,
+ },
+ {
+ desc: "the node is producting block",
+ startBlockHeight: 1000,
+ bestBlockHeight: 1067,
+ startTime: 1557906284061,
+ nodeOrder: 1,
+ wantError: nil,
+ wantNextLeaderTime: 1557906284061 + 66 * blockTimeInterval,
+ },
+ {
+ desc: "first round, must exclude genesis block",
+ startBlockHeight: 1,
+ bestBlockHeight: 5,
+ startTime: 1557906284061,
+ nodeOrder: 3,
+ wantError: nil,
+ wantNextLeaderTime: 1557906284061 + 9 * blockTimeInterval,
+ },
+ }
+
+ for i, c := range cases {
+ nextLeaderTime, err := nextLeaderTimeHelper(c.startBlockHeight, c.bestBlockHeight, c.startTime, c.nodeOrder)
+ if err != c.wantError {
+ t.Fatalf("case #%d (%s) want error:%v, got error:%v", i, c.desc, c.wantError, err)
+ }
+
+ if err != nil {
+ continue
+ }
+ nextLeaderTimestamp := nextLeaderTime.UnixNano() / 1e6
+ if nextLeaderTimestamp != c.wantNextLeaderTime {
+ t.Errorf("case #%d (%s) want next leader time:%d, got next leader time:%d", i, c.desc, c.wantNextLeaderTime, nextLeaderTimestamp)
+ }
+ }
+}
--- /dev/null
+package state
+
+// VoteResult represents a snapshot of each round of DPOS voting
+// Seq indicates the sequence of current votes, which start from zero
+// NumOfVote indicates the number of votes each consensus node receives, the key of map represent public key
+// LastBlockHeight indicates the last voted block height
+// Finalized indicates whether this vote is finalized
+type VoteResult struct {
+ Seq uint64
+ NumOfVote map[string]uint64
+ LastBlockHeight uint64
+ Finalized bool
+}