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

#include <main.h>

Collaboration diagram for CPartialMerkleTree:

Public Member Functions
uint256	ExtractMatches (std::vector< uint256 > &vMatch)

Protected Member Functions
unsigned int	CalcTreeWidth (int height)

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

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

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

Protected Attributes
unsigned int	nTransactions

std::vector< bool >	vBits

std::vector< uint256 >	vHash

bool	fBad

Detailed Description

Data structure that represents a partial merkle tree.

It respresents 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 explorer 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 519 of file main.h.

Member Function Documentation

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

protected

Definition at line 2678 of file main.cpp.

References BEGIN, END, and Hash().

Here is the call graph for this function:

unsigned int CPartialMerkleTree::CalcTreeWidth ( int height )

inlineprotected

Definition at line 535 of file main.h.

Referenced by ExtractMatches().

Here is the caller graph for this function:

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

Definition at line 2759 of file main.cpp.

References CalcTreeWidth(), fBad, MAX_BLOCK_SIZE, nTransactions, TraverseAndExtract(), vBits, and vHash.

Here is the call graph for this function:

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

protected

Definition at line 2695 of file main.cpp.

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