Struct bdk_chain::bitcoin::merkle_tree::PartialMerkleTree

pub struct PartialMerkleTree { /* private fields */ }
Expand 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:

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

Implementations§

§

impl PartialMerkleTree

pub fn num_transactions(&self) -> u32

Returns the total number of transactions in the block.

pub fn bits(&self) -> &Vec<bool>

Returns the node-is-parent-of-matched-txid bits of the partial merkle tree.

pub fn hashes(&self) -> &Vec<TxMerkleNode>

Returns the transaction ids and internal hashes of the partial merkle tree.

pub fn from_txids(txids: &[Txid], matches: &[bool]) -> PartialMerkleTree

Construct a partial merkle tree The txids are the transaction hashes of the block and the matches is the contains flags wherever a tx hash should be included in the proof.

Panics when txids is empty or when matches has a different length

§Examples
use bitcoin::hash_types::Txid;
use bitcoin::hex::FromHex;
use bitcoin::merkle_tree::{MerkleBlock, PartialMerkleTree};

// Block 80000
let txids: Vec<Txid> = [
    "c06fbab289f723c6261d3030ddb6be121f7d2508d77862bb1e484f5cd7f92b25",
    "5a4ebf66822b0b2d56bd9dc64ece0bc38ee7844a23ff1d7320a88c5fdb2ad3e2",
]
.iter()
.map(|hex| hex.parse::<Txid>().unwrap())
.collect();

// Select the second transaction
let matches = vec![false, true];
let tree = PartialMerkleTree::from_txids(&txids, &matches);
assert!(tree.extract_matches(&mut vec![], &mut vec![]).is_ok());

pub fn extract_matches( &self, matches: &mut Vec<Txid>, indexes: &mut Vec<u32> ) -> Result<TxMerkleNode, MerkleBlockError>

Extract the matching txid’s represented by this partial merkle tree and their respective indices within the partial tree. returns the merkle root, or error in case of failure

Trait Implementations§

§

impl Clone for PartialMerkleTree

§

fn clone(&self) -> PartialMerkleTree

Returns a copy of the value. Read more
1.0.0 · source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
§

impl Debug for PartialMerkleTree

§

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter. Read more
§

impl Decodable for PartialMerkleTree

§

fn consensus_decode_from_finite_reader<R>( r: &mut R ) -> Result<PartialMerkleTree, Error>
where R: Read + ?Sized,

Decode Self from a size-limited reader. Read more
§

fn consensus_decode<R>(reader: &mut R) -> Result<Self, Error>
where R: Read + ?Sized,

Decode an object with a well-defined format. Read more
§

impl Encodable for PartialMerkleTree

§

fn consensus_encode<W>(&self, w: &mut W) -> Result<usize, Error>
where W: Write + ?Sized,

Encodes an object with a well-defined format. Read more
§

impl PartialEq for PartialMerkleTree

§

fn eq(&self, other: &PartialMerkleTree) -> bool

This method tests for self and other values to be equal, and is used by ==.
1.0.0 · source§

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
§

impl Eq for PartialMerkleTree

§

impl StructuralPartialEq for PartialMerkleTree

Auto Trait Implementations§

Blanket Implementations§

source§

impl<T> Any for T
where T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for T
where T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
§

impl<Q, K> Equivalent<K> for Q
where Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

§

fn equivalent(&self, key: &K) -> bool

Checks if this value is equivalent to the given key. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for T
where U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for T
where T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

§

fn vzip(self) -> V