Bitcoin Core
0.20.99
P2P Digital Currency

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. 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...  
unsigned int  GetNumTransactions () const 
Get number of transactions the merkle proof is indicating for crossreference with local blockchain knowledge. 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 
nodeisparentofmatchedtxid bits More...  
std::vector< uint256 >  vHash 
txids and internal hashes More...  
bool  fBad 
flag set when encountering invalid data More...  
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 depthfirst 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 depthfirst 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 54 of file merkleblock.h.
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 133 of file merkleblock.cpp.
CPartialMerkleTree::CPartialMerkleTree  (  ) 
Definition at line 147 of file merkleblock.cpp.

protected 
calculate the hash of a node in the merkle tree (at leaf level: the txid's themselves)
Definition at line 57 of file merkleblock.cpp.

inlineprotected 
helper function to efficiently calculate the number of nodes at given height in the merkle tree
Definition at line 70 of file merkleblock.h.
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 149 of file merkleblock.cpp.

inline 
Get number of transactions the merkle proof is indicating for crossreference with local blockchain knowledge.
Definition at line 113 of file merkleblock.h.

inline 

protected 
recursive function that traverses tree nodes, storing the data as bits and hashes
Definition at line 77 of file merkleblock.cpp.

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

protected 
flag set when encountering invalid data
Definition at line 67 of file merkleblock.h.

protected 
the total number of transactions in the block
Definition at line 58 of file merkleblock.h.

protected 
nodeisparentofmatchedtxid bits
Definition at line 61 of file merkleblock.h.

protected 
txids and internal hashes
Definition at line 64 of file merkleblock.h.