Veriblock block tree. More...

Detailed Description

It is strongly advised to not modify the Veriblock tree directly, as it is intended to be fully managed by AltBlockTree

Invariant: Adding an invalid payload to block X cannot invalidate any block but X. As a consequence, the tree allows duplicates and AltBlockTree must check that an altchain fork does not contain VTB duplicates.; addPayloads fully validates each payload and refuses to add invalid payloads.; removePayloads and unsafelyRemovePayload cannot invalidate any block as long as they are called by AltBlockTree, and not by the user.; all payloads and blocks are valid as a consequence of the above.

Definition: a validation hole is incorrect use of removePayloads and unsafelyRemovePayload by AltBlockTree that results in invalid Veriblock tree blocks or corrupted state.

Notes regarding the validation hole: At this moment, the validation hole can be considered plugged as long as the user never modifies the VBK tree directly, never uses PopStateMachine and only calls AltBlockTree::setState() and AltBlockTree::comparePopScore() as currently implemented. However, a trivial code modification can unintentionally re-introduce the issue.

To plug the validation hole, we must ensure that any unvalidated block is unapplied before all of the blocks that were applied at the time of the application.

Suppose, altchain blocks were applied in the following order: V1, V2, V3, U4, U5, U6, V7, V8, U9 (V* are fully valid blocks, U* are unvalidated blocks)

In this example, AltBlockTree must ensure that the blocks are unapplied in the following sequence:

U9 is unapplied first
V8 and V7 in any order; both V8, V7 and V7, V8 are safe
U6, U5, U4 in this specific order
V3-V1 in any order

This looks like a feasible safeguard:

Prevent the user from modifying the VBK tree
Add a list stack that stores all blocks in the order they were applied. On application, blocks are appended to the list. On unapplication, blocks are deleted from the list. A block can be unapplied only if it is contained in the list slice beween the tail and the last unvalidated block.

In this example, initially, the slice is [U9]. After we unapply U9, the slice becomes [U6, V7, V8]. If U6 is unapplied, the slice becomes [U5, V7, V8].

Definition at line 95 of file vbk_block_tree.hpp.

#include <vbk_block_tree.hpp>

Inheritance diagram for altintegration::VbkBlockTree:

Collaboration diagram for altintegration::VbkBlockTree:

Public Types
using	VbkTree = BlockTree< VbkBlock, VbkChainParams >

using	BtcTree = BtcBlockTree

using	index_t = VbkTree::index_t

using	stored_index_t = VbkTree::stored_index_t

using	payloads_t = typename index_t::payloads_t

using	pid_t = typename payloads_t::id_t

using	endorsement_t = typename index_t::endorsement_t

using	command_group_store_t = VbkCommandGroupStore

using	PopForkComparator = PopAwareForkResolutionComparator< VbkBlock, VbkChainParams, BtcTree, VbkBlockTree >

Public Types inherited from altintegration::BlockTree< VbkBlock, VbkChainParams >
using	base = BaseBlockTree< VbkBlock >

using	block_t = VbkBlock

using	params_t = VbkChainParams

using	index_t = typename base::index_t

using	stored_index_t = typename base::stored_index_t

using	hash_t = typename Block::hash_t

using	prev_block_hash_t = typename Block::prev_hash_t

using	height_t = typename Block::height_t

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

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< VbkBlock >

using	stored_index_t = StoredBlockIndex< VbkBlock >

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
	VbkBlockTree (const VbkChainParams &vbkp, const BtcChainParams &btcp, PayloadsStorage &payloadsProvider, BlockReader &blockProvider)

bool	loadBlockForward (const stored_index_t &index, bool fast_load, ValidationState &state) override
	efficiently connect `index` to current tree as a leaf, loaded from disk More...

BtcTree &	btc ()

const BtcTree &	btc () const

PopForkComparator &	getComparator ()

const PopForkComparator &	getComparator () const

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

uint32_t	estimateMissedNumberOfVTBs (const index_t &index) const

bool	addPayloads (const VbkBlock::hash_t &hash, const std::vector< payloads_t > &payloads, ValidationState &state)
	Attempts to add payloads to the block and perform full validation. More...

void	removePayloads (const hash_t &hash, const std::vector< pid_t > &pids)

void	removePayloads (index_t &index, const std::vector< pid_t > &pids)

void	unsafelyRemovePayload (const Blob< 24 > &hash, const pid_t &pid)
	If we add payloads to the VBK tree in the following order: A1, B2, A3. More...

void	unsafelyRemovePayload (index_t &index, const pid_t &pid, bool shouldDetermineBestChain=true)

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

bool	setState (index_t &to, ValidationState &state) override

void	overrideTip (index_t &to) override

void	finalizeBlocks ()

Public Member Functions inherited from altintegration::BlockTree< VbkBlock, VbkChainParams >
	BlockTree (const VbkChainParams &param, const BlockReader &blockProvider)

const VbkChainParams &	getParams () const

virtual void	bootstrapWithGenesis (const block_t &block)
	Bootstrap blockchain with a single genesis block. More...

virtual void	bootstrapWithChain (height_t startHeight, const std::vector< block_t > &chain)
	Bootstrap network with a chain that starts at 'startHeight'. More...

bool	acceptBlockHeader (const block_t &block, ValidationState &state)

bool	acceptBlockHeader (const std::shared_ptr< block_t > &block, ValidationState &state)

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

bool	loadBlockForward (const stored_index_t &index, bool fast_load, ValidationState &state) override

bool	isBlockOld (height_t height) const
	block is considered old if it is behind current tip further than 'old blocks window' blocks More...

bool	isBlockOld (const hash_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...

void	finalizeBlocks ()

Public Member Functions inherited from altintegration::BaseBlockTree< VbkBlock >
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 ()

Additional Inherited Members
Public Attributes inherited from altintegration::BaseBlockTree< VbkBlock >
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...

Protected Member Functions inherited from altintegration::BlockTree< VbkBlock, VbkChainParams >
bool	acceptBlockHeaderImpl (const std::shared_ptr< block_t > &block, ValidationState &state, bool shouldContextuallyCheck)

void	bootstrap (height_t height, const block_t &block, ValidationState &state)

void	bootstrap (height_t height, std::shared_ptr< block_t > block, ValidationState &state)

bool	validateAndAddBlock (const std::shared_ptr< block_t > &block, ValidationState &state, bool shouldContextuallyCheck, index_t **ret)

void	determineBestChain (index_t &candidate, ValidationState &state) override

void	onBlockInserted (index_t *newIndex) final
	whenever new block is inserted, BlockTree has to update its ChainWork More...

Protected Member Functions inherited from altintegration::BaseBlockTree< VbkBlock >
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::BlockTree< VbkBlock, VbkChainParams >
const VbkChainParams *	param_

Protected Attributes inherited from altintegration::BaseBlockTree< VbkBlock >
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

◆ BtcTree

using altintegration::VbkBlockTree::BtcTree = BtcBlockTree

Definition at line 97 of file vbk_block_tree.hpp.

◆ command_group_store_t

using altintegration::VbkBlockTree::command_group_store_t = VbkCommandGroupStore

Definition at line 103 of file vbk_block_tree.hpp.

◆ endorsement_t

using altintegration::VbkBlockTree::endorsement_t = typename index_t::endorsement_t

Definition at line 102 of file vbk_block_tree.hpp.

◆ index_t

using altintegration::VbkBlockTree::index_t = VbkTree::index_t

Definition at line 98 of file vbk_block_tree.hpp.

◆ payloads_t

using altintegration::VbkBlockTree::payloads_t = typename index_t::payloads_t

Definition at line 100 of file vbk_block_tree.hpp.

◆ pid_t

using altintegration::VbkBlockTree::pid_t = typename payloads_t::id_t

Definition at line 101 of file vbk_block_tree.hpp.

◆ PopForkComparator

using altintegration::VbkBlockTree::PopForkComparator = PopAwareForkResolutionComparator<VbkBlock, VbkChainParams, BtcTree, VbkBlockTree>

Definition at line 104 of file vbk_block_tree.hpp.

◆ stored_index_t

using altintegration::VbkBlockTree::stored_index_t = VbkTree::stored_index_t

Definition at line 99 of file vbk_block_tree.hpp.

◆ VbkTree

using altintegration::VbkBlockTree::VbkTree = BlockTree<VbkBlock, VbkChainParams>

Definition at line 96 of file vbk_block_tree.hpp.

Member Function Documentation

◆ addPayloads()

bool altintegration::VbkBlockTree::addPayloads	(	const VbkBlock::hash_t &	hash,
		const std::vector< payloads_t > &	payloads,
		ValidationState &	state
	)

If successful, it is possible to setState() to the block after the addPayloads call. If unsuccessful, it leaves the state unchanged.

Invariant: atomic: adds either all or none of the payloads

◆ btc() [1/2]

BtcTree & altintegration::VbkBlockTree::btc ( )

inline

Definition at line 126 of file vbk_block_tree.hpp.

126{ return cmp_.getProtectingBlockTree(); }

◆ btc() [2/2]

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

inline

Definition at line 127 of file vbk_block_tree.hpp.

127{ return cmp_.getProtectingBlockTree(); }

◆ getComparator() [1/2]

PopForkComparator & altintegration::VbkBlockTree::getComparator ( )

inline

Definition at line 129 of file vbk_block_tree.hpp.

129{ return cmp_; }

◆ getComparator() [2/2]

const PopForkComparator & altintegration::VbkBlockTree::getComparator ( ) const

inline

Definition at line 130 of file vbk_block_tree.hpp.

130{ return cmp_; }

◆ loadBlockForward()

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

overridevirtual

recovers all pointers (pprev, pnext, endorsedBy)
recalculates chainWork
does validation of endorsements
recovers tips array
Invariant
NOT atomic.

Reimplemented from altintegration::BaseBlockTree< VbkBlock >.

◆ loadTip()

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

overridevirtual

Reimplemented from altintegration::BaseBlockTree< VbkBlock >.

◆ overrideTip()

void altintegration::VbkBlockTree::overrideTip ( index_t & to )

overridevirtual

Reimplemented from altintegration::BaseBlockTree< VbkBlock >.

◆ setState()

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

overridevirtual

Reimplemented from altintegration::BaseBlockTree< VbkBlock >.

◆ unsafelyRemovePayload()

void altintegration::VbkBlockTree::unsafelyRemovePayload	(	const Blob< 24 > &	hash,
		const pid_t &	pid
	)

Ending up with the tree looking like this: A(1,3)-o-o-o-B(2)

It is only safe to use this function to remove them in the opposite order: A3, B2, A1; or A3, B2.

It is unsafe to use this function to remove them in any other order eg: B2, A3, A1; or just B2.

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

include/veriblock/pop/blockchain/pop/vbk_block_tree.hpp

Detailed Description

Public Types

Public Member Functions

Additional Inherited Members

Member Typedef Documentation

◆ BtcTree

◆ command_group_store_t

◆ endorsement_t

◆ index_t

◆ payloads_t

◆ pid_t

◆ PopForkComparator

◆ stored_index_t

◆ VbkTree

Member Function Documentation

◆ addPayloads()

◆ btc() [1/2]

◆ btc() [2/2]

◆ getComparator() [1/2]

◆ getComparator() [2/2]

◆ loadBlockForward()

◆ loadTip()

◆ overrideTip()

◆ setState()

◆ unsafelyRemovePayload()