bitcoin/merkle_tree/
block.rs

1// SPDX-License-Identifier: CC0-1.0
2//
3// This code was translated from merkleblock.h, merkleblock.cpp and pmt_tests.cpp
4// Copyright (c) 2009-2010 Satoshi Nakamoto
5// Copyright (c) 2009-2018 The Bitcoin Core developers
6// SPDX-License-Identifier: MIT
7
8//! Merkle Block and Partial Merkle Tree.
9//!
10//! Support proofs that transaction(s) belong to a block.
11//!
12//! # Examples
13//!
14//! ```rust
15//! use bitcoin::hash_types::Txid;
16//! use bitcoin::hex::FromHex;
17//! use bitcoin::{Block, MerkleBlock};
18//!
19//! // Get the proof from a bitcoind by running in the terminal:
20//! // $ TXID="5a4ebf66822b0b2d56bd9dc64ece0bc38ee7844a23ff1d7320a88c5fdb2ad3e2"
21//! // $ bitcoin-cli gettxoutproof [\"$TXID\"]
22//! let mb_bytes = Vec::from_hex("01000000ba8b9cda965dd8e536670f9ddec10e53aab14b20bacad27b913719\
23//!     0000000000190760b278fe7b8565fda3b968b918d5fd997f993b23674c0af3b6fde300b38f33a5914ce6ed5b\
24//!     1b01e32f570200000002252bf9d75c4f481ebb6278d708257d1f12beb6dd30301d26c623f789b2ba6fc0e2d3\
25//!     2adb5f8ca820731dff234a84e78ec30bce4ec69dbd562d0b2b8266bf4e5a0105").unwrap();
26//! let mb: MerkleBlock = bitcoin::consensus::deserialize(&mb_bytes).unwrap();
27//!
28//! // Authenticate and extract matched transaction ids
29//! let mut matches: Vec<Txid> = vec![];
30//! let mut index: Vec<u32> = vec![];
31//! assert!(mb.extract_matches(&mut matches, &mut index).is_ok());
32//! assert_eq!(1, matches.len());
33//! assert_eq!(
34//!     "5a4ebf66822b0b2d56bd9dc64ece0bc38ee7844a23ff1d7320a88c5fdb2ad3e2".parse::<Txid>().unwrap(),
35//!     matches[0]
36//! );
37//! assert_eq!(1, index.len());
38//! assert_eq!(1, index[0]);
39//! ```
40
41use core::fmt;
42
43use hashes::Hash;
44use io::{Read, Write};
45
46use self::MerkleBlockError::*;
47use crate::blockdata::block::{self, Block, TxMerkleNode};
48use crate::blockdata::transaction::{Transaction, Txid};
49use crate::blockdata::weight::Weight;
50use crate::consensus::encode::{self, Decodable, Encodable, MAX_VEC_SIZE};
51use crate::prelude::*;
52
53/// Data structure that represents a block header paired to a partial merkle tree.
54///
55/// NOTE: This assumes that the given Block has *at least* 1 transaction. If the Block has 0 txs,
56/// it will hit an assertion.
57#[derive(PartialEq, Eq, Clone, Debug)]
58pub struct MerkleBlock {
59    /// The block header
60    pub header: block::Header,
61    /// Transactions making up a partial merkle tree
62    pub txn: PartialMerkleTree,
63}
64
65impl MerkleBlock {
66    /// Create a MerkleBlock from a block, that contains proofs for specific txids.
67    ///
68    /// The `block` is a full block containing the header and transactions and `match_txids` is a
69    /// function that returns true for the ids that should be included in the partial merkle tree.
70    ///
71    /// # Examples
72    ///
73    /// ```rust
74    /// use bitcoin::hash_types::Txid;
75    /// use bitcoin::hex::FromHex;
76    /// use bitcoin::{Block, MerkleBlock};
77    ///
78    /// // Block 80000
79    /// let block_bytes = Vec::from_hex("01000000ba8b9cda965dd8e536670f9ddec10e53aab14b20bacad2\
80    ///     7b9137190000000000190760b278fe7b8565fda3b968b918d5fd997f993b23674c0af3b6fde300b38f33\
81    ///     a5914ce6ed5b1b01e32f5702010000000100000000000000000000000000000000000000000000000000\
82    ///     00000000000000ffffffff0704e6ed5b1b014effffffff0100f2052a01000000434104b68a50eaa0287e\
83    ///     ff855189f949c1c6e5f58b37c88231373d8a59809cbae83059cc6469d65c665ccfd1cfeb75c6e8e19413\
84    ///     bba7fbff9bc762419a76d87b16086eac000000000100000001a6b97044d03da79c005b20ea9c0e1a6d9d\
85    ///     c12d9f7b91a5911c9030a439eed8f5000000004948304502206e21798a42fae0e854281abd38bacd1aee\
86    ///     d3ee3738d9e1446618c4571d1090db022100e2ac980643b0b82c0e88ffdfec6b64e3e6ba35e7ba5fdd7d\
87    ///     5d6cc8d25c6b241501ffffffff0100f2052a010000001976a914404371705fa9bd789a2fcd52d2c580b6\
88    ///     5d35549d88ac00000000").unwrap();
89    /// let block: Block = bitcoin::consensus::deserialize(&block_bytes).unwrap();
90    ///
91    /// // Create a merkle block containing a single transaction
92    /// let txid = "5a4ebf66822b0b2d56bd9dc64ece0bc38ee7844a23ff1d7320a88c5fdb2ad3e2".parse::<Txid>().unwrap();
93    /// let match_txids: Vec<Txid> = vec![txid].into_iter().collect();
94    /// let mb = MerkleBlock::from_block_with_predicate(&block, |t| match_txids.contains(t));
95    ///
96    /// // Authenticate and extract matched transaction ids
97    /// let mut matches: Vec<Txid> = vec![];
98    /// let mut index: Vec<u32> = vec![];
99    /// assert!(mb.extract_matches(&mut matches, &mut index).is_ok());
100    /// assert_eq!(txid, matches[0]);
101    /// ```
102    pub fn from_block_with_predicate<F>(block: &Block, match_txids: F) -> Self
103    where
104        F: Fn(&Txid) -> bool,
105    {
106        let block_txids: Vec<_> = block.txdata.iter().map(Transaction::compute_txid).collect();
107        Self::from_header_txids_with_predicate(&block.header, &block_txids, match_txids)
108    }
109
110    /// Create a MerkleBlock from the block's header and txids, that contain proofs for specific txids.
111    ///
112    /// The `header` is the block header, `block_txids` is the full list of txids included in the block and
113    /// `match_txids` is a function that returns true for the ids that should be included in the partial merkle tree.
114    pub fn from_header_txids_with_predicate<F>(
115        header: &block::Header,
116        block_txids: &[Txid],
117        match_txids: F,
118    ) -> Self
119    where
120        F: Fn(&Txid) -> bool,
121    {
122        let matches: Vec<bool> = block_txids.iter().map(match_txids).collect();
123
124        let pmt = PartialMerkleTree::from_txids(block_txids, &matches);
125        MerkleBlock { header: *header, txn: pmt }
126    }
127
128    /// Extract the matching txid's represented by this partial merkle tree
129    /// and their respective indices within the partial tree.
130    /// returns Ok(()) on success, or error in case of failure
131    pub fn extract_matches(
132        &self,
133        matches: &mut Vec<Txid>,
134        indexes: &mut Vec<u32>,
135    ) -> Result<(), MerkleBlockError> {
136        let merkle_root = self.txn.extract_matches(matches, indexes)?;
137
138        if merkle_root.eq(&self.header.merkle_root) {
139            Ok(())
140        } else {
141            Err(MerkleRootMismatch)
142        }
143    }
144}
145
146impl Encodable for MerkleBlock {
147    fn consensus_encode<W: Write + ?Sized>(&self, w: &mut W) -> Result<usize, io::Error> {
148        let len = self.header.consensus_encode(w)? + self.txn.consensus_encode(w)?;
149        Ok(len)
150    }
151}
152
153impl Decodable for MerkleBlock {
154    fn consensus_decode<R: Read + ?Sized>(r: &mut R) -> Result<Self, encode::Error> {
155        Ok(MerkleBlock {
156            header: Decodable::consensus_decode(r)?,
157            txn: Decodable::consensus_decode(r)?,
158        })
159    }
160}
161
162/// Data structure that represents a partial merkle tree.
163///
164/// It represents a subset of the txid's of a known block, in a way that
165/// allows recovery of the list of txid's and the merkle root, in an
166/// authenticated way.
167///
168/// The encoding works as follows: we traverse the tree in depth-first order,
169/// storing a bit for each traversed node, signifying whether the node is the
170/// parent of at least one matched leaf txid (or a matched txid itself). In
171/// case we are at the leaf level, or this bit is 0, its merkle node hash is
172/// stored, and its children are not explored further. Otherwise, no hash is
173/// stored, but we recurse into both (or the only) child branch. During
174/// decoding, the same depth-first traversal is performed, consuming bits and
175/// hashes as they written during encoding.
176///
177/// The serialization is fixed and provides a hard guarantee about the
178/// encoded size:
179///
180///   SIZE <= 10 + ceil(32.25*N)
181///
182/// Where N represents the number of leaf nodes of the partial tree. N itself
183/// is bounded by:
184///
185///   N <= total_transactions
186///   N <= 1 + matched_transactions*tree_height
187///
188/// The serialization format:
189///  - uint32     total_transactions (4 bytes)
190///  - varint     number of hashes   (1-3 bytes)
191///  - uint256[]  hashes in depth-first order (<= 32*N bytes)
192///  - varint     number of bytes of flag bits (1-3 bytes)
193///  - byte[]     flag bits, packed per 8 in a byte, least significant bit first (<= 2*N-1 bits)
194///
195/// The size constraints follow from this.
196#[derive(PartialEq, Eq, Clone, Debug)]
197pub struct PartialMerkleTree {
198    /// The total number of transactions in the block
199    num_transactions: u32,
200    /// node-is-parent-of-matched-txid bits
201    bits: Vec<bool>,
202    /// Transaction ids and internal hashes
203    hashes: Vec<TxMerkleNode>,
204}
205
206impl PartialMerkleTree {
207    /// Returns the total number of transactions in the block.
208    pub fn num_transactions(&self) -> u32 { self.num_transactions }
209
210    /// Returns the node-is-parent-of-matched-txid bits of the partial merkle tree.
211    pub fn bits(&self) -> &Vec<bool> { &self.bits }
212
213    /// Returns the transaction ids and internal hashes of the partial merkle tree.
214    pub fn hashes(&self) -> &Vec<TxMerkleNode> { &self.hashes }
215
216    /// Construct a partial merkle tree
217    /// The `txids` are the transaction hashes of the block and the `matches` is the contains flags
218    /// wherever a tx hash should be included in the proof.
219    ///
220    /// Panics when `txids` is empty or when `matches` has a different length
221    ///
222    /// # Examples
223    ///
224    /// ```rust
225    /// use bitcoin::hash_types::Txid;
226    /// use bitcoin::hex::FromHex;
227    /// use bitcoin::merkle_tree::{MerkleBlock, PartialMerkleTree};
228    ///
229    /// // Block 80000
230    /// let txids: Vec<Txid> = [
231    ///     "c06fbab289f723c6261d3030ddb6be121f7d2508d77862bb1e484f5cd7f92b25",
232    ///     "5a4ebf66822b0b2d56bd9dc64ece0bc38ee7844a23ff1d7320a88c5fdb2ad3e2",
233    /// ]
234    /// .iter()
235    /// .map(|hex| hex.parse::<Txid>().unwrap())
236    /// .collect();
237    ///
238    /// // Select the second transaction
239    /// let matches = vec![false, true];
240    /// let tree = PartialMerkleTree::from_txids(&txids, &matches);
241    /// assert!(tree.extract_matches(&mut vec![], &mut vec![]).is_ok());
242    /// ```
243    pub fn from_txids(txids: &[Txid], matches: &[bool]) -> Self {
244        // We can never have zero txs in a merkle block, we always need the coinbase tx
245        assert_ne!(txids.len(), 0);
246        assert_eq!(txids.len(), matches.len());
247
248        let mut pmt = PartialMerkleTree {
249            num_transactions: txids.len() as u32,
250            bits: Vec::with_capacity(txids.len()),
251            hashes: vec![],
252        };
253        let height = pmt.calc_tree_height();
254
255        // traverse the partial tree
256        pmt.traverse_and_build(height, 0, txids, matches);
257        pmt
258    }
259
260    /// Extract the matching txid's represented by this partial merkle tree
261    /// and their respective indices within the partial tree.
262    /// returns the merkle root, or error in case of failure
263    pub fn extract_matches(
264        &self,
265        matches: &mut Vec<Txid>,
266        indexes: &mut Vec<u32>,
267    ) -> Result<TxMerkleNode, MerkleBlockError> {
268        matches.clear();
269        indexes.clear();
270        // An empty set will not work
271        if self.num_transactions == 0 {
272            return Err(NoTransactions);
273        };
274        // check for excessively high numbers of transactions
275        if self.num_transactions as u64 > Weight::MAX_BLOCK / Weight::MIN_TRANSACTION {
276            return Err(TooManyTransactions);
277        }
278        // there can never be more hashes provided than one for every txid
279        if self.hashes.len() as u32 > self.num_transactions {
280            return Err(TooManyHashes);
281        };
282        // there must be at least one bit per node in the partial tree, and at least one node per hash
283        if self.bits.len() < self.hashes.len() {
284            return Err(NotEnoughBits);
285        };
286
287        let height = self.calc_tree_height();
288
289        // traverse the partial tree
290        let mut bits_used = 0u32;
291        let mut hash_used = 0u32;
292        let hash_merkle_root =
293            self.traverse_and_extract(height, 0, &mut bits_used, &mut hash_used, matches, indexes)?;
294        // Verify that all bits were consumed (except for the padding caused by
295        // serializing it as a byte sequence)
296        if (bits_used + 7) / 8 != (self.bits.len() as u32 + 7) / 8 {
297            return Err(NotAllBitsConsumed);
298        }
299        // Verify that all hashes were consumed
300        if hash_used != self.hashes.len() as u32 {
301            return Err(NotAllHashesConsumed);
302        }
303        Ok(TxMerkleNode::from_byte_array(hash_merkle_root.to_byte_array()))
304    }
305
306    /// Calculates the height of the tree.
307    fn calc_tree_height(&self) -> u32 {
308        let mut height = 0;
309        while self.calc_tree_width(height) > 1 {
310            height += 1;
311        }
312        height
313    }
314
315    /// Helper function to efficiently calculate the number of nodes at given height
316    /// in the merkle tree
317    #[inline]
318    fn calc_tree_width(&self, height: u32) -> u32 {
319        (self.num_transactions + (1 << height) - 1) >> height
320    }
321
322    /// Calculate the hash of a node in the merkle tree (at leaf level: the txid's themselves)
323    fn calc_hash(&self, height: u32, pos: u32, txids: &[Txid]) -> TxMerkleNode {
324        if height == 0 {
325            // Hash at height 0 is the txid itself
326            TxMerkleNode::from_byte_array(txids[pos as usize].to_byte_array())
327        } else {
328            // Calculate left hash
329            let left = self.calc_hash(height - 1, pos * 2, txids);
330            // Calculate right hash if not beyond the end of the array - copy left hash otherwise
331            let right = if pos * 2 + 1 < self.calc_tree_width(height - 1) {
332                self.calc_hash(height - 1, pos * 2 + 1, txids)
333            } else {
334                left
335            };
336            // Combine subhashes
337            PartialMerkleTree::parent_hash(left, right)
338        }
339    }
340
341    /// Recursive function that traverses tree nodes, storing the data as bits and hashes
342    fn traverse_and_build(&mut self, height: u32, pos: u32, txids: &[Txid], matches: &[bool]) {
343        // Determine whether this node is the parent of at least one matched txid
344        let mut parent_of_match = false;
345        let mut p = pos << height;
346        while p < (pos + 1) << height && p < self.num_transactions {
347            parent_of_match |= matches[p as usize];
348            p += 1;
349        }
350        // Store as flag bit
351        self.bits.push(parent_of_match);
352
353        if height == 0 || !parent_of_match {
354            // If at height 0, or nothing interesting below, store hash and stop
355            let hash = self.calc_hash(height, pos, txids);
356            self.hashes.push(hash);
357        } else {
358            // Otherwise, don't store any hash, but descend into the subtrees
359            self.traverse_and_build(height - 1, pos * 2, txids, matches);
360            if pos * 2 + 1 < self.calc_tree_width(height - 1) {
361                self.traverse_and_build(height - 1, pos * 2 + 1, txids, matches);
362            }
363        }
364    }
365
366    /// Recursive function that traverses tree nodes, consuming the bits and hashes produced by
367    /// TraverseAndBuild. It returns the hash of the respective node and its respective index.
368    fn traverse_and_extract(
369        &self,
370        height: u32,
371        pos: u32,
372        bits_used: &mut u32,
373        hash_used: &mut u32,
374        matches: &mut Vec<Txid>,
375        indexes: &mut Vec<u32>,
376    ) -> Result<TxMerkleNode, MerkleBlockError> {
377        if *bits_used as usize >= self.bits.len() {
378            return Err(BitsArrayOverflow);
379        }
380        let parent_of_match = self.bits[*bits_used as usize];
381        *bits_used += 1;
382        if height == 0 || !parent_of_match {
383            // If at height 0, or nothing interesting below, use stored hash and do not descend
384            if *hash_used as usize >= self.hashes.len() {
385                return Err(HashesArrayOverflow);
386            }
387            let hash = self.hashes[*hash_used as usize];
388            *hash_used += 1;
389            if height == 0 && parent_of_match {
390                // in case of height 0, we have a matched txid
391                matches.push(Txid::from_byte_array(hash.to_byte_array()));
392                indexes.push(pos);
393            }
394            Ok(hash)
395        } else {
396            // otherwise, descend into the subtrees to extract matched txids and hashes
397            let left = self.traverse_and_extract(
398                height - 1,
399                pos * 2,
400                bits_used,
401                hash_used,
402                matches,
403                indexes,
404            )?;
405            let right;
406            if pos * 2 + 1 < self.calc_tree_width(height - 1) {
407                right = self.traverse_and_extract(
408                    height - 1,
409                    pos * 2 + 1,
410                    bits_used,
411                    hash_used,
412                    matches,
413                    indexes,
414                )?;
415                if right == left {
416                    // The left and right branches should never be identical, as the transaction
417                    // hashes covered by them must each be unique.
418                    return Err(IdenticalHashesFound);
419                }
420            } else {
421                right = left;
422            }
423            // and combine them before returning
424            Ok(PartialMerkleTree::parent_hash(left, right))
425        }
426    }
427
428    /// Helper method to produce SHA256D(left + right)
429    fn parent_hash(left: TxMerkleNode, right: TxMerkleNode) -> TxMerkleNode {
430        let mut encoder = TxMerkleNode::engine();
431        left.consensus_encode(&mut encoder).expect("engines don't error");
432        right.consensus_encode(&mut encoder).expect("engines don't error");
433        TxMerkleNode::from_engine(encoder)
434    }
435}
436
437impl Encodable for PartialMerkleTree {
438    fn consensus_encode<W: Write + ?Sized>(&self, w: &mut W) -> Result<usize, io::Error> {
439        let mut ret = self.num_transactions.consensus_encode(w)?;
440        ret += self.hashes.consensus_encode(w)?;
441
442        let nb_bytes_for_bits = (self.bits.len() + 7) / 8;
443        ret += encode::VarInt::from(nb_bytes_for_bits).consensus_encode(w)?;
444        for chunk in self.bits.chunks(8) {
445            let mut byte = 0u8;
446            for (i, bit) in chunk.iter().enumerate() {
447                byte |= (*bit as u8) << i;
448            }
449            ret += byte.consensus_encode(w)?;
450        }
451        Ok(ret)
452    }
453}
454
455impl Decodable for PartialMerkleTree {
456    fn consensus_decode_from_finite_reader<R: Read + ?Sized>(
457        r: &mut R,
458    ) -> Result<Self, encode::Error> {
459        let num_transactions: u32 = Decodable::consensus_decode(r)?;
460        let hashes: Vec<TxMerkleNode> = Decodable::consensus_decode(r)?;
461
462        let nb_bytes_for_bits = encode::VarInt::consensus_decode(r)?.0 as usize;
463        if nb_bytes_for_bits > MAX_VEC_SIZE {
464            return Err(encode::Error::OversizedVectorAllocation {
465                requested: nb_bytes_for_bits,
466                max: MAX_VEC_SIZE,
467            });
468        }
469        let mut bits = vec![false; nb_bytes_for_bits * 8];
470        for chunk in bits.chunks_mut(8) {
471            let byte = u8::consensus_decode(r)?;
472            for (i, bit) in chunk.iter_mut().enumerate() {
473                *bit = (byte & (1 << i)) != 0;
474            }
475        }
476
477        Ok(PartialMerkleTree { num_transactions, hashes, bits })
478    }
479}
480
481/// An error when verifying the merkle block.
482#[derive(Debug, Clone, PartialEq, Eq)]
483#[non_exhaustive]
484pub enum MerkleBlockError {
485    /// Merkle root in the header doesn't match to the root calculated from partial merkle tree.
486    MerkleRootMismatch,
487    /// Partial merkle tree contains no transactions.
488    NoTransactions,
489    /// There are too many transactions.
490    TooManyTransactions,
491    /// There are too many hashes
492    TooManyHashes,
493    /// There must be at least one bit per node in the partial tree,
494    /// and at least one node per hash
495    NotEnoughBits,
496    /// Not all bits were consumed
497    NotAllBitsConsumed,
498    /// Not all hashes were consumed
499    NotAllHashesConsumed,
500    /// Overflowed the bits array
501    BitsArrayOverflow,
502    /// Overflowed the hashes array
503    HashesArrayOverflow,
504    /// The left and right branches should never be identical
505    IdenticalHashesFound,
506}
507
508internals::impl_from_infallible!(MerkleBlockError);
509
510impl fmt::Display for MerkleBlockError {
511    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
512        use MerkleBlockError::*;
513
514        match *self {
515            MerkleRootMismatch => write!(f, "merkle header root doesn't match to the root calculated from the partial merkle tree"),
516            NoTransactions => write!(f, "partial merkle tree contains no transactions"),
517            TooManyTransactions => write!(f, "too many transactions"),
518            TooManyHashes => write!(f, "proof contains more hashes than transactions"),
519            NotEnoughBits => write!(f, "proof contains less bits than hashes"),
520            NotAllBitsConsumed => write!(f, "not all bit were consumed"),
521            NotAllHashesConsumed => write!(f, "not all hashes were consumed"),
522            BitsArrayOverflow => write!(f, "overflowed the bits array"),
523            HashesArrayOverflow => write!(f, "overflowed the hashes array"),
524            IdenticalHashesFound => write!(f, "found identical transaction hashes"),
525        }
526    }
527}
528
529#[cfg(feature = "std")]
530impl std::error::Error for MerkleBlockError {
531    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
532        use MerkleBlockError::*;
533
534        match *self {
535            MerkleRootMismatch | NoTransactions | TooManyTransactions | TooManyHashes
536            | NotEnoughBits | NotAllBitsConsumed | NotAllHashesConsumed | BitsArrayOverflow
537            | HashesArrayOverflow | IdenticalHashesFound => None,
538        }
539    }
540}
541
542#[cfg(test)]
543mod tests {
544    use hex::test_hex_unwrap as hex;
545    #[cfg(feature = "rand-std")]
546    use secp256k1::rand::prelude::*;
547
548    use super::*;
549    use crate::consensus::encode::{deserialize, serialize};
550
551    #[cfg(feature = "rand-std")]
552    macro_rules! pmt_tests {
553        ($($name:ident),* $(,)?) => {
554            $(
555                #[test]
556                fn $name() {
557                    pmt_test_from_name(stringify!($name));
558                }
559            )*
560        }
561    }
562
563    #[cfg(feature = "rand-std")]
564    pmt_tests!(
565        pmt_test_1,
566        pmt_test_4,
567        pmt_test_7,
568        pmt_test_17,
569        pmt_test_56,
570        pmt_test_100,
571        pmt_test_127,
572        pmt_test_256,
573        pmt_test_312,
574        pmt_test_513,
575        pmt_test_1000,
576        pmt_test_4095
577    );
578
579    /// Parses the transaction count out of `name` with form: `pmt_test_$num`.
580    #[cfg(feature = "rand-std")]
581    fn pmt_test_from_name(name: &str) { pmt_test(name[9..].parse().unwrap()) }
582
583    #[cfg(feature = "rand-std")]
584    fn pmt_test(tx_count: usize) {
585        use core::cmp::min;
586
587        use crate::merkle_tree;
588
589        let mut rng = thread_rng();
590        // Create some fake tx ids
591        let tx_ids = (1..=tx_count)
592            .map(|i| format!("{:064x}", i).parse::<Txid>().unwrap())
593            .collect::<Vec<_>>();
594
595        // Calculate the merkle root and height
596        let hashes = tx_ids.iter().map(|t| t.to_raw_hash());
597        let merkle_root_1: TxMerkleNode =
598            merkle_tree::calculate_root(hashes).expect("hashes is not empty").into();
599        let mut height = 1;
600        let mut ntx = tx_count;
601        while ntx > 1 {
602            ntx = (ntx + 1) / 2;
603            height += 1;
604        }
605
606        // Check with random subsets with inclusion chances 1, 1/2, 1/4, ..., 1/128
607        for att in 1..15 {
608            let mut matches = vec![false; tx_count];
609            let mut match_txid1 = vec![];
610            for j in 0..tx_count {
611                // Generate `att / 2` random bits
612                let rand_bits = match att / 2 {
613                    0 => 0,
614                    bits => rng.gen::<u64>() >> (64 - bits),
615                };
616                let include = rand_bits == 0;
617                matches[j] = include;
618
619                if include {
620                    match_txid1.push(tx_ids[j]);
621                };
622            }
623
624            // Build the partial merkle tree
625            let pmt1 = PartialMerkleTree::from_txids(&tx_ids, &matches);
626            let serialized = serialize(&pmt1);
627
628            // Verify PartialMerkleTree's size guarantees
629            let n = min(tx_count, 1 + match_txid1.len() * height);
630            assert!(serialized.len() <= 10 + (258 * n + 7) / 8);
631
632            // Deserialize into a tester copy
633            let pmt2: PartialMerkleTree =
634                deserialize(&serialized).expect("Could not deserialize own data");
635
636            // Extract merkle root and matched txids from copy
637            let mut match_txid2: Vec<Txid> = vec![];
638            let mut indexes = vec![];
639            let merkle_root_2 = pmt2
640                .extract_matches(&mut match_txid2, &mut indexes)
641                .expect("Could not extract matches");
642
643            // Check that it has the same merkle root as the original, and a valid one
644            assert_eq!(merkle_root_1, merkle_root_2);
645            assert_ne!(merkle_root_2, TxMerkleNode::all_zeros());
646
647            // check that it contains the matched transactions (in the same order!)
648            assert_eq!(match_txid1, match_txid2);
649
650            // check that random bit flips break the authentication
651            for _ in 0..4 {
652                let mut pmt3: PartialMerkleTree = deserialize(&serialized).unwrap();
653                pmt3.damage(&mut rng);
654                let mut match_txid3 = vec![];
655                let merkle_root_3 = pmt3.extract_matches(&mut match_txid3, &mut indexes).unwrap();
656                assert_ne!(merkle_root_3, merkle_root_1);
657            }
658        }
659    }
660
661    #[test]
662    fn pmt_malleability() {
663        // Create some fake tx ids with the last 2 hashes repeating
664        let txids: Vec<Txid> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 10]
665            .iter()
666            .map(|i| format!("{:064x}", i).parse::<Txid>().unwrap())
667            .collect();
668
669        let matches =
670            vec![false, false, false, false, false, false, false, false, false, true, true, false];
671
672        let tree = PartialMerkleTree::from_txids(&txids, &matches);
673        // Should fail due to duplicate txs found
674        let result = tree.extract_matches(&mut vec![], &mut vec![]);
675        assert!(result.is_err());
676    }
677
678    #[test]
679    fn merkleblock_serialization() {
680        // Got it by running the rpc call
681        // `gettxoutproof '["220ebc64e21abece964927322cba69180ed853bb187fbc6923bac7d010b9d87a"]'`
682        let mb_hex = include_str!("../../tests/data/merkle_block.hex");
683
684        let mb: MerkleBlock = deserialize(&hex!(mb_hex)).unwrap();
685        assert_eq!(get_block_13b8a().block_hash(), mb.header.block_hash());
686        assert_eq!(
687            mb.header.merkle_root,
688            mb.txn.extract_matches(&mut vec![], &mut vec![]).unwrap()
689        );
690        // Serialize again and check that it matches the original bytes
691        assert_eq!(mb_hex, serialize(&mb).to_lower_hex_string().as_str());
692    }
693
694    /// Create a CMerkleBlock using a list of txids which will be found in the
695    /// given block.
696    #[test]
697    fn merkleblock_construct_from_txids_found() {
698        let block = get_block_13b8a();
699
700        let txids: Vec<Txid> = [
701            "74d681e0e03bafa802c8aa084379aa98d9fcd632ddc2ed9782b586ec87451f20",
702            "f9fc751cb7dc372406a9f8d738d5e6f8f63bab71986a39cf36ee70ee17036d07",
703        ]
704        .iter()
705        .map(|hex| hex.parse::<Txid>().unwrap())
706        .collect();
707
708        let txid1 = txids[0];
709        let txid2 = txids[1];
710        let txids = [txid1, txid2];
711
712        let merkle_block = MerkleBlock::from_block_with_predicate(&block, |t| txids.contains(t));
713
714        assert_eq!(merkle_block.header.block_hash(), block.block_hash());
715
716        let mut matches: Vec<Txid> = vec![];
717        let mut index: Vec<u32> = vec![];
718
719        assert_eq!(
720            merkle_block.txn.extract_matches(&mut matches, &mut index).unwrap(),
721            block.header.merkle_root
722        );
723        assert_eq!(matches.len(), 2);
724
725        // Ordered by occurrence in depth-first tree traversal.
726        assert_eq!(matches[0], txid2);
727        assert_eq!(index[0], 1);
728
729        assert_eq!(matches[1], txid1);
730        assert_eq!(index[1], 8);
731    }
732
733    /// Create a CMerkleBlock using a list of txids which will not be found in the given block
734    #[test]
735    fn merkleblock_construct_from_txids_not_found() {
736        let block = get_block_13b8a();
737        let txids: Vec<Txid> = ["c0ffee00003bafa802c8aa084379aa98d9fcd632ddc2ed9782b586ec87451f20"]
738            .iter()
739            .map(|hex| hex.parse::<Txid>().unwrap())
740            .collect();
741
742        let merkle_block = MerkleBlock::from_block_with_predicate(&block, |t| txids.contains(t));
743
744        assert_eq!(merkle_block.header.block_hash(), block.block_hash());
745
746        let mut matches: Vec<Txid> = vec![];
747        let mut index: Vec<u32> = vec![];
748
749        assert_eq!(
750            merkle_block.txn.extract_matches(&mut matches, &mut index).unwrap(),
751            block.header.merkle_root
752        );
753        assert_eq!(matches.len(), 0);
754        assert_eq!(index.len(), 0);
755    }
756
757    #[cfg(feature = "rand-std")]
758    impl PartialMerkleTree {
759        /// Flip one bit in one of the hashes - this should break the authentication
760        fn damage(&mut self, rng: &mut ThreadRng) {
761            let n = rng.gen_range(0..self.hashes.len());
762            let bit = rng.gen::<u8>();
763            let hashes = &mut self.hashes;
764            let mut hash = hashes[n].to_byte_array();
765            hash[(bit >> 3) as usize] ^= 1 << (bit & 7);
766            hashes[n] = TxMerkleNode::from_slice(&hash).unwrap();
767        }
768    }
769
770    /// Returns a real block (0000000000013b8ab2cd513b0261a14096412195a72a0c4827d229dcc7e0f7af)
771    /// with 9 txs.
772    fn get_block_13b8a() -> Block {
773        use hex::FromHex;
774        let block_hex = include_str!("../../tests/data/block_13b8a.hex");
775        deserialize(&Vec::from_hex(block_hex).unwrap()).unwrap()
776    }
777
778    macro_rules! check_calc_tree_width {
779        ($($test_name:ident, $num_transactions:literal, $height:literal, $expected_width:literal);* $(;)?) => {
780            $(
781                #[test]
782                fn $test_name() {
783                    let pmt = PartialMerkleTree {
784                        num_transactions: $num_transactions,
785                        bits: vec![],
786                        hashes: vec![],
787                    };
788                    let got = pmt.calc_tree_width($height);
789                    assert_eq!(got, $expected_width)
790                }
791            )*
792        }
793    }
794
795    // tree_width_<id> <num txs> <height> <expected_width>
796    //
797    // height 0 is the bottom of the tree, where the leaves are.
798    check_calc_tree_width! {
799        tree_width_01, 1, 0, 1;
800        //
801        tree_width_02, 2, 0, 2;
802        tree_width_03, 2, 1, 1;
803        //
804        tree_width_04, 3, 0, 3;
805        tree_width_05, 3, 1, 2;
806        tree_width_06, 3, 2, 1;
807        //
808        tree_width_07, 4, 0, 4;
809        tree_width_08, 4, 1, 2;
810        tree_width_09, 4, 2, 1;
811        //
812        tree_width_10, 5, 0, 5;
813        tree_width_11, 5, 1, 3;
814        tree_width_12, 5, 2, 2;
815        tree_width_13, 5, 3, 1;
816        //
817        tree_width_14, 6, 0, 6;
818        tree_width_15, 6, 1, 3;
819        tree_width_16, 6, 2, 2;
820        tree_width_17, 6, 3, 1;
821        //
822        tree_width_18, 7, 0, 7;
823        tree_width_19, 7, 1, 4;
824        tree_width_20, 7, 2, 2;
825        tree_width_21, 7, 3, 1;
826    }
827
828    #[test]
829    fn regression_2606() {
830        // Attempt
831        let bytes = hex!(
832            "000006000000000000000004ee00000004c7f1ccb1000000ffff000000010000\
833             0000ffffffffff1f000000000400000000000002000000000500000000000000\
834             000000000300000000000003000000000200000000ff00000000c7f1ccb10407\
835             00000000000000ccb100c76538b100000004bfa9c251681b1b00040000000025\
836             00000004bfaac251681b1b25\
837         "
838        );
839        let deser = crate::consensus::deserialize::<MerkleBlock>(&bytes);
840        assert!(deser.is_err());
841    }
842}
bitcoin/merkle_tree/block.rs

bitcoin/merkle_tree/
block.rs
