Struct bitcoin_merkle::PartialMerkleTree

pub struct PartialMerkleTree { /* private fields */ }

| 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.25N) | | Where N represents the number of leaf nodes of | the partial tree. N itself is bounded by: | | N <= total_transactions | N <= 1 + matched_transactionstree_height | | The serialization format: | | - uint32 total_transactions (4 bytes) | | - varint number of hashes (1-3 bytes) | | - uint256[] hashes in depth-first order (<= | 32N bytes) | | - varint number of bytes of flag bits (1-3 | bytes) | | - byte[] flag bits, packed per 8 in | a byte, least significant bit | first (<= 2N-1 bits) | | The size constraints follow from this.

Implementations

impl PartialMerkleTree

pub fn calc_tree_width(&self, height: i32) -> u32

| helper function to efficiently calculate | the number of nodes at given height in | the merkle tree |

pub fn get_num_transactions(&self) -> u32

| Get number of transactions the merkle | proof is indicating for cross-reference | with local blockchain knowledge. |

pub fn calc_hash(&mut self, height: i32, pos: u32, txid: &Vec<u256>) -> u256

| calculate the hash of a node in the merkle | tree (at leaf level: the txid’s themselves) |

pub fn traverse_and_build( &mut self, height: i32, pos: u32, txid: &Vec<u256>, match_: &Vec<bool> )

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

pub fn traverse_and_extract( &mut self, height: i32, pos: u32, n_bits_used: &mut u32, n_hash_used: &mut u32, match_: &mut Vec<u256>, vn_index: &mut Vec<u32> ) -> u256

| 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. |

pub fn new_with_txid_and_match(txid: &Vec<u256>, match_: &Vec<bool>) -> Self

| Construct a partial merkle tree from | a list of transaction ids, and a mask | that selects a subset of them |

pub fn extract_matches( &mut self, match_: &mut Vec<u256>, vn_index: &mut Vec<u32> ) -> u256

| 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 |

Trait Implementations

impl Default for PartialMerkleTree

fn default() -> Self

Returns the “default value” for a type.