Bitcoin Core  0.15.99
P2P Digital Currency
Public Member Functions | Public Attributes | Protected Member Functions | Protected Attributes | List of all members
CPartialMerkleTree Class Reference

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

#include <merkleblock.h>

Public Member Functions

template<typename Stream , typename Operation >
void SerializationOp (Stream &s, Operation ser_action)
 
 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. More...
 
 CPartialMerkleTree ()
 
uint256 ExtractMatches (std::vector< uint256 > &vMatch, std::vector< unsigned int > &vnIndex)
 extract the matching txid's represented by this partial merkle tree and their respective indices within the partial tree. More...
 

Public Attributes

 ADD_SERIALIZE_METHODS
 serialization implementation More...
 

Protected Member Functions

unsigned int CalcTreeWidth (int height) const
 helper function to efficiently calculate the number of nodes at given height in the merkle tree More...
 
uint256 CalcHash (int height, unsigned int pos, const std::vector< uint256 > &vTxid)
 calculate the hash of a node in the merkle tree (at leaf level: the txid's themselves) More...
 
void TraverseAndBuild (int height, unsigned int pos, const std::vector< uint256 > &vTxid, const std::vector< bool > &vMatch)
 recursive function that traverses tree nodes, storing the data as bits and hashes More...
 
uint256 TraverseAndExtract (int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector< uint256 > &vMatch, std::vector< unsigned int > &vnIndex)
 recursive function that traverses tree nodes, consuming the bits and hashes produced by TraverseAndBuild. More...
 

Protected Attributes

unsigned int nTransactions
 the total number of transactions in the block More...
 
std::vector< bool > vBits
 node-is-parent-of-matched-txid bits More...
 
std::vector< uint256vHash
 txids and internal hashes More...
 
bool fBad
 flag set when encountering invalid data More...
 

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:

Definition at line 50 of file merkleblock.h.

Constructor & Destructor Documentation

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 137 of file merkleblock.cpp.

Here is the call graph for this function:

CPartialMerkleTree::CPartialMerkleTree ( )

Definition at line 151 of file merkleblock.cpp.

Here is the caller graph for this function:

Member Function Documentation

uint256 CPartialMerkleTree::CalcHash ( int  height,
unsigned int  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 61 of file merkleblock.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned int 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 66 of file merkleblock.h.

Here is the call graph for this function:

Here is the caller graph for this function:

uint256 CPartialMerkleTree::ExtractMatches ( std::vector< uint256 > &  vMatch,
std::vector< unsigned int > &  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 153 of file merkleblock.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Stream , typename Operation >
void CPartialMerkleTree::SerializationOp ( Stream &  s,
Operation  ser_action 
)
inline

Definition at line 88 of file merkleblock.h.

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

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

Definition at line 81 of file merkleblock.cpp.

Here is the caller graph for this function:

uint256 CPartialMerkleTree::TraverseAndExtract ( int  height,
unsigned int  pos,
unsigned int &  nBitsUsed,
unsigned int &  nHashUsed,
std::vector< uint256 > &  vMatch,
std::vector< unsigned int > &  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 99 of file merkleblock.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

CPartialMerkleTree::ADD_SERIALIZE_METHODS

serialization implementation

Definition at line 85 of file merkleblock.h.

bool CPartialMerkleTree::fBad
protected

flag set when encountering invalid data

Definition at line 63 of file merkleblock.h.

unsigned int CPartialMerkleTree::nTransactions
protected

the total number of transactions in the block

Definition at line 54 of file merkleblock.h.

std::vector<bool> CPartialMerkleTree::vBits
protected

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

Definition at line 57 of file merkleblock.h.

std::vector<uint256> CPartialMerkleTree::vHash
protected

txids and internal hashes

Definition at line 60 of file merkleblock.h.


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