[#CPartialMerkleTree]
= CPartialMerkleTree
:mrdocs:

Data structure that represents a partial merkle tree&period;

== Synopsis

Declared in `&lt;merkleblock&period;h&gt;`

[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
class CPartialMerkleTree;
----

== Description

It represents a subset of the txid&apos;s of a known block, in a way that allows recovery of the list of txid&apos;s and the merkle root, in an authenticated way&period;

The encoding works as follows&colon; we traverse the tree in depth&hyphen;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)&period; 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&period; Otherwise, no hash is stored, but we recurse into both (or the only) child branch&period; During decoding, the same depth&hyphen;first traversal is performed, consuming bits and hashes as they written during encoding&period;

The serialization is fixed and provides a hard guarantee about the encoded size&colon;

SIZE &lt;&equals; 10 &plus; ceil(32&period;25&ast;N)

Where N represents the number of leaf nodes of the partial tree&period; N itself is bounded by&colon;

N &lt;&equals; total&lowbar;transactions N &lt;&equals; 1 &plus; matched&lowbar;transactions&ast;tree&lowbar;height

The serialization format&colon;

* uint32 total&lowbar;transactions (4 bytes)
* varint number of hashes (1&hyphen;3 bytes)
* uint256&lsqb;&rsqb;hashes in depth&hyphen;first order (&lt;&equals; 32&ast;N bytes)
* varint number of bytes of flag bits (1&hyphen;3 bytes)
* byte&lsqb;&rsqb;flag bits, packed per 8 in a byte, least significant bit first (&lt;&equals; 2&ast;N&hyphen;1 bits) The size constraints follow from this&period;

== Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:CPartialMerkleTree/2constructor-04.adoc[`CPartialMerkleTree`]         [.small]#[constructor]#
| Constructors
| xref:CPartialMerkleTree/ExtractMatches.adoc[`ExtractMatches`] 
| extract the matching txid&apos;s represented by this partial merkle tree and their respective indices within the partial tree&period; returns the merkle root, or 0 in case of failure
| xref:CPartialMerkleTree/GetNumTransactions.adoc[`GetNumTransactions`] 
| Get number of transactions the merkle proof is indicating for cross&hyphen;reference with local blockchain knowledge&period;
|===


== Protected Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:CPartialMerkleTree/CalcHash.adoc[`CalcHash`] 
| calculate the hash of a node in the merkle tree (at leaf level&colon; the txid&apos;s themselves)
| xref:CPartialMerkleTree/CalcTreeWidth.adoc[`CalcTreeWidth`] 
| helper function to efficiently calculate the number of nodes at given height in the merkle tree
| xref:CPartialMerkleTree/TraverseAndBuild.adoc[`TraverseAndBuild`] 
| recursive function that traverses tree nodes, storing the data as bits and hashes
| xref:CPartialMerkleTree/TraverseAndExtract.adoc[`TraverseAndExtract`] 
| recursive function that traverses tree nodes, consuming the bits and hashes produced by TraverseAndBuild&period; it returns the hash of the respective node and its respective index&period;
|===


== Protected Data Members

[cols="1,4"]
|===
| Name| Description
| xref:CPartialMerkleTree/fBad.adoc[`fBad`] 
| flag set when encountering invalid data
| xref:CPartialMerkleTree/nTransactions.adoc[`nTransactions`] 
| the total number of transactions in the block
| xref:CPartialMerkleTree/vBits.adoc[`vBits`] 
| node&hyphen;is&hyphen;parent&hyphen;of&hyphen;matched&hyphen;txid bits
| xref:CPartialMerkleTree/vHash.adoc[`vHash`] 
| txids and internal hashes
|===



[.small]#Created with https://www.mrdocs.com[MrDocs]#
