Represents simplified view on Altchain's block tree, maintains VBK tree and BTC tree. More...

Detailed Description

Helps Altchain to compare Altchain blocks by POP score in POP Fork Resolution.

Invariant: If POP score of two chains are equal, it expects Altchain to resolve conflict using their native fork resolution algorithm.

AltBlockTree is initialized with Altchain, Veriblock and Bitcoin parameters, as well as with PayloadsStorage implementation.

// use mainnet for all chains, for instance
AltChainParamsMain altp;
VbkChainParamsMain vbkp;
BtcChainParamsMain btcp;
// your implementation of PayloadsStorage
PayloadsProviderImpl provider;
// your implementation of BlockReader
BlockReaderImpl blockProvider
AltBlockTree tree(altp, vbkp, btcp, provider, blockProvider);

After initialization AltBlockTree does not contain any blocks. Users MUST bootstrap AltBlockTree - add initial/genesis/root block of Altchain.

We will refer to this block as bootstrap block. Bootstrap block is a first block in Altchain that can be endorsed, but can not contain POP body (PopData).

If bootstrap() fails, your block provided in struct AltChainParams::getBootstrapBlock() is invalid.

ValidationState will contain detailed info about failure reason, if any.

ValidationState state;
bool ret = tree.bootstrap(state);
assert(ret && "bootstrap is unsuccessful");

Invariant: bootstrap block is immediately finalized - it can not be reorganized.

Whenever any new full block (block with header, block body and PopData) is accepted, users must first add block header to AltBlockTree, then add PopData to this block.

bool onNewFullBlock(AltBlockTree& tree, Block block) {
    ValidationState state;
 
    // first, add block header. if this returns false,
    // header can not be connected (invalid).
    if(!tree.acceptBlockHeader(block.getHeader(), state)) {
        return false;
    }
 
    // then, attach block body (PopData) to block header.
    // if block does not exist, this will fail on assert.
    tree.acceptBlock(block.getHash(), block.getPopData());
 
    // ...

AltBlockTree::acceptBlockHeader() connects block immediately if all previous blocks are connected, or just adds block body to AltBlock when one of previous blocks is not connected.

After that, users can check if this block is connected:

// ...
// this returns nullptr if the block can not be found
auto* blockindex = tree.getBlockIndex(block.getHash());
assert(blockindex && "we added this block to the tree, so it must exist");
 
auto candidates = tree.getConnectedTipsAfter(*blockindex);
if(candidates.empty()) {
  // we have no POP FR candidates
  return true; 
}
 
const auto* tip = tree.getBestChain().tip();
for(const auto* candidate : candidates) {
    // here, we assume that candidate has all txes downloaded and block is fully available
 
    // compare current tip to a candidate
    int result = tree.comparePopScore(tip->getHash(), candidate->getHash());

Note: after AltBlockTree::comparePopScore AltBlockTree always corresponds to a state, as if winner chain have been applied.

        if(result < 0) {
            // candidate has better POP score.
            // tree already switched to candidate chain.
 
            UpdateTip(candidate->getHash());
            // NOTE: update `tip`, otherwise old tip will be passed to first arg,
            // and comparePopScore will die on assert
            tip = candidate;
            return true;
        } else if (result == 0) {
            // tip POP score == candidate POP score
            // tree tip is unchanged
            // fallback to chain-native Fork Resolution algorithm
 
            // in BTC, for example, compare blocks by chainwork
            if(tip->nChainWork < candidate->nChainWork) {
                UpdateTip(candidate->getHash());
            }
            return true;
       } else {
            // candidate is invalid or has worse POP score
            // tree tip is unchanged
            return true;
        }
    } 
} 

Invariant: AltBlockTree::comparePopScore always compares current AltBlockTree tip to other block. To avoid confusion, you must specify tip explicitly as first arg. If incorrect tip is passed, function dies on assert.; AltBlockTree::comparePopScore always leaves AltBlockTree switched to winner (by POP Score) chain.; Current active chain of AltBlockTree always corresponds to an empty tree with all applied blocks from first bootstrap block to current tip, i.e. currently applied active chain and this state MUST be always valid.

When tip is changed, Altchain MUST change state of AltBlockTree:

Note: use AltBlockTree::setState() to switch from current best chain to new block. It can very expensive operation if there's large reorg. If altchain is already at this state, this is a no-op.

void UpdateTip(uint256 bestHash) {
  ValidationState state;
  bool ret = tree.setState(bestHash, state);
  assert(ret && "this block won FR, so it must be valid");
}

Invariant: Current tip of your Altchain tree MUST correspond to tree.getBestChain().tip(), so calling AltBlockTree::setState() ensures they are in sync.

See also: PayloadsStorage; AltChainParams; VbkChainParams; BtcChainParams

Definition at line 178 of file alt_block_tree.hpp.

#include <alt_block_tree.hpp>

Inheritance diagram for altintegration::AltBlockTree:

Collaboration diagram for altintegration::AltBlockTree:

Classes
struct	BlockPayloadMutator
	an incremental block builder More...

Public Types
using	base = BaseBlockTree< AltBlock >

using	alt_config_t = AltChainParams

using	vbk_config_t = VbkChainParams

using	btc_config_t = BtcChainParams

using	index_t = base::index_t

using	stored_index_t = base::stored_index_t

using	endorsement_t = typename index_t::endorsement_t

using	eid_t = typename endorsement_t::id_t

using	hash_t = typename AltBlock::hash_t

using	command_group_store_t = AltCommandGroupStore

using	PopForkComparator = PopAwareForkResolutionComparator< AltBlock, AltChainParams, VbkBlockTree, AltBlockTree >

Public Types inherited from altintegration::BaseBlockTree< AltBlock >
using	block_t = AltBlock

using	block_height_t = typename block_t::height_t

using	hash_t = typename Block::hash_t

using	prev_block_hash_t = typename Block::prev_hash_t

using	index_t = BlockIndex< AltBlock >

using	stored_index_t = StoredBlockIndex< AltBlock >

using	on_invalidate_t = void(const index_t &)

using	block_index_t = std::unordered_map< prev_block_hash_t, std::unique_ptr< index_t > >

Public Member Functions
	AltBlockTree (const alt_config_t &alt_config, const vbk_config_t &vbk_config, const btc_config_t &btc_config, PayloadsStorage &payloadsProvider, BlockReader &blockProvider)

void	bootstrap ()
	Set the very first (bootstrap) altchain block with POP enabled. More...

VBK_CHECK_RETURN bool	acceptBlockHeader (const AltBlock &block, ValidationState &state)
	Validate and add ALT block header to AltBlockTree. More...

void	acceptBlock (const hash_t &block, const PopData &payloads)
	Attach "block body" - PopData to block header, which already exists in AltBlockTree. More...

void	acceptBlock (index_t &index, const PopData &payloads, ValidationState &state)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

void	acceptBlock (index_t &index, const PopData &payloads)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

BlockPayloadMutator	makeConnectedLeafPayloadMutator (index_t &block)
	Create a session object that allows incremental payload list modification in the given block. More...

std::vector< const index_t * >	getConnectedTipsAfter (const index_t &index) const
	Get all connected tips after given block. More...

VBK_CHECK_RETURN bool	loadBlockForward (const stored_index_t &index, bool fast_load, ValidationState &state) override
	Efficiently connect block loaded from disk as a leaf. More...

VBK_CHECK_RETURN bool	loadTip (const hash_t &hash, ValidationState &state) override
	After all blocks loaded, efficiently set current tip. More...

VBK_CHECK_RETURN int	comparePopScore (const AltBlock::hash_t &A, const AltBlock::hash_t &B)
	Efficiently compares current tip (A) and any other block (B). More...

VBK_CHECK_RETURN bool	setState (index_t &to, ValidationState &state) override
	Switch AltBlockTree from the current tip to different block, while doing all validations of intermediate blocks. More...

const VbkBlockTree &	vbk () const
	Accessor for VBK tree. More...

const VbkBlockTree::BtcTree &	btc () const
	Accessor for BTC tree. More...

const AltChainParams &	getParams () const
	Accessor for Network Parameters stored in this tree. More...

Public Member Functions inherited from altintegration::BaseBlockTree< AltBlock >
const std::unordered_set< index_t * > &	getTips () const

std::vector< index_t * >	getBlocks () const

std::vector< index_t * >	getAllBlocks () const

const BlockReader &	getBlockProvider () const

	BaseBlockTree (const BlockReader &blockProvider)

	BaseBlockTree (const BaseBlockTree &)=delete

	BaseBlockTree (BaseBlockTree &&)=default

BaseBlockTree &	operator= (const BaseBlockTree &)=delete

BaseBlockTree &	operator= (BaseBlockTree &&)=default

const Chain< index_t > &	getBestChain () const
	Getter for currently Active Chain. More...

prev_block_hash_t	makePrevHash (const T &h) const

BaseBlockTree< VbkBlock >::prev_block_hash_t	makePrevHash (const hash_t &h) const
	HACK: getBlockIndex accepts either hash_t or prev_block_hash_t then, depending on what it received, it should do trim LE on full hash to receive short hash, which is stored inside a map. More...

index_t *	getBlockIndex (const T &hash)
	Get BlockIndex by block hash. More...

const index_t *	getBlockIndex (const T &hash) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More...

index_t *	findBlockIndex (const T &hash)
	Get BlockIndex by block hash. More...

const index_t *	findBlockIndex (const T &hash) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More...

virtual bool	loadTip (const hash_t &hash, ValidationState &state)

virtual bool	loadBlockForward (const stored_index_t &index, bool fast_load, ValidationState &state)
	Efficiently connects BlockIndex to this tree as a leaf, when it is loaded from disk. More...

void	removeSubtree (index_t &toRemove)
	Removes block and all its successors. More...

void	removeSubtree (const hash_t &toRemove)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More...

void	removeLeaf (index_t &toRemove)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More...

void	invalidateSubtree (index_t &toBeInvalidated, enum BlockValidityStatus reason, bool shouldDetermineBestChain=true)
	Mark given block as invalid. More...

void	invalidateSubtree (const hash_t &toBeInvalidated, enum BlockValidityStatus reason, bool shouldDetermineBestChain=true)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More...

void	revalidateSubtree (const hash_t &hash, enum BlockValidityStatus reason, bool shouldDetermineBestChain=true)

void	revalidateSubtree (index_t &toBeValidated, enum BlockValidityStatus reason, bool shouldDetermineBestChain=true)

bool	isBootstrapped () const
	Check if the blockchain is bootstrapped. More...

virtual bool	setState (const hash_t &block, ValidationState &state)

virtual bool	setState (index_t &index, ValidationState &)

virtual void	overrideTip (index_t &to)

index_t &	getRoot () const

const FinalizedPayloadsIndex< index_t > &	getFinalizedPayloadsIndex () const

const PayloadsIndex< index_t > &	getPayloadsIndex () const

DeferForkResolutionGuard	deferForkResolutionGuard ()

Public Attributes
signals::Signal< void(index_t &index, ValidationState &)>	onInvalidBlockConnected
	a block has been handed over to the underlying tree and flagged as invalid More...

signals::Signal< void(index_t &index)>	onBlockConnected
	a block has been successfully handed over to the underlying tree More...

Public Attributes inherited from altintegration::BaseBlockTree< AltBlock >
signals::Signal< void(const index_t &)>	onBlockBeforeDeallocated
	before we deallocate any block index we emit it to this signal More...

signals::Signal< on_invalidate_t >	onBlockValidityChanged
	signals to the end user that block have been invalidated More...

signals::Signal< void(const index_t &index)>	onBeforeOverrideTip
	chain reorg signal - the tip is being changed More...

Friends
struct	MemPoolBlockTree

Additional Inherited Members
Protected Member Functions inherited from altintegration::BaseBlockTree< AltBlock >
void	deallocateBlock (index_t &block)
	Permanently erases block from a block tree. More...

std::string	toPrettyString (size_t level=0) const

void	decreaseAppliedBlockCount (size_t erasedBlocks)

void	decreaseAppliedBlockCount (size_t)

Protected Attributes inherited from altintegration::BaseBlockTree< AltBlock >
bool	isLoadingBlocks_
	if true, we're in "loading blocks" state More...

bool	isLoaded_
	if true, we can no longer execute loadBlock/loadTip on this tree. More...

block_index_t	blocks_
	stores ALL blocks, including valid and invalid More...

std::unordered_set< index_t * >	tips_
	stores ONLY VALID tips, including currently active tip More...

Chain< index_t >	activeChain_
	currently applied chain More...

FinalizedPayloadsIndex< index_t >	finalizedPayloadsIndex_
	stores mapping of payload id -> its containing ALT/VBK block which are already finalized. More...

PayloadsIndex< index_t >	payloadsIndex_
	stores mapping of payload id -> its containing ALT/VBK blocks which are not yet finalized. More...

const BlockReader &	blockProvider_

Member Typedef Documentation

◆ alt_config_t

using altintegration::AltBlockTree::alt_config_t = AltChainParams

Definition at line 180 of file alt_block_tree.hpp.

◆ base

using altintegration::AltBlockTree::base = BaseBlockTree<AltBlock>

Definition at line 179 of file alt_block_tree.hpp.

◆ btc_config_t

using altintegration::AltBlockTree::btc_config_t = BtcChainParams

Definition at line 182 of file alt_block_tree.hpp.

◆ command_group_store_t

using altintegration::AltBlockTree::command_group_store_t = AltCommandGroupStore

Definition at line 188 of file alt_block_tree.hpp.

◆ eid_t

using altintegration::AltBlockTree::eid_t = typename endorsement_t::id_t

Definition at line 186 of file alt_block_tree.hpp.

◆ endorsement_t

using altintegration::AltBlockTree::endorsement_t = typename index_t::endorsement_t

Definition at line 185 of file alt_block_tree.hpp.

◆ hash_t

using altintegration::AltBlockTree::hash_t = typename AltBlock::hash_t

Definition at line 187 of file alt_block_tree.hpp.

◆ index_t

using altintegration::AltBlockTree::index_t = base::index_t

Definition at line 183 of file alt_block_tree.hpp.

◆ PopForkComparator

using altintegration::AltBlockTree::PopForkComparator = PopAwareForkResolutionComparator<AltBlock, AltChainParams, VbkBlockTree, AltBlockTree>

Definition at line 190 of file alt_block_tree.hpp.

◆ stored_index_t

using altintegration::AltBlockTree::stored_index_t = base::stored_index_t

Definition at line 184 of file alt_block_tree.hpp.

◆ vbk_config_t

using altintegration::AltBlockTree::vbk_config_t = VbkChainParams

Definition at line 181 of file alt_block_tree.hpp.

Member Function Documentation

◆ acceptBlock()

void altintegration::AltBlockTree::acceptBlock	(	const hash_t &	block,
		const PopData &	payloads
	)

When block is connected (meaning that all of its ancestors are also connected and have block body), it emits new signal onBlockConnected.

Precondition: can be executed on blocks in random order. I.e.; must not be executed twice on the same block; must not be executed on bootstrap block; PopData must be statelessly validated before passing it here

Exceptions

StateCorruptedException when we detect state corruption and we can not recover.

Parameters

[in]	block	hash of block where to add the block body
[in]	payloads	all POP payloads stored in this block

◆ acceptBlockHeader()

VBK_CHECK_RETURN bool altintegration::AltBlockTree::acceptBlockHeader	(	const AltBlock &	block,
		ValidationState &	state
	)

Parameters

[in]	block	ALT block header
[out]	state	validation state

Returns: true if block is valid, and added; false otherwise.

◆ bootstrap()

void altintegration::AltBlockTree::bootstrap ( )

Call this method before any use of AltBlockTree.

◆ btc()

const VbkBlockTree::BtcTree & altintegration::AltBlockTree::btc ( ) const

inline

Definition at line 421 of file alt_block_tree.hpp.

421{ return cmp_.getProtectingBlockTree().btc(); }

◆ comparePopScore()

VBK_CHECK_RETURN int altintegration::AltBlockTree::comparePopScore	(	const AltBlock::hash_t &	A,
		const AltBlock::hash_t &	B
	)

Parameters

[in]	A	hash of current tip in AltBlockTree. Fails on assert if current tip != A.
[in]	B	block. Current tip will be compared against this block. Can not be exist on chain and does not have to be fully validated(necessary validation will be performed during the fork resolution).

Warning: POP Fork Resolution is NOT transitive, it can not be used to search for an "absolute" best chain. If A is better than B, and B is better than C, then A may NOT be better than C. It is expected that caller will execute this comparator once for every tip candidate to avoid cycles (A->B->C->A). But this is no big deal, as sooner or later peers with different chains will converge to the same chain.

Returns: Returns positive if chain A is better. Returns negative if chain B is better. Returns 0 if blocks are equal in terms of POP. Users should fallback to chain-native Fork Resolution algorithm.

Precondition: this function can be called only on existing blocks; this function can be called only on connected blocks, otherwise it dies on assert; the first argument must always be equal to the current tip of AltBlockTree, otherwise it dies on assert; no other blocks but [genesis .. current tip] must be applied

Invariant: If B loses the fork resolution, only partial validation of B is performed. We can not determine B validity, because we never applied B alone.; If B wins the fork resolution, it is fully validated and AltBlockTree::setState(B,...) will be successful.; If POP score of both chains is equal, we expect altchain to determine best chain and then change state of AltBlockTree via setState.

Postcondition: if neither chain wins, A stays applied.; if chain B wins, the tree automatically switches to chain B (it becomes the tip); if return value is more or equal to 0, tree state is unchanged.

Exceptions

StateCorruptedException when we detect state corruption and we can not recover.

Warning: Operation can be expensive for long forks.

◆ getConnectedTipsAfter()

std::vector< const index_t * > altintegration::AltBlockTree::getConnectedTipsAfter ( const index_t & index ) const

Parameters

[in] index input block

Returns: vector of blocks where every block is connected and after index.

◆ getParams()

const AltChainParams & altintegration::AltBlockTree::getParams ( ) const

inline

Definition at line 425 of file alt_block_tree.hpp.

425{ return alt_config_; }

◆ loadBlockForward()

VBK_CHECK_RETURN bool altintegration::AltBlockTree::loadBlockForward	(	const stored_index_t &	index,
		bool	fast_load,
		ValidationState &	state
	)

overridevirtual

It recovers all pointers (pprev, pnext, endorsedBy, blockOfProofEndorsements), validates block and endorsements, recovers validity index, recovers tips array.

Parameters

[in]	index	block
[in]	fast_load	flag
[out]	state	validation state

Returns: true if block is valid

Invariant: NOT atomic. If loadBlock failed, AltBlockTree state is undefined and can not be used. Tip: ask user to run with '-reindex'.

Reimplemented from altintegration::BaseBlockTree< AltBlock >.

◆ loadTip()

VBK_CHECK_RETURN bool altintegration::AltBlockTree::loadTip	(	const hash_t &	hash,
		ValidationState &	state
	)

override

Parameters

[in]	hash	tip hash
[out]	state	validation state

Returns: true on success, false otherwise

◆ makeConnectedLeafPayloadMutator()

BlockPayloadMutator altintegration::AltBlockTree::makeConnectedLeafPayloadMutator ( index_t & block )

Precondition: the block must be a connected leaf

Parameters

[in] block the block index of the block to modify

◆ setState()

VBK_CHECK_RETURN bool altintegration::AltBlockTree::setState	(	index_t &	to,
		ValidationState &	state
	)

overridevirtual

Parameters

[in]	to	tree will be switched to this block
[out]	state

Returns: false if intermediate or target block is invalid. In this case tree will rollback into original state. true if state change is successful.

Invariant: atomic - either switches to new state, or does nothing.; the function switches state from exactly [genesis .. current tip] chain being applied(and no other) to [genesis .. to] chain being applied; both the current and new chains are fully valid; full validation of [genesis .. to] is a side effect

Warning: Expensive operation when we need to do long reorgs.

Exceptions

StateCorruptedException when we detect state corruption and we can not recover.

Reimplemented from altintegration::BaseBlockTree< AltBlock >.

◆ vbk()

const VbkBlockTree & altintegration::AltBlockTree::vbk ( ) const

inline

Definition at line 417 of file alt_block_tree.hpp.

417{ return cmp_.getProtectingBlockTree(); }

Friends And Related Function Documentation

◆ MemPoolBlockTree

friend struct MemPoolBlockTree

friend

Definition at line 444 of file alt_block_tree.hpp.

Member Data Documentation

◆ onBlockConnected

signals::Signal<void(index_t& index)> altintegration::AltBlockTree::onBlockConnected

Definition at line 307 of file alt_block_tree.hpp.

◆ onInvalidBlockConnected

signals::Signal<void(index_t& index, ValidationState&)> altintegration::AltBlockTree::onInvalidBlockConnected

Definition at line 304 of file alt_block_tree.hpp.

The documentation for this struct was generated from the following file:

include/veriblock/pop/blockchain/alt_block_tree.hpp

Detailed Description

Classes

Public Types

Public Member Functions

Public Attributes

Friends

Additional Inherited Members

Member Typedef Documentation

◆ alt_config_t

◆ base

◆ btc_config_t

◆ command_group_store_t

◆ eid_t

◆ endorsement_t

◆ hash_t

◆ index_t

◆ PopForkComparator

◆ stored_index_t

◆ vbk_config_t

Member Function Documentation

◆ acceptBlock()

◆ acceptBlockHeader()

◆ bootstrap()

◆ btc()

◆ comparePopScore()

◆ getConnectedTipsAfter()

◆ getParams()

◆ loadBlockForward()

◆ loadTip()

◆ makeConnectedLeafPayloadMutator()

◆ setState()

◆ vbk()

Friends And Related Function Documentation

◆ MemPoolBlockTree

Member Data Documentation

◆ onBlockConnected

◆ onInvalidBlockConnected