Data structure that represents a partial merkle tree.
Declared in <merkleblock.h>
class CPartialMerkleTree;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.
| Name | Description |
|---|---|
CPartialMerkleTree [constructor] | Constructors |
ExtractMatches | 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 |
GetNumTransactions | Get number of transactions the merkle proof is indicating for cross-reference with local blockchain knowledge. |
| Name | Description |
|---|---|
CalcHash | calculate the hash of a node in the merkle tree (at leaf level: the txid's themselves) |
CalcTreeWidth | helper function to efficiently calculate the number of nodes at given height in the merkle tree |
TraverseAndBuild | recursive function that traverses tree nodes, storing the data as bits and hashes |
TraverseAndExtract | 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. |
| Name | Description |
|---|---|
fBad | flag set when encountering invalid data |
nTransactions | the total number of transactions in the block |
vBits | node-is-parent-of-matched-txid bits |
vHash | txids and internal hashes |