bitcoin/merkle_tree/
mod.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! Bitcoin merkle tree functions.
4//!
5//! # Examples
6//!
7//! ```
8//! # use bitcoin::{merkle_tree, Txid};
9//! # use bitcoin::hashes::Hash;
10//! # let tx1 = Txid::all_zeros();  // Dummy hash values.
11//! # let tx2 = Txid::all_zeros();
12//! let tx_hashes = vec![tx1, tx2]; // All the hashes we wish to merkelize.
13//! let root = merkle_tree::calculate_root(tx_hashes.into_iter());
14//! ```
15
16mod block;
17
18use core::cmp::min;
19use core::iter;
20
21use hashes::Hash;
22use io::Write;
23
24use crate::consensus::encode::Encodable;
25use crate::prelude::*;
26
27#[rustfmt::skip]
28#[doc(inline)]
29pub use self::block::{MerkleBlock, MerkleBlockError, PartialMerkleTree};
30
31/// Calculates the merkle root of a list of *hashes*, inline (in place) in `hashes`.
32///
33/// In most cases, you'll want to use [`calculate_root`] instead. Please note, calling this function
34/// trashes the data in `hashes` (i.e. the `hashes` is left in an undefined state at conclusion of
35/// this method and should not be used again afterwards).
36///
37/// # Returns
38/// - `None` if `hashes` is empty. The merkle root of an empty tree of hashes is undefined.
39/// - `Some(hash)` if `hashes` contains one element. A single hash is by definition the merkle root.
40/// - `Some(merkle_root)` if length of `hashes` is greater than one.
41pub fn calculate_root_inline<T>(hashes: &mut [T]) -> Option<T>
42where
43    T: Hash + Encodable,
44    <T as Hash>::Engine: Write,
45{
46    match hashes.len() {
47        0 => None,
48        1 => Some(hashes[0]),
49        _ => Some(merkle_root_r(hashes)),
50    }
51}
52
53/// Calculates the merkle root of an iterator of *hashes*.
54///
55/// # Returns
56/// - `None` if `hashes` is empty. The merkle root of an empty tree of hashes is undefined.
57/// - `Some(hash)` if `hashes` contains one element. A single hash is by definition the merkle root.
58/// - `Some(merkle_root)` if length of `hashes` is greater than one.
59pub fn calculate_root<T, I>(mut hashes: I) -> Option<T>
60where
61    T: Hash + Encodable,
62    <T as Hash>::Engine: Write,
63    I: Iterator<Item = T>,
64{
65    let first = hashes.next()?;
66    let second = match hashes.next() {
67        Some(second) => second,
68        None => return Some(first),
69    };
70
71    let mut hashes = iter::once(first).chain(iter::once(second)).chain(hashes);
72
73    // We need a local copy to pass to `merkle_root_r`. It's more efficient to do the first loop of
74    // processing as we make the copy instead of copying the whole iterator.
75    let (min, max) = hashes.size_hint();
76    let mut alloc = Vec::with_capacity(max.unwrap_or(min) / 2 + 1);
77
78    while let Some(hash1) = hashes.next() {
79        // If the size is odd, use the last element twice.
80        let hash2 = hashes.next().unwrap_or(hash1);
81        let mut encoder = T::engine();
82        hash1.consensus_encode(&mut encoder).expect("in-memory writers don't error");
83        hash2.consensus_encode(&mut encoder).expect("in-memory writers don't error");
84        alloc.push(T::from_engine(encoder));
85    }
86
87    Some(merkle_root_r(&mut alloc))
88}
89
90// `hashes` must contain at least one hash.
91fn merkle_root_r<T>(hashes: &mut [T]) -> T
92where
93    T: Hash + Encodable,
94    <T as Hash>::Engine: Write,
95{
96    if hashes.len() == 1 {
97        return hashes[0];
98    }
99
100    for idx in 0..((hashes.len() + 1) / 2) {
101        let idx1 = 2 * idx;
102        let idx2 = min(idx1 + 1, hashes.len() - 1);
103        let mut encoder = T::engine();
104        hashes[idx1].consensus_encode(&mut encoder).expect("in-memory writers don't error");
105        hashes[idx2].consensus_encode(&mut encoder).expect("in-memory writers don't error");
106        hashes[idx] = T::from_engine(encoder);
107    }
108    let half_len = hashes.len() / 2 + hashes.len() % 2;
109
110    merkle_root_r(&mut hashes[0..half_len])
111}
112
113#[cfg(test)]
114mod tests {
115    use hashes::sha256d;
116
117    use super::*;
118    use crate::blockdata::block::Block;
119    use crate::consensus::encode::deserialize;
120
121    #[test]
122    fn both_merkle_root_functions_return_the_same_result() {
123        // testnet block 000000000000045e0b1660b6445b5e5c5ab63c9a4f956be7e1e69be04fa4497b
124        let segwit_block = include_bytes!("../../tests/data/testnet_block_000000000000045e0b1660b6445b5e5c5ab63c9a4f956be7e1e69be04fa4497b.raw");
125        let block: Block = deserialize(&segwit_block[..]).expect("Failed to deserialize block");
126        assert!(block.check_merkle_root()); // Sanity check.
127
128        let hashes_iter = block.txdata.iter().map(|obj| obj.compute_txid().to_raw_hash());
129
130        let mut hashes_array: [sha256d::Hash; 15] = [Hash::all_zeros(); 15];
131        for (i, hash) in hashes_iter.clone().enumerate() {
132            hashes_array[i] = hash;
133        }
134
135        let from_iter = calculate_root(hashes_iter);
136        let from_array = calculate_root_inline(&mut hashes_array);
137        assert_eq!(from_iter, from_array);
138    }
139}
bitcoin/merkle_tree/mod.rs

bitcoin/merkle_tree/
mod.rs
