CPartialMerkleTree Class Reference

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

#include <main.h>

Inheritance 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 1208 of file main.h.

Member Function Documentation

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

protected

Definition at line 2463 of file main.cpp.

unsigned int CPartialMerkleTree::CalcTreeWidth ( int  height )

inlineprotected

Definition at line 1224 of file main.h.

uint256 CPartialMerkleTree::ExtractMatches

(

std::vector< uint256 > &

vMatch

)

Definition at line 2544 of file main.cpp.

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

protected

Definition at line 2480 of file main.cpp.

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

protected

Definition at line 2498 of file main.cpp.

Member Data Documentation

bool CPartialMerkleTree::fBad

protected

Definition at line 1221 of file main.h.

unsigned int CPartialMerkleTree::nTransactions

protected

Definition at line 1212 of file main.h.

std::vector<bool> CPartialMerkleTree::vBits

protected

Definition at line 1215 of file main.h.

std::vector<uint256> CPartialMerkleTree::vHash

protected

Definition at line 1218 of file main.h.

---

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

• src/main.h
• src/main.cpp