Data structure that represents a partial merkle tree. More...

#include <merkleblock.h>

Public Member Functions
	SERIALIZE_METHODS (CPartialMerkleTree, obj)

	CPartialMerkleTree (const std::vector< uint256 > &vTxid, const std::vector< bool > &vMatch)
	Construct a partial merkle tree from a list of transaction ids, and a mask that selects a subset of them.

	CPartialMerkleTree ()

uint256	ExtractMatches (std::vector< uint256 > &vMatch, std::vector< size_t > &vnIndex)
	Extract the matching txid's represented by this partial merkle tree and their respective indices within the partial tree.

uint32_t	GetNumTransactions () const
	Get number of transactions the merkle proof is indicating for cross-reference with local blockchain knowledge.

Protected Member Functions
size_t	CalcTreeWidth (int height) const
	Helper function to efficiently calculate the number of nodes at given height in the merkle tree.

uint256	CalcHash (int height, size_t pos, const std::vector< uint256 > &vTxid)
	Calculate the hash of a node in the merkle tree (at leaf level: the txid's themselves)

void	TraverseAndBuild (int height, size_t pos, const std::vector< uint256 > &vTxid, const std::vector< bool > &vMatch)
	Recursive function that traverses tree nodes, storing the data as bits and hashes.

uint256	TraverseAndExtract (int height, size_t pos, size_t &nBitsUsed, size_t &nHashUsed, std::vector< uint256 > &vMatch, std::vector< size_t > &vnIndex)
	Recursive function that traverses tree nodes, consuming the bits and hashes produced by TraverseAndBuild.

Protected Attributes
uint32_t	nTransactions
	the total number of transactions in the block

std::vector< bool >	vBits
	node-is-parent-of-matched-txid bits

std::vector< uint256 >	vHash
	txids and internal hashes

bool	fBad
	flag set when encountering invalid data

Detailed Description

Data structure that represents a partial merkle tree.

It represents a subset of the txid's of a known block, in a way that allows recovery of the list of txid's and the merkle root, in an authenticated way.

The encoding works as follows: we traverse the tree in depth-first order, storing a bit for each traversed node, signifying whether the node is the parent of at least one matched leaf txid (or a matched txid itself). In case we are at the leaf level, or this bit is 0, its merkle node hash is stored, and its children are not explored further. Otherwise, no hash is stored, but we recurse into both (or the only) child branch. During decoding, the same depth-first traversal is performed, consuming bits and hashes as they written during encoding.

The serialization is fixed and provides a hard guarantee about the encoded size:

SIZE <= 10 + ceil(32.25*N)

Where N represents the number of leaf nodes of the partial tree. N itself is bounded by:

N <= total_transactions N <= 1 + matched_transactions*tree_height

The serialization format:

uint32 total_transactions (4 bytes)
varint number of hashes (1-3 bytes)
uint256[] hashes in depth-first order (<= 32*N bytes)
varint number of bytes of flag bits (1-3 bytes)
byte[] flag bits, packed per 8 in a byte, least significant bit first (<= 2*N-1 bits) The size constraints follow from this.

Definition at line 56 of file merkleblock.h.

Constructor & Destructor Documentation

◆ CPartialMerkleTree() [1/2]

CPartialMerkleTree::CPartialMerkleTree	(	const std::vector< uint256 > &	vTxid,
		const std::vector< bool > &	vMatch
	)

Construct a partial merkle tree from a list of transaction ids, and a mask that selects a subset of them.

Definition at line 161 of file merkleblock.cpp.

Here is the call graph for this function:

◆ CPartialMerkleTree() [2/2]

CPartialMerkleTree::CPartialMerkleTree ( )

Definition at line 178 of file merkleblock.cpp.

Member Function Documentation

◆ CalcHash()

uint256 CPartialMerkleTree::CalcHash	(	int	height,
		size_t	pos,
		const std::vector< uint256 > &	vTxid
	)

protected

Calculate the hash of a node in the merkle tree (at leaf level: the txid's themselves)

Definition at line 63 of file merkleblock.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ CalcTreeWidth()

size_t CPartialMerkleTree::CalcTreeWidth ( int height ) const

inlineprotected

Helper function to efficiently calculate the number of nodes at given height in the merkle tree.

Definition at line 74 of file merkleblock.h.

Here is the caller graph for this function:

◆ ExtractMatches()

uint256 CPartialMerkleTree::ExtractMatches	(	std::vector< uint256 > &	vMatch,
		std::vector< size_t > &	vnIndex
	)

Extract the matching txid's represented by this partial merkle tree and their respective indices within the partial tree.

Returns the merkle root, or 0 in case of failure.

Definition at line 180 of file merkleblock.cpp.

Here is the call graph for this function:

◆ GetNumTransactions()

uint32_t CPartialMerkleTree::GetNumTransactions ( ) const

inline

Get number of transactions the merkle proof is indicating for cross-reference with local blockchain knowledge.

Definition at line 132 of file merkleblock.h.

◆ SERIALIZE_METHODS()

CPartialMerkleTree::SERIALIZE_METHODS	(	CPartialMerkleTree	,
		obj
	)

inline

Definition at line 102 of file merkleblock.h.

Here is the call graph for this function:

◆ TraverseAndBuild()

void CPartialMerkleTree::TraverseAndBuild	(	int	height,
		size_t	pos,
		const std::vector< uint256 > &	vTxid,
		const std::vector< bool > &	vMatch
	)

protected

Recursive function that traverses tree nodes, storing the data as bits and hashes.

Definition at line 88 of file merkleblock.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ TraverseAndExtract()

uint256 CPartialMerkleTree::TraverseAndExtract	(	int	height,
		size_t	pos,
		size_t &	nBitsUsed,
		size_t &	nHashUsed,
		std::vector< uint256 > &	vMatch,
		std::vector< size_t > &	vnIndex
	)

protected

Recursive function that traverses tree nodes, consuming the bits and hashes produced by TraverseAndBuild.

It returns the hash of the respective node and its respective index.

Definition at line 112 of file merkleblock.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ fBad

bool CPartialMerkleTree::fBad

protected

flag set when encountering invalid data

Definition at line 68 of file merkleblock.h.

◆ nTransactions

uint32_t CPartialMerkleTree::nTransactions

protected

the total number of transactions in the block

Definition at line 59 of file merkleblock.h.

◆ vBits

std::vector<bool> CPartialMerkleTree::vBits

protected

node-is-parent-of-matched-txid bits

Definition at line 62 of file merkleblock.h.

◆ vHash

std::vector<uint256> CPartialMerkleTree::vHash

protected

txids and internal hashes

Definition at line 65 of file merkleblock.h.

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

src/merkleblock.h
src/merkleblock.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ CPartialMerkleTree() [1/2]

◆ CPartialMerkleTree() [2/2]

Member Function Documentation

◆ CalcHash()

◆ CalcTreeWidth()

◆ ExtractMatches()

◆ GetNumTransactions()

◆ SERIALIZE_METHODS()

◆ TraverseAndBuild()

◆ TraverseAndExtract()

Member Data Documentation

◆ fBad

◆ nTransactions

◆ vBits

◆ vHash