aboutsummaryrefslogtreecommitdiffstats
path: root/vendor/github.com/dexon-foundation/dexon-consensus/core/lattice-data.go
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/dexon-foundation/dexon-consensus/core/lattice-data.go')
-rw-r--r--vendor/github.com/dexon-foundation/dexon-consensus/core/lattice-data.go683
1 files changed, 0 insertions, 683 deletions
diff --git a/vendor/github.com/dexon-foundation/dexon-consensus/core/lattice-data.go b/vendor/github.com/dexon-foundation/dexon-consensus/core/lattice-data.go
deleted file mode 100644
index 0bbe8902a..000000000
--- a/vendor/github.com/dexon-foundation/dexon-consensus/core/lattice-data.go
+++ /dev/null
@@ -1,683 +0,0 @@
-// Copyright 2018 The dexon-consensus Authors
-// This file is part of the dexon-consensus library.
-//
-// The dexon-consensus library is free software: you can redistribute it
-// and/or modify it under the terms of the GNU Lesser General Public License as
-// published by the Free Software Foundation, either version 3 of the License,
-// or (at your option) any later version.
-//
-// The dexon-consensus library is distributed in the hope that it will be
-// useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser
-// General Public License for more details.
-//
-// You should have received a copy of the GNU Lesser General Public License
-// along with the dexon-consensus library. If not, see
-// <http://www.gnu.org/licenses/>.
-
-package core
-
-import (
- "errors"
- "fmt"
- "sort"
- "time"
-
- "github.com/dexon-foundation/dexon-consensus/common"
- "github.com/dexon-foundation/dexon-consensus/core/db"
- "github.com/dexon-foundation/dexon-consensus/core/types"
- "github.com/dexon-foundation/dexon-consensus/core/utils"
-)
-
-// Errors for sanity check error.
-var (
- ErrDuplicatedAckOnOneChain = fmt.Errorf("duplicated ack on one chain")
- ErrInvalidProposerID = fmt.Errorf("invalid proposer id")
- ErrInvalidWitness = fmt.Errorf("invalid witness data")
- ErrInvalidBlock = fmt.Errorf("invalid block")
- ErrNotAckParent = fmt.Errorf("not ack parent")
- ErrDoubleAck = fmt.Errorf("double ack")
- ErrAcksNotSorted = fmt.Errorf("acks not sorted")
- ErrInvalidBlockHeight = fmt.Errorf("invalid block height")
- ErrAlreadyInLattice = fmt.Errorf("block already in lattice")
- ErrIncorrectBlockTime = fmt.Errorf("block timestamp is incorrect")
- ErrInvalidRoundID = fmt.Errorf("invalid round id")
- ErrUnknownRoundID = fmt.Errorf("unknown round id")
- ErrRoundOutOfRange = fmt.Errorf("round out of range")
- ErrRoundNotSwitch = fmt.Errorf("round not switch")
- ErrNotGenesisBlock = fmt.Errorf("not a genesis block")
- ErrUnexpectedGenesisBlock = fmt.Errorf("unexpected genesis block")
-)
-
-// ErrAckingBlockNotExists is for sanity check error.
-type ErrAckingBlockNotExists struct {
- hash common.Hash
-}
-
-func (e ErrAckingBlockNotExists) Error() string {
- return fmt.Sprintf("acking block %s not exists", e.hash.String()[:6])
-}
-
-// Errors for method usage
-var (
- ErrRoundNotIncreasing = errors.New("round not increasing")
- ErrPurgedBlockNotFound = errors.New("purged block not found")
- ErrPurgeNotDeliveredBlock = errors.New("not purge from head")
-)
-
-// latticeDataConfig is the configuration for latticeData for each round.
-type latticeDataConfig struct {
- roundBasedConfig
- // Number of chains between runs
- numChains uint32
- // Block interval specifies reasonable time difference between
- // parent/child blocks.
- minBlockTimeInterval time.Duration
-}
-
-// Initiate latticeDataConfig from types.Config.
-func (config *latticeDataConfig) fromConfig(roundID uint64, cfg *types.Config) {
- config.numChains = cfg.NumChains
- config.minBlockTimeInterval = cfg.MinBlockInterval
- config.setupRoundBasedFields(roundID, cfg)
-}
-
-// isValidBlockTime checks if timestamp of a block is valid according to a
-// reference time.
-func (config *latticeDataConfig) isValidBlockTime(
- b *types.Block, ref time.Time) bool {
- return !b.Timestamp.Before(ref.Add(config.minBlockTimeInterval))
-}
-
-// isValidGenesisBlockTime checks if a timestamp is valid for a genesis block.
-func (config *latticeDataConfig) isValidGenesisBlockTime(b *types.Block) bool {
- return !b.Timestamp.Before(config.roundBeginTime)
-}
-
-// newLatticeDataConfig constructs a latticeDataConfig instance.
-func newLatticeDataConfig(
- prev *latticeDataConfig, cur *types.Config) *latticeDataConfig {
- c := &latticeDataConfig{}
- c.fromConfig(prev.roundID+1, cur)
- c.setRoundBeginTime(prev.roundEndTime)
- return c
-}
-
-// latticeData is a module for storing lattice.
-type latticeData struct {
- // DB for getting blocks purged in memory.
- db db.Database
- // chains stores chains' blocks and other info.
- chains []*chainStatus
- // blockByHash stores blocks, indexed by block hash.
- blockByHash map[common.Hash]*types.Block
- // This stores configuration for each round.
- configs []*latticeDataConfig
- // shallowBlocks stores the hash of blocks that their body is not receive yet.
- shallowBlocks map[common.Hash]types.Position
-}
-
-// newLatticeData creates a new latticeData instance.
-func newLatticeData(
- db db.Database,
- dMoment time.Time,
- round uint64,
- config *types.Config) (data *latticeData) {
-
- genesisConfig := &latticeDataConfig{}
- genesisConfig.fromConfig(round, config)
- genesisConfig.setRoundBeginTime(dMoment)
- data = &latticeData{
- db: db,
- chains: make([]*chainStatus, genesisConfig.numChains),
- blockByHash: make(map[common.Hash]*types.Block),
- configs: []*latticeDataConfig{genesisConfig},
- shallowBlocks: make(map[common.Hash]types.Position),
- }
- for i := range data.chains {
- data.chains[i] = &chainStatus{
- ID: uint32(i),
- blocks: []*types.Block{},
- lastAckPos: make([]*types.Position, genesisConfig.numChains),
- }
- }
- return
-}
-
-func (data *latticeData) addShallowBlock(hash common.Hash, pos types.Position) {
- // We don't care other errors here. This `if` is to prevent being spammed by
- // very old blocks.
- if _, err := data.findBlock(hash); err != db.ErrBlockDoesNotExist {
- return
- }
- data.shallowBlocks[hash] = pos
-}
-
-func (data *latticeData) checkAckingRelations(
- b *types.Block, allowShallow bool) error {
- acksByChainID := make(map[uint32]struct{}, len(data.chains))
- for _, hash := range b.Acks {
- bAck, err := data.findBlock(hash)
- if err != nil {
- if err == db.ErrBlockDoesNotExist {
- err = &ErrAckingBlockNotExists{hash}
- if allowShallow {
- if pos, exist := data.shallowBlocks[hash]; exist {
- bAck = &types.Block{
- Position: pos,
- }
- err = nil
- }
- }
- }
- if err != nil {
- return err
- }
- }
- // Check if it acks blocks from old rounds, the allowed round difference
- // is 1.
- if DiffUint64(bAck.Position.Round, b.Position.Round) > 1 {
- return ErrRoundOutOfRange
- }
- // Check if it acks older blocks than blocks on the same chain.
- lastAckPos :=
- data.chains[bAck.Position.ChainID].lastAckPos[b.Position.ChainID]
- if lastAckPos != nil && !bAck.Position.Newer(lastAckPos) {
- return ErrDoubleAck
- }
- // Check if it acks two blocks on the same chain. This would need
- // to check after we replace map with slice for acks.
- if _, acked := acksByChainID[bAck.Position.ChainID]; acked {
- return ErrDuplicatedAckOnOneChain
- }
- acksByChainID[bAck.Position.ChainID] = struct{}{}
- }
- return nil
-}
-
-func (data *latticeData) sanityCheck(b *types.Block, allowShallow bool) error {
- // TODO(mission): Check if its proposer is in validator set, lattice has no
- // knowledge about node set.
- config := data.getConfig(b.Position.Round)
- if config == nil {
- return ErrInvalidRoundID
- }
- // Check if the chain id is valid.
- if b.Position.ChainID >= config.numChains {
- return utils.ErrInvalidChainID
- }
- // Make sure parent block is arrived.
- chain := data.chains[b.Position.ChainID]
- chainTip := chain.tip
- if chainTip == nil {
- if !b.ParentHash.Equal(common.Hash{}) {
- return &ErrAckingBlockNotExists{b.ParentHash}
- }
- if !b.IsGenesis() {
- return ErrNotGenesisBlock
- }
- if !config.isValidGenesisBlockTime(b) {
- return ErrIncorrectBlockTime
- }
- return data.checkAckingRelations(b, allowShallow)
- }
- // Check parent block if parent hash is specified.
- if !b.ParentHash.Equal(common.Hash{}) {
- if !b.ParentHash.Equal(chainTip.Hash) {
- return &ErrAckingBlockNotExists{b.ParentHash}
- }
- if !b.IsAcking(b.ParentHash) {
- return ErrNotAckParent
- }
- }
- chainTipConfig := data.getConfig(chainTip.Position.Round)
- // Round can't be rewinded.
- if chainTip.Position.Round > b.Position.Round {
- return ErrInvalidRoundID
- }
- checkTip := false
- if chainTip.Timestamp.After(chainTipConfig.roundEndTime) {
- // Round switching should happen when chainTip already pass
- // round end time of its round.
- if chainTip.Position.Round == b.Position.Round {
- return ErrRoundNotSwitch
- }
- // The round ID is continuous.
- if b.Position.Round-chainTip.Position.Round == 1 {
- checkTip = true
- } else {
- // This block should be genesis block of new round because round
- // ID is not continuous.
- if !b.IsGenesis() {
- return ErrNotGenesisBlock
- }
- if !config.isValidGenesisBlockTime(b) {
- return ErrIncorrectBlockTime
- }
- // TODO(mission): make sure rounds between chainTip and current block
- // don't expect blocks from this chain.
- }
- } else {
- if chainTip.Position.Round != b.Position.Round {
- // Round should not switch.
- return ErrInvalidRoundID
- }
- checkTip = true
- }
- // Validate the relation between chain tip when needed.
- if checkTip {
- if b.Position.Height != chainTip.Position.Height+1 {
- return ErrInvalidBlockHeight
- }
- if b.Witness.Height < chainTip.Witness.Height {
- return ErrInvalidWitness
- }
- if !config.isValidBlockTime(b, chainTip.Timestamp) {
- return ErrIncorrectBlockTime
- }
- // Chain tip should be acked.
- if !b.IsAcking(chainTip.Hash) {
- return ErrNotAckParent
- }
- }
- return data.checkAckingRelations(b, allowShallow)
-}
-
-// addBlock processes blocks. It does sanity check, inserts block into lattice
-// and deletes blocks which will not be used.
-func (data *latticeData) addBlock(
- block *types.Block) (deliverable []*types.Block, err error) {
- var (
- bAck *types.Block
- updated bool
- )
- if err = data.db.PutBlock(*block); err != nil {
- if err == db.ErrBlockExists {
- // If a node is crashed and restarted, we might encounter some
- // blocks that already confirmed but not delivered yet. Then
- // syncer might still try to add that block in this way.
- err = nil
- } else {
- return
- }
- }
- data.chains[block.Position.ChainID].addBlock(block)
- data.blockByHash[block.Hash] = block
- // Update lastAckPos.
- for _, ack := range block.Acks {
- if bAck, err = data.findBlock(ack); err != nil {
- return
- }
- data.chains[bAck.Position.ChainID].lastAckPos[block.Position.ChainID] =
- bAck.Position.Clone()
- }
- // Extract deliverable blocks to total ordering. A block is deliverable to
- // total ordering iff all its ackings blocks were delivered to total ordering.
- for {
- updated = false
- for _, status := range data.chains {
- if status.nextOutputIndex >= len(status.blocks) {
- continue
- }
- tip := status.blocks[status.nextOutputIndex]
- allAckingBlockDelivered := true
- for _, ack := range tip.Acks {
- if bAck, err = data.findBlock(ack); err != nil {
- if err == db.ErrBlockDoesNotExist {
- err = nil
- allAckingBlockDelivered = false
- break
- }
- return
- }
- // Check if this block is outputed or not.
- idx := data.chains[bAck.Position.ChainID].findBlock(&bAck.Position)
- var ok bool
- if idx == -1 {
- // Either the block is delivered or not added to chain yet.
- if out :=
- data.chains[bAck.Position.ChainID].lastOutputPosition; out != nil {
- ok = !out.Older(&bAck.Position)
- } else if ackTip :=
- data.chains[bAck.Position.ChainID].tip; ackTip != nil {
- ok = !ackTip.Position.Older(&bAck.Position)
- }
- } else {
- ok = idx < data.chains[bAck.Position.ChainID].nextOutputIndex
- }
- if ok {
- continue
- }
- // This acked block exists and not delivered yet.
- allAckingBlockDelivered = false
- }
- if allAckingBlockDelivered {
- status.lastOutputPosition = &tip.Position
- status.nextOutputIndex++
- deliverable = append(deliverable, tip)
- updated = true
- }
- }
- if !updated {
- break
- }
- }
- return
-}
-
-// addFinalizedBlock processes block for syncing internal data.
-func (data *latticeData) addFinalizedBlock(block *types.Block) (err error) {
- var bAck *types.Block
- chain := data.chains[block.Position.ChainID]
- if chain.tip != nil && chain.tip.Position.Height >= block.Position.Height {
- return
- }
- chain.nextOutputIndex = 0
- chain.blocks = []*types.Block{}
- chain.tip = block
- chain.lastOutputPosition = nil
- // Update lastAckPost.
- for _, ack := range block.Acks {
- if bAck, err = data.findBlock(ack); err != nil {
- return
- }
- data.chains[bAck.Position.ChainID].lastAckPos[block.Position.ChainID] =
- bAck.Position.Clone()
- }
- return
-}
-
-func (data *latticeData) tipRound(chainID uint32) uint64 {
- if tip := data.chains[chainID].tip; tip != nil {
- tipConfig := data.getConfig(tip.Position.Round)
- offset := uint64(0)
- if tip.Timestamp.After(tipConfig.roundEndTime) {
- offset++
- }
- return tip.Position.Round + offset
- }
- return uint64(0)
-
-}
-
-// isBindTip checks if a block's fields should follow up its parent block.
-func (data *latticeData) isBindTip(
- pos types.Position, tip *types.Block) (bindTip bool, err error) {
- if tip == nil {
- return
- }
- if pos.Round < tip.Position.Round {
- err = ErrInvalidRoundID
- return
- }
- tipConfig := data.getConfig(tip.Position.Round)
- if tip.Timestamp.After(tipConfig.roundEndTime) {
- if pos.Round == tip.Position.Round {
- err = ErrRoundNotSwitch
- return
- }
- if pos.Round == tip.Position.Round+1 {
- bindTip = true
- }
- } else {
- if pos.Round != tip.Position.Round {
- err = ErrInvalidRoundID
- return
- }
- bindTip = true
- }
- return
-}
-
-// prepareBlock setups fields of a block based on its ChainID and Round,
-// including:
-// - Acks
-// - Timestamp
-// - ParentHash and Height from parent block. If there is no valid parent block
-// (e.g. Newly added chain or bootstrap), these fields should be setup as
-// genesis block.
-func (data *latticeData) prepareBlock(b *types.Block) error {
- var (
- minTimestamp time.Time
- config *latticeDataConfig
- acks common.Hashes
- bindTip bool
- )
- if config = data.getConfig(b.Position.Round); config == nil {
- return ErrUnknownRoundID
- }
- // If chainID is illegal in this round, reject it.
- if b.Position.ChainID >= config.numChains {
- return utils.ErrInvalidChainID
- }
- // Reset fields to make sure we got these information from parent block.
- b.Position.Height = 0
- b.ParentHash = common.Hash{}
- // Decide valid timestamp range.
- chainTip := data.chains[b.Position.ChainID].tip
- if chainTip != nil {
- // TODO(mission): find a way to prevent us to assign a witness height
- // from Jurassic period.
- b.Witness.Height = chainTip.Witness.Height
- }
- bindTip, err := data.isBindTip(b.Position, chainTip)
- if err != nil {
- return err
- }
- // For blocks with continuous round ID, assign timestamp range based on
- // parent block and bound config.
- if bindTip {
- minTimestamp = chainTip.Timestamp.Add(config.minBlockTimeInterval)
- // When a chain is removed and added back, the reference block
- // of previous round can't be used as parent block.
- b.ParentHash = chainTip.Hash
- b.Position.Height = chainTip.Position.Height + 1
- } else {
- // Discontinuous round ID detected, another fresh start of
- // new round.
- minTimestamp = config.roundBeginTime
- }
- // Fix timestamp if the given one is invalid.
- if b.Timestamp.Before(minTimestamp) {
- b.Timestamp = minTimestamp
- }
- // Setup acks fields.
- for _, status := range data.chains {
- // Check if we can ack latest block on that chain.
- if status.tip == nil {
- continue
- }
- lastAckPos := status.lastAckPos[b.Position.ChainID]
- if lastAckPos != nil && !status.tip.Position.Newer(lastAckPos) {
- // The reference block is already acked.
- continue
- }
- if status.tip.Position.Round > b.Position.Round {
- // Avoid forward acking: acking some block from later rounds.
- continue
- }
- if b.Position.Round > status.tip.Position.Round+1 {
- // Can't ack block too old or too new to us.
- continue
- }
- acks = append(acks, status.tip.Hash)
- }
- b.Acks = common.NewSortedHashes(acks)
- return nil
-}
-
-// prepareEmptyBlock setups fields of a block based on its ChainID.
-// including:
-// - Acks only acking its parent
-// - Timestamp with parent.Timestamp + minBlockProposeInterval
-// - ParentHash and Height from parent block. If there is no valid parent block
-// (ex. Newly added chain or bootstrap), these fields would be setup as
-// genesis block.
-func (data *latticeData) prepareEmptyBlock(b *types.Block) (err error) {
- // emptyBlock has no proposer.
- b.ProposerID = types.NodeID{}
- // Reset fields to make sure we got these information from parent block.
- b.Position.Height = 0
- b.ParentHash = common.Hash{}
- b.Timestamp = time.Time{}
- // Decide valid timestamp range.
- config := data.getConfig(b.Position.Round)
- chainTip := data.chains[b.Position.ChainID].tip
- bindTip, err := data.isBindTip(b.Position, chainTip)
- if err != nil {
- return
- }
- if bindTip {
- b.ParentHash = chainTip.Hash
- b.Position.Height = chainTip.Position.Height + 1
- b.Timestamp = chainTip.Timestamp.Add(config.minBlockTimeInterval)
- b.Witness.Height = chainTip.Witness.Height
- b.Witness.Data = make([]byte, len(chainTip.Witness.Data))
- copy(b.Witness.Data, chainTip.Witness.Data)
- b.Acks = common.NewSortedHashes(common.Hashes{chainTip.Hash})
- } else {
- b.Timestamp = config.roundBeginTime
- }
- return
-}
-
-// TODO(mission): make more abstraction for this method.
-// nextBlock returns the next height and timestamp of a chain.
-func (data *latticeData) nextBlock(
- round uint64, chainID uint32) (uint64, time.Time, error) {
- chainTip := data.chains[chainID].tip
- bindTip, err := data.isBindTip(
- types.Position{Round: round, ChainID: chainID}, chainTip)
- if err != nil {
- return 0, time.Time{}, err
- }
- config := data.getConfig(round)
- if bindTip {
- return chainTip.Position.Height + 1,
- chainTip.Timestamp.Add(config.minBlockTimeInterval), nil
- }
- return 0, config.roundBeginTime, nil
-}
-
-// findBlock seeks blocks in memory or db.
-func (data *latticeData) findBlock(h common.Hash) (b *types.Block, err error) {
- if b = data.blockByHash[h]; b != nil {
- return
- }
- var tmpB types.Block
- if tmpB, err = data.db.GetBlock(h); err != nil {
- return
- }
- b = &tmpB
- return
-}
-
-// purgeBlocks purges blocks from cache.
-func (data *latticeData) purgeBlocks(blocks []*types.Block) error {
- for _, b := range blocks {
- if _, exists := data.blockByHash[b.Hash]; !exists {
- return ErrPurgedBlockNotFound
- }
- delete(data.blockByHash, b.Hash)
- // Blocks are purged in ascending order by position.
- if err := data.chains[b.Position.ChainID].purgeBlock(b); err != nil {
- return err
- }
- }
- return nil
-}
-
-// getConfig get configuration for lattice-data by round ID.
-func (data *latticeData) getConfig(round uint64) (config *latticeDataConfig) {
- r := data.configs[0].roundID
- if round < r || round >= r+uint64(len(data.configs)) {
- return
- }
- return data.configs[round-r]
-}
-
-// appendConfig appends a configuration for upcoming round. Rounds appended
-// should be consecutive.
-func (data *latticeData) appendConfig(
- round uint64, config *types.Config) (err error) {
- // Check if the round of config is increasing by 1.
- if round != uint64(len(data.configs))+data.configs[0].roundID {
- return ErrRoundNotIncreasing
- }
- // Set round beginning time.
- newConfig := newLatticeDataConfig(data.configs[len(data.configs)-1], config)
- data.configs = append(data.configs, newConfig)
- // Resize each slice if incoming config contains larger number of chains.
- if uint32(len(data.chains)) < newConfig.numChains {
- count := newConfig.numChains - uint32(len(data.chains))
- for _, status := range data.chains {
- status.lastAckPos = append(
- status.lastAckPos, make([]*types.Position, count)...)
- }
- for i := uint32(len(data.chains)); i < newConfig.numChains; i++ {
- data.chains = append(data.chains, &chainStatus{
- ID: i,
- blocks: []*types.Block{},
- lastAckPos: make([]*types.Position, newConfig.numChains),
- })
- }
- }
- return nil
-}
-
-type chainStatus struct {
- // ID keeps the chainID of this chain status.
- ID uint32
- // blocks stores blocks proposed for this chain, sorted by height.
- blocks []*types.Block
- // tip is the last block on this chain.
- tip *types.Block
- // lastAckPos caches last acking position from other chains. Nil means
- // not acked yet.
- lastAckPos []*types.Position
- // the index to be output next time.
- nextOutputIndex int
- // the position of output last time.
- lastOutputPosition *types.Position
-}
-
-// findBlock finds index of block in current pending blocks on this chain.
-// Return -1 if not found.
-func (s *chainStatus) findBlock(pos *types.Position) (idx int) {
- idx = sort.Search(len(s.blocks), func(i int) bool {
- return s.blocks[i].Position.Newer(pos) ||
- s.blocks[i].Position.Equal(pos)
- })
- if idx == len(s.blocks) {
- idx = -1
- } else if !s.blocks[idx].Position.Equal(pos) {
- idx = -1
- }
- return idx
-}
-
-// getBlock returns a pending block by giving its index from findBlock method.
-func (s *chainStatus) getBlock(idx int) (b *types.Block) {
- if idx < 0 || idx >= len(s.blocks) {
- return
- }
- b = s.blocks[idx]
- return
-}
-
-// addBlock adds a block to pending blocks on this chain.
-func (s *chainStatus) addBlock(b *types.Block) {
- s.blocks = append(s.blocks, b)
- s.tip = b
-}
-
-// purgeBlock purges a block from cache, make sure this block is already saved
-// in db.
-func (s *chainStatus) purgeBlock(b *types.Block) error {
- if b.Hash != s.blocks[0].Hash || s.nextOutputIndex <= 0 {
- return ErrPurgeNotDeliveredBlock
- }
- s.blocks = s.blocks[1:]
- s.nextOutputIndex--
- return nil
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-23 18:16:03 +0800