Public commit record
68/100 · Adequate
What the developer wrote
Authored by rustaceanrob
Move `MerkleBlock` to `p2p`
Moves the module into a duplicate named `merkle_tree` module, fixes all
of the new lints, moves the test vectors to a new folder that mirrors
that of `bitcoin`, and updates all available `primitives` imports.
✓ Descriptive subject✓ Provides detailed explanatory context✓ Mentions testing or verification
What changed, and why it matters
This commit is a straightforward code reorganization: it moves the MerkleBlock and PartialMerkleTree implementation from the main `bitcoin` crate into the `p2p` crate, where it is more logically grouped with peer-to-peer message types. The actual logic, tests, and test data files are copied almost unchanged. There is no indication this fixes or introduces a security vulnerability.
Recommended action
No security action needed. Treat as a normal refactoring/reorganization commit. Reviewers may want to verify that downstream users relying on `bitcoin::MerkleBlock` have a migration path to `bitcoin_p2p_messages::merkle_tree::MerkleBlock` (or the new crate path), but this is an API-change concern, not a security issue.
Security signals we found
No strong security signals were identified.
Evidence from the diff
The change relocates MerkleBlock/PartialMerkleTree from bitcoin/src/merkle_tree/block.rs to p2p/src/merkle_tree.rs, updates imports to use primitives and bitcoin::consensus where appropriate, removes the re-export from bitcoin, and moves the test hex fixtures from bitcoin/tests/data/ to p2p/tests/data/. The implementation code is functionally identical, including all validation checks and test cases. No security-relevant behavior was modified.
Changed components
bitcoin/src/lib.rsbitcoin/src/merkle_tree/mod.rsp2p/src/lib.rsp2p/src/merkle_tree.rsp2p/src/message.rsp2p/tests/data/block_13b8a.hexp2p/tests/data/merkle_block.hexInspect captured patch +900 / −896
diff --git a/bitcoin/src/lib.rs b/bitcoin/src/lib.rs
index 43f2ba0a..11478557 100644
--- a/bitcoin/src/lib.rs
+++ b/bitcoin/src/lib.rs
@@ -180,7 +180,6 @@ pub use crate::{
crypto::ecdsa,
crypto::key::{self, CompressedPublicKey, Keypair, PrivateKey, PublicKey, XOnlyPublicKey},
crypto::sighash::{self, LegacySighash, SegwitV0Sighash, TapSighash, TapSighashTag},
- merkle_tree::MerkleBlock,
network::params::{self, Params},
network::{Network, NetworkKind, TestnetVersion},
pow::{Target, Work},
diff --git a/bitcoin/src/merkle_tree/block.rs b/bitcoin/src/merkle_tree/block.rs
deleted file mode 100644
index 18c8eef7..00000000
--- a/bitcoin/src/merkle_tree/block.rs
+++ /dev/null
@@ -1,889 +0,0 @@
-// SPDX-License-Identifier: CC0-1.0
-//
-// This code was translated from merkleblock.h, merkleblock.cpp and pmt_tests.cpp
-// Copyright (c) 2009-2010 Satoshi Nakamoto
-// Copyright (c) 2009-2018 The Bitcoin Core developers
-// SPDX-License-Identifier: MIT
-
-//! Merkle Block and Partial Merkle Tree.
-//!
-//! Support proofs that transaction(s) belong to a block.
-
-use core::convert::Infallible;
-use core::fmt;
-
-#[cfg(feature = "arbitrary")]
-use arbitrary::{Arbitrary, Unstructured};
-use internals::ToU64 as _;
-use io::{BufRead, Write};
-
-use crate::block::{self, Block, Checked};
-use crate::consensus::encode::{self, Decodable, Encodable, ReadExt, WriteExt, MAX_VEC_SIZE};
-use crate::merkle_tree::TxMerkleNode;
-use crate::prelude::Vec;
-use crate::transaction::{Transaction, Txid};
-use crate::Weight;
-
-/// Data structure that represents a block header paired to a partial Merkle tree.
-///
-/// NOTE: This assumes that the given Block has *at least* 1 transaction. If the Block has 0 txs,
-/// it will hit an assertion.
-#[derive(PartialEq, Eq, Clone, Debug)]
-pub struct MerkleBlock {
- /// The block header
- pub header: block::Header,
- /// Transactions making up a partial Merkle tree
- pub txn: PartialMerkleTree,
-}
-
-impl MerkleBlock {
- /// Constructs a new MerkleBlock from a block, that contains proofs for specific txids.
- ///
- /// The `block` is a full block containing the header and transactions and `match_txids` is a
- /// function that returns true for the ids that should be included in the partial Merkle tree.
- ///
- /// # Examples
- ///
- /// ```rust
- /// use bitcoin::hex::FromHex;
- /// use bitcoin::{Block, MerkleBlock, Txid};
- ///
- /// // Block 80000
- /// let block_bytes = Vec::from_hex("01000000ba8b9cda965dd8e536670f9ddec10e53aab14b20bacad2\
- /// 7b9137190000000000190760b278fe7b8565fda3b968b918d5fd997f993b23674c0af3b6fde300b38f33\
- /// a5914ce6ed5b1b01e32f5702010000000100000000000000000000000000000000000000000000000000\
- /// 00000000000000ffffffff0704e6ed5b1b014effffffff0100f2052a01000000434104b68a50eaa0287e\
- /// ff855189f949c1c6e5f58b37c88231373d8a59809cbae83059cc6469d65c665ccfd1cfeb75c6e8e19413\
- /// bba7fbff9bc762419a76d87b16086eac000000000100000001a6b97044d03da79c005b20ea9c0e1a6d9d\
- /// c12d9f7b91a5911c9030a439eed8f5000000004948304502206e21798a42fae0e854281abd38bacd1aee\
- /// d3ee3738d9e1446618c4571d1090db022100e2ac980643b0b82c0e88ffdfec6b64e3e6ba35e7ba5fdd7d\
- /// 5d6cc8d25c6b241501ffffffff0100f2052a010000001976a914404371705fa9bd789a2fcd52d2c580b6\
- /// 5d35549d88ac00000000").unwrap();
- /// let block: Block = bitcoin::consensus::deserialize(&block_bytes).unwrap();
- /// let block = block.validate().expect("valid block");
- ///
- /// // Constructs a new Merkle block containing a single transaction
- /// let txid = "5a4ebf66822b0b2d56bd9dc64ece0bc38ee7844a23ff1d7320a88c5fdb2ad3e2".parse::<Txid>().unwrap();
- /// let match_txids: Vec<Txid> = vec![txid].into_iter().collect();
- /// let mb = MerkleBlock::from_block_with_predicate(&block, |t| match_txids.contains(t));
- ///
- /// // Authenticate and extract matched transaction ids
- /// let mut matches: Vec<Txid> = vec![];
- /// let mut index: Vec<u32> = vec![];
- /// assert!(mb.extract_matches(&mut matches, &mut index).is_ok());
- /// assert_eq!(txid, matches[0]);
- /// ```
- pub fn from_block_with_predicate<F>(block: &Block<Checked>, match_txids: F) -> Self
- where
- F: Fn(&Txid) -> bool,
- {
- let block_txids: Vec<_> =
- block.transactions().iter().map(Transaction::compute_txid).collect();
- Self::from_header_txids_with_predicate(block.header(), &block_txids, match_txids)
- }
-
- /// Constructs a new MerkleBlock from the block's header and txids, that contain proofs for specific txids.
- ///
- /// The `header` is the block header, `block_txids` is the full list of txids included in the block and
- /// `match_txids` is a function that returns true for the ids that should be included in the partial Merkle tree.
- pub fn from_header_txids_with_predicate<F>(
- header: &block::Header,
- block_txids: &[Txid],
- match_txids: F,
- ) -> Self
- where
- F: Fn(&Txid) -> bool,
- {
- let matches: Vec<bool> = block_txids.iter().map(match_txids).collect();
-
- let pmt = PartialMerkleTree::from_txids(block_txids, &matches);
- Self { header: *header, txn: pmt }
- }
-
- /// Extracts the matching txid's represented by this partial Merkle tree
- /// and their respective indices within the partial tree.
- /// returns Ok(()) on success, or error in case of failure
- pub fn extract_matches(
- &self,
- matches: &mut Vec<Txid>,
- indexes: &mut Vec<u32>,
- ) -> Result<(), MerkleBlockError> {
- let merkle_root = self.txn.extract_matches(matches, indexes)?;
-
- if merkle_root.eq(&self.header.merkle_root) {
- Ok(())
- } else {
- Err(MerkleBlockError::MerkleRootMismatch)
- }
- }
-}
-
-impl Encodable for MerkleBlock {
- fn consensus_encode<W: Write + ?Sized>(&self, w: &mut W) -> Result<usize, io::Error> {
- let len = self.header.consensus_encode(w)? + self.txn.consensus_encode(w)?;
- Ok(len)
- }
-}
-
-impl Decodable for MerkleBlock {
- fn consensus_decode<R: BufRead + ?Sized>(r: &mut R) -> Result<Self, encode::Error> {
- Ok(Self { header: Decodable::consensus_decode(r)?, txn: Decodable::consensus_decode(r)? })
- }
-}
-
-/// 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 are 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)
-/// - CompactSize number of hashes (1-3 bytes)
-/// - uint256[] hashes in depth-first order (<= 32*N bytes)
-/// - CompactSize 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.
-#[derive(PartialEq, Eq, Clone, Debug)]
-pub struct PartialMerkleTree {
- /// The total number of transactions in the block
- num_transactions: u32,
- /// node-is-parent-of-matched-txid bits
- bits: Vec<bool>,
- /// Transaction ids and internal hashes
- hashes: Vec<TxMerkleNode>,
-}
-
-impl PartialMerkleTree {
- /// Returns the total number of transactions in the block.
- pub fn num_transactions(&self) -> u32 { self.num_transactions }
-
- /// Returns the node-is-parent-of-matched-txid bits of the partial Merkle tree.
- pub fn bits(&self) -> &Vec<bool> { &self.bits }
-
- /// Returns the transaction ids and internal hashes of the partial Merkle tree.
- pub fn hashes(&self) -> &Vec<TxMerkleNode> { &self.hashes }
-
- /// Constructs a new partial Merkle tree.
- ///
- /// The `txids` are the transaction hashes of the block and `matches` contains flags indicating
- /// whether each txid should be included in the proof.
- ///
- /// # Panics
- ///
- /// Panics when `txids` is empty or when `matches` has a different length.
- ///
- /// # Examples
- ///
- /// ```rust
- /// use bitcoin::Txid;
- /// use bitcoin::merkle_tree::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 from_txids(txids: &[Txid], matches: &[bool]) -> Self {
- // We can never have zero txs in a Merkle block, we always need the coinbase tx
- assert_ne!(txids.len(), 0);
- assert_eq!(txids.len(), matches.len());
-
- let mut pmt = Self {
- num_transactions: txids.len() as u32,
- bits: Vec::with_capacity(txids.len()),
- hashes: vec![],
- };
- let height = pmt.calc_tree_height();
-
- // traverse the partial tree
- pmt.traverse_and_build(height, 0, txids, matches);
- pmt
- }
-
- /// Extracts 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
- pub fn extract_matches(
- &self,
- matches: &mut Vec<Txid>,
- indexes: &mut Vec<u32>,
- ) -> Result<TxMerkleNode, MerkleBlockError> {
- matches.clear();
- indexes.clear();
- // An empty set will not work
- if self.num_transactions == 0 {
- return Err(MerkleBlockError::NoTransactions);
- };
- // check for excessively high numbers of transactions
- if self.num_transactions.to_u64() > Weight::MAX_BLOCK / Weight::MIN_TRANSACTION {
- return Err(MerkleBlockError::TooManyTransactions);
- }
- // there can never be more hashes provided than one for every txid
- if self.hashes.len() as u32 > self.num_transactions {
- return Err(MerkleBlockError::TooManyHashes);
- };
- // there must be at least one bit per node in the partial tree, and at least one node per hash
- if self.bits.len() < self.hashes.len() {
- return Err(MerkleBlockError::NotEnoughBits);
- };
-
- let height = self.calc_tree_height();
-
- // traverse the partial tree
- let mut bits_used = 0u32;
- let mut hash_used = 0u32;
- let hash_merkle_root =
- self.traverse_and_extract(height, 0, &mut bits_used, &mut hash_used, matches, indexes)?;
- // Verify that all bits were consumed (except for the padding caused by
- // serializing it as a byte sequence)
- if bits_used.div_ceil(8) != self.bits.len().div_ceil(8) as u32 {
- return Err(MerkleBlockError::NotAllBitsConsumed);
- }
- // Verify that all hashes were consumed
- if hash_used != self.hashes.len() as u32 {
- return Err(MerkleBlockError::NotAllHashesConsumed);
- }
- Ok(hash_merkle_root)
- }
-
- /// Calculates the height of the tree.
- fn calc_tree_height(&self) -> u32 {
- let mut height = 0;
- while self.calc_tree_width(height) > 1 {
- height += 1;
- }
- height
- }
-
- /// Helper function to efficiently calculate the number of nodes at given height
- /// in the Merkle tree
- #[inline]
- fn calc_tree_width(&self, height: u32) -> u32 {
- (self.num_transactions + (1 << height) - 1) >> height
- }
-
- /// Calculates the hash of a node in the Merkle tree (at leaf level: the txid's themselves)
- fn calc_hash(&self, height: u32, pos: u32, txids: &[Txid]) -> TxMerkleNode {
- if height == 0 {
- // Hash at height 0 is the txid itself
- TxMerkleNode::from_byte_array(txids[pos as usize].to_byte_array())
- } else {
- // Calculate left hash
- let left = self.calc_hash(height - 1, pos * 2, txids);
- // Calculate right hash if not beyond the end of the array - copy left hash otherwise
- let right = if pos * 2 + 1 < self.calc_tree_width(height - 1) {
- self.calc_hash(height - 1, pos * 2 + 1, txids)
- } else {
- left
- };
- // Combine subhashes
- left.combine(&right)
- }
- }
-
- /// Recursive function that traverses tree nodes, storing the data as bits and hashes
- fn traverse_and_build(&mut self, height: u32, pos: u32, txids: &[Txid], matches: &[bool]) {
- // Determine whether this node is the parent of at least one matched txid
- let mut parent_of_match = false;
- let mut p = pos << height;
- while p < (pos + 1) << height && p < self.num_transactions {
- parent_of_match |= matches[p as usize];
- p += 1;
- }
- // Store as flag bit
- self.bits.push(parent_of_match);
-
- if height == 0 || !parent_of_match {
- // If at height 0, or nothing interesting below, store hash and stop
- let hash = self.calc_hash(height, pos, txids);
- self.hashes.push(hash);
- } else {
- // Otherwise, don't store any hash, but descend into the subtrees
- self.traverse_and_build(height - 1, pos * 2, txids, matches);
- if pos * 2 + 1 < self.calc_tree_width(height - 1) {
- self.traverse_and_build(height - 1, pos * 2 + 1, txids, matches);
- }
- }
- }
-
- /// 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.
- fn traverse_and_extract(
- &self,
- height: u32,
- pos: u32,
- bits_used: &mut u32,
- hash_used: &mut u32,
- matches: &mut Vec<Txid>,
- indexes: &mut Vec<u32>,
- ) -> Result<TxMerkleNode, MerkleBlockError> {
- if *bits_used as usize >= self.bits.len() {
- return Err(MerkleBlockError::BitsArrayOverflow);
- }
- let parent_of_match = self.bits[*bits_used as usize];
- *bits_used += 1;
- if height == 0 || !parent_of_match {
- // If at height 0, or nothing interesting below, use stored hash and do not descend
- if *hash_used as usize >= self.hashes.len() {
- return Err(MerkleBlockError::HashesArrayOverflow);
- }
- let hash = self.hashes[*hash_used as usize];
- *hash_used += 1;
- if height == 0 && parent_of_match {
- // in case of height 0, we have a matched txid
- matches.push(Txid::from_byte_array(hash.to_byte_array()));
- indexes.push(pos);
- }
- Ok(hash)
- } else {
- // otherwise, descend into the subtrees to extract matched txids and hashes
- let left = self.traverse_and_extract(
- height - 1,
- pos * 2,
- bits_used,
- hash_used,
- matches,
- indexes,
- )?;
- let right;
- if pos * 2 + 1 < self.calc_tree_width(height - 1) {
- right = self.traverse_and_extract(
- height - 1,
- pos * 2 + 1,
- bits_used,
- hash_used,
- matches,
- indexes,
- )?;
- if right == left {
- // The left and right branches should never be identical, as the transaction
- // hashes covered by them must each be unique.
- return Err(MerkleBlockError::IdenticalHashesFound);
- }
- } else {
- right = left;
- }
- // and combine them before returning
- Ok(left.combine(&right))
- }
- }
-}
-
-impl Encodable for PartialMerkleTree {
- fn consensus_encode<W: Write + ?Sized>(&self, w: &mut W) -> Result<usize, io::Error> {
- let mut ret = self.num_transactions.consensus_encode(w)?;
- ret += self.hashes.consensus_encode(w)?;
-
- let nb_bytes_for_bits = self.bits.len().div_ceil(8);
- ret += w.emit_compact_size(nb_bytes_for_bits)?;
- for chunk in self.bits.chunks(8) {
- let mut byte = 0u8;
- for (i, bit) in chunk.iter().enumerate() {
- byte |= (*bit as u8) << i;
- }
- ret += byte.consensus_encode(w)?;
- }
- Ok(ret)
- }
-}
-
-impl Decodable for PartialMerkleTree {
- fn consensus_decode_from_finite_reader<R: BufRead + ?Sized>(
- r: &mut R,
- ) -> Result<Self, encode::Error> {
- let num_transactions: u32 = Decodable::consensus_decode(r)?;
- let hashes: Vec<TxMerkleNode> = Decodable::consensus_decode(r)?;
-
- let nb_bytes_for_bits = r.read_compact_size()? as usize;
- if nb_bytes_for_bits > MAX_VEC_SIZE {
- return Err(encode::ParseError::OversizedVectorAllocation {
- requested: nb_bytes_for_bits,
- max: MAX_VEC_SIZE,
- }
- .into());
- }
- let mut bits = vec![false; nb_bytes_for_bits * 8];
- for chunk in bits.chunks_mut(8) {
- let byte = u8::consensus_decode(r)?;
- for (i, bit) in chunk.iter_mut().enumerate() {
- *bit = (byte & (1 << i)) != 0;
- }
- }
-
- Ok(Self { num_transactions, hashes, bits })
- }
-}
-
-/// An error when verifying the Merkle block.
-#[derive(Debug, Clone, PartialEq, Eq)]
-#[non_exhaustive]
-pub enum MerkleBlockError {
- /// Merkle root in the header doesn't match to the root calculated from partial Merkle tree.
- MerkleRootMismatch,
- /// Partial Merkle tree contains no transactions.
- NoTransactions,
- /// There are too many transactions.
- TooManyTransactions,
- /// There are too many hashes
- TooManyHashes,
- /// There must be at least one bit per node in the partial tree,
- /// and at least one node per hash
- NotEnoughBits,
- /// Not all bits were consumed
- NotAllBitsConsumed,
- /// Not all hashes were consumed
- NotAllHashesConsumed,
- /// Overflowed the bits array
- BitsArrayOverflow,
- /// Overflowed the hashes array
- HashesArrayOverflow,
- /// The left and right branches should never be identical
- IdenticalHashesFound,
-}
-
-impl From<Infallible> for MerkleBlockError {
- fn from(never: Infallible) -> Self { match never {} }
-}
-
-impl fmt::Display for MerkleBlockError {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
- match self {
- Self::MerkleRootMismatch => write!(f, "Merkle header root doesn't match to the root calculated from the partial Merkle tree"),
- Self::NoTransactions => write!(f, "partial Merkle tree contains no transactions"),
- Self::TooManyTransactions => write!(f, "too many transactions"),
- Self::TooManyHashes => write!(f, "proof contains more hashes than transactions"),
- Self::NotEnoughBits => write!(f, "proof contains fewer bits than hashes"),
- Self::NotAllBitsConsumed => write!(f, "not all bits were consumed"),
- Self::NotAllHashesConsumed => write!(f, "not all hashes were consumed"),
- Self::BitsArrayOverflow => write!(f, "overflowed the bits array"),
- Self::HashesArrayOverflow => write!(f, "overflowed the hashes array"),
- Self::IdenticalHashesFound => write!(f, "found identical transaction hashes"),
- }
- }
-}
-
-#[cfg(feature = "std")]
-impl std::error::Error for MerkleBlockError {
- fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
- match self {
- Self::MerkleRootMismatch
- | Self::NoTransactions
- | Self::TooManyTransactions
- | Self::TooManyHashes
- | Self::NotEnoughBits
- | Self::NotAllBitsConsumed
- | Self::NotAllHashesConsumed
- | Self::BitsArrayOverflow
- | Self::HashesArrayOverflow
- | Self::IdenticalHashesFound => None,
- }
- }
-}
-
-#[cfg(feature = "arbitrary")]
-impl<'a> Arbitrary<'a> for PartialMerkleTree {
- fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
- Ok(Self {
- num_transactions: u.arbitrary()?,
- bits: Vec::<bool>::arbitrary(u)?,
- hashes: Vec::<TxMerkleNode>::arbitrary(u)?,
- })
- }
-}
-
-#[cfg(feature = "arbitrary")]
-impl<'a> Arbitrary<'a> for MerkleBlock {
- fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
- Ok(Self { header: u.arbitrary()?, txn: u.arbitrary()? })
- }
-}
-
-#[cfg(test)]
-mod tests {
- use core::cmp;
-
- use hex::{DisplayHex, FromHex};
- use hex_lit::hex;
-
- use super::*;
- use crate::block::Unchecked;
- use crate::consensus::encode;
- use crate::Txid;
-
- // `bloc` in hex.
- const PRNG_SEED: usize = 0x626C6F63;
-
- // Simple and deterministic PRNG, not suitable for cryptographic use cases.
- struct LcgPrng {
- state: usize,
- }
-
- impl LcgPrng {
- const P: usize = 1039;
- const Q: usize = 677;
-
- const fn new(seed: usize) -> Self { Self { state: seed } }
-
- #[inline]
- fn next_usize(&mut self) -> usize {
- self.state = self.state.wrapping_mul(Self::P).wrapping_add(Self::Q);
- self.state
- }
-
- #[inline]
- fn next_in_range(&mut self, max: usize) -> usize { self.next_usize() % max }
-
- #[inline]
- fn next_u8(&mut self) -> u8 { self.next_usize().to_le_bytes()[0] }
- }
-
- macro_rules! pmt_tests {
- ($($name:ident),* $(,)?) => {
- $(
- #[test]
- fn $name() {
- pmt_test_from_name(stringify!($name));
- }
- )*
- }
- }
-
- pmt_tests!(
- pmt_test_1,
- pmt_test_4,
- pmt_test_7,
- pmt_test_17,
- pmt_test_56,
- pmt_test_100,
- pmt_test_127,
- pmt_test_256,
- pmt_test_312,
- pmt_test_513,
- pmt_test_1000,
- pmt_test_4095
- );
-
- /// Parses the transaction count out of `name` with form: `pmt_test_$num`.
- fn pmt_test_from_name(name: &str) { pmt_test(name[9..].parse().unwrap()) }
-
- fn pmt_test(tx_count: usize) {
- let mut rng = LcgPrng::new(PRNG_SEED ^ tx_count);
- // Create some fake tx ids
- let tx_ids = (1..=tx_count)
- .map(|i| format!("{:064x}", i).parse::<Txid>().unwrap())
- .collect::<Vec<_>>();
-
- // Calculate the Merkle root and height
- let hashes = tx_ids.iter().copied();
- let merkle_root_1 = TxMerkleNode::calculate_root(hashes).expect("hashes is not empty");
- let mut height = 1;
- let mut ntx = tx_count;
- while ntx > 1 {
- ntx = ntx.div_ceil(2);
- height += 1;
- }
-
- // Check with random subsets with inclusion chances 1, 1/2, 1/4, ..., 1/128
- for att in 1..15 {
- let mut matches = vec![false; tx_count];
- let mut match_txid1 = vec![];
- for j in 0..tx_count {
- // Generate `att / 2` random bits
- let rand_bits = match att / 2 {
- 0 => 0,
- bits => rng.next_usize().rotate_right(64 - bits),
- };
- let include = rand_bits == 0;
- matches[j] = include;
-
- if include {
- match_txid1.push(tx_ids[j]);
- };
- }
-
- // Build the partial Merkle tree
- let pmt1 = PartialMerkleTree::from_txids(&tx_ids, &matches);
- let serialized = encode::serialize(&pmt1);
-
- // Verify PartialMerkleTree's size guarantees
- let n = cmp::min(tx_count, 1 + match_txid1.len() * height);
- assert!(serialized.len() <= 10 + (258 * n).div_ceil(8));
-
- // Deserialize into a tester copy
- let pmt2: PartialMerkleTree =
- encode::deserialize(&serialized).expect("could not deserialize own data");
-
- // Extract Merkle root and matched txids from copy
- let mut match_txid2: Vec<Txid> = vec![];
- let mut indexes = vec![];
- let merkle_root_2 = pmt2
- .extract_matches(&mut match_txid2, &mut indexes)
- .expect("could not extract matches");
-
- // Check that it has the same Merkle root as the original, and a valid one
- assert_eq!(merkle_root_1, merkle_root_2);
- assert_ne!(merkle_root_2, TxMerkleNode::from_byte_array([0; 32]));
-
- // check that it contains the matched transactions (in the same order!)
- assert_eq!(match_txid1, match_txid2);
-
- // check that random bit flips break the authentication
- for _ in 0..4 {
- let mut pmt3: PartialMerkleTree = encode::deserialize(&serialized).unwrap();
- pmt3.damage(&mut rng);
- let mut match_txid3 = vec![];
- let merkle_root_3 = pmt3.extract_matches(&mut match_txid3, &mut indexes).unwrap();
- assert_ne!(merkle_root_3, merkle_root_1);
- }
- }
- }
-
- #[test]
- fn pmt_malleability() {
- // Create some fake tx ids with the last 2 hashes repeating
- let txids: Vec<Txid> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 10]
- .iter()
- .map(|i| format!("{:064x}", i).parse::<Txid>().unwrap())
- .collect();
-
- let matches =
- vec![false, false, false, false, false, false, false, false, false, true, true, false];
-
- let tree = PartialMerkleTree::from_txids(&txids, &matches);
- // Should fail due to duplicate txs found
- let result = tree.extract_matches(&mut vec![], &mut vec![]);
- assert!(result.is_err());
- }
-
- #[test]
- fn merkleblock_serialization() {
- // Got it by running the rpc call
- // `gettxoutproof '["220ebc64e21abece964927322cba69180ed853bb187fbc6923bac7d010b9d87a"]'`
- let mb_hex = include_str!("../../tests/data/merkle_block.hex");
-
- let bytes = Vec::from_hex(mb_hex).unwrap();
- let mb: MerkleBlock = encode::deserialize(&bytes).unwrap();
- assert_eq!(get_block_13b8a().block_hash(), mb.header.block_hash());
- assert_eq!(
- mb.header.merkle_root,
- mb.txn.extract_matches(&mut vec![], &mut vec![]).unwrap()
- );
- // Serialize again and check that it matches the original bytes
- assert_eq!(mb_hex, encode::serialize(&mb).to_lower_hex_string().as_str());
- }
-
- /// Constructs a new MerkleBlock using a list of txids which will be found in the
- /// given block.
- #[test]
- fn merkleblock_construct_from_txids_found() {
- let block = get_block_13b8a();
-
- let txids: Vec<Txid> = [
- "74d681e0e03bafa802c8aa084379aa98d9fcd632ddc2ed9782b586ec87451f20",
- "f9fc751cb7dc372406a9f8d738d5e6f8f63bab71986a39cf36ee70ee17036d07",
- ]
- .iter()
- .map(|hex| hex.parse::<Txid>().unwrap())
- .collect();
-
- let txid1 = txids[0];
- let txid2 = txids[1];
- let txids = [txid1, txid2];
-
- let merkle_block = MerkleBlock::from_block_with_predicate(&block, |t| txids.contains(t));
-
- assert_eq!(merkle_block.header.block_hash(), block.block_hash());
-
- let mut matches: Vec<Txid> = vec![];
- let mut index: Vec<u32> = vec![];
-
- assert_eq!(
- merkle_block.txn.extract_matches(&mut matches, &mut index).unwrap(),
- block.header().merkle_root
- );
- assert_eq!(matches.len(), 2);
-
- // Ordered by occurrence in depth-first tree traversal.
- assert_eq!(matches[0], txid2);
- assert_eq!(index[0], 1);
-
- assert_eq!(matches[1], txid1);
- assert_eq!(index[1], 8);
- }
-
- /// Constructs a new MerkleBlock using a list of txids which will not be found in the given block
- #[test]
- fn merkleblock_construct_from_txids_not_found() {
- let block = get_block_13b8a();
- let txids: Vec<Txid> = ["c0ffee00003bafa802c8aa084379aa98d9fcd632ddc2ed9782b586ec87451f20"]
- .iter()
- .map(|hex| hex.parse::<Txid>().unwrap())
- .collect();
-
- let merkle_block = MerkleBlock::from_block_with_predicate(&block, |t| txids.contains(t));
-
- assert_eq!(merkle_block.header.block_hash(), block.block_hash());
-
- let mut matches: Vec<Txid> = vec![];
- let mut index: Vec<u32> = vec![];
-
- assert_eq!(
- merkle_block.txn.extract_matches(&mut matches, &mut index).unwrap(),
- block.header().merkle_root
- );
- assert_eq!(matches.len(), 0);
- assert_eq!(index.len(), 0);
- }
-
- impl PartialMerkleTree {
- /// Flip one bit in one of the hashes - this should break the authentication
- fn damage(&mut self, rng: &mut LcgPrng) {
- let n = rng.next_in_range(self.hashes.len());
- let bit = rng.next_u8();
- let hashes = &mut self.hashes;
- let mut hash = hashes[n].to_byte_array();
- hash[(bit >> 3) as usize] ^= 1 << (bit & 7);
- hashes[n] = TxMerkleNode::from_byte_array(hash);
- }
- }
-
- /// Returns a real block (0000000000013b8ab2cd513b0261a14096412195a72a0c4827d229dcc7e0f7af)
- /// with 9 txs.
- fn get_block_13b8a() -> Block<Checked> {
- let block_hex = include_str!("../../tests/data/block_13b8a.hex");
- let block: Block<Unchecked> =
- encode::deserialize(&Vec::from_hex(block_hex).unwrap()).unwrap();
- block.validate().expect("block should be valid")
- }
-
- macro_rules! check_calc_tree_width {
- ($($test_name:ident, $num_transactions:literal, $height:literal, $expected_width:literal);* $(;)?) => {
- $(
- #[test]
- fn $test_name() {
- let pmt = PartialMerkleTree {
- num_transactions: $num_transactions,
- bits: vec![],
- hashes: vec![],
- };
- let got = pmt.calc_tree_width($height);
- assert_eq!(got, $expected_width)
- }
- )*
- }
- }
-
- // tree_width_<id> <num txs> <height> <expected_width>
- //
- // height 0 is the bottom of the tree, where the leaves are.
- check_calc_tree_width! {
- tree_width_01, 1, 0, 1;
- //
- tree_width_02, 2, 0, 2;
- tree_width_03, 2, 1, 1;
- //
- tree_width_04, 3, 0, 3;
- tree_width_05, 3, 1, 2;
- tree_width_06, 3, 2, 1;
- //
- tree_width_07, 4, 0, 4;
- tree_width_08, 4, 1, 2;
- tree_width_09, 4, 2, 1;
- //
- tree_width_10, 5, 0, 5;
- tree_width_11, 5, 1, 3;
- tree_width_12, 5, 2, 2;
- tree_width_13, 5, 3, 1;
- //
- tree_width_14, 6, 0, 6;
- tree_width_15, 6, 1, 3;
- tree_width_16, 6, 2, 2;
- tree_width_17, 6, 3, 1;
- //
- tree_width_18, 7, 0, 7;
- tree_width_19, 7, 1, 4;
- tree_width_20, 7, 2, 2;
- tree_width_21, 7, 3, 1;
- }
-
- #[test]
- fn regression_2606() {
- // Attempt to deserialize a partial Merkle tree with a number of hashes that would
- // overflow the maximum allowed size.
- let bytes = hex!(
- "000006000000000000000004ee00000004c7f1ccb1000000ffff000000010000\
- 0000ffffffffff1f000000000400000000000002000000000500000000000000\
- 000000000300000000000003000000000200000000ff00000000c7f1ccb10407\
- 00000000000000ccb100c76538b100000004bfa9c251681b1b00040000000025\
- 00000004bfaac251681b1b25\
- "
- );
- let deser = encode::deserialize::<MerkleBlock>(&bytes);
-
- // The attempt to deserialize should result in an error.
- assert!(deser.is_err());
- }
-
- #[test]
- fn extract_matches_from_merkleblock() {
- // Get the proof from a bitcoind by running in the terminal:
- // $ TXID="5a4ebf66822b0b2d56bd9dc64ece0bc38ee7844a23ff1d7320a88c5fdb2ad3e2"
- // $ bitcoin-cli gettxoutproof [\"$TXID\"]
- let mb_bytes = Vec::from_hex("01000000ba8b9cda965dd8e536670f9ddec10e53aab14b20bacad27b913719\
- 0000000000190760b278fe7b8565fda3b968b918d5fd997f993b23674c0af3b6fde300b38f33a5914ce6ed5b\
- 1b01e32f570200000002252bf9d75c4f481ebb6278d708257d1f12beb6dd30301d26c623f789b2ba6fc0e2d3\
- 2adb5f8ca820731dff234a84e78ec30bce4ec69dbd562d0b2b8266bf4e5a0105").unwrap();
- let mb: MerkleBlock = encode::deserialize(&mb_bytes).unwrap();
-
- // Authenticate and extract matched transaction ids
- let mut matches: Vec<Txid> = vec![];
- let mut index: Vec<u32> = vec![];
- assert!(mb.extract_matches(&mut matches, &mut index).is_ok());
-
- // The matches and index vectors are coupled, should be the same length.
- assert_eq!(matches.len(), index.len());
-
- // There should only be one match.
- assert_eq!(matches.len(), 1);
-
- // The match should come from index 1.
- assert_eq!(index[0], 1);
-
- // And we know the txid we want.
- let want = "5a4ebf66822b0b2d56bd9dc64ece0bc38ee7844a23ff1d7320a88c5fdb2ad3e2"
- .parse::<Txid>()
- .expect("failed to parse txid");
- assert_eq!(matches[0], want);
- }
-}
diff --git a/bitcoin/src/merkle_tree/mod.rs b/bitcoin/src/merkle_tree/mod.rs
index 81995949..16fad6cf 100644
--- a/bitcoin/src/merkle_tree/mod.rs
+++ b/bitcoin/src/merkle_tree/mod.rs
@@ -14,13 +14,10 @@
//! assert!(root.is_some());
//! ```
-mod block;
-
use io::{BufRead, Write};
#[rustfmt::skip]
#[doc(inline)]
-pub use self::block::{MerkleBlock, MerkleBlockError, PartialMerkleTree};
pub use primitives::{TxMerkleNode, WitnessMerkleNode};
use crate::consensus::{encode, Decodable, Encodable};
diff --git a/bitcoin/tests/data/block_13b8a.hex b/bitcoin/tests/data/block_13b8a.hex
deleted file mode 100644
index 6e83915b..00000000
--- a/bitcoin/tests/data/block_13b8a.hex
+++ /dev/null
@@ -1 +0,0 @@
-0100000090f0a9f110702f808219ebea1173056042a714bad51b916cb6800000000000005275289558f51c9966699404ae2294730c3c9f9bda53523ce50e9b95e558da2fdb261b4d4c86041b1ab1bf930901000000010000000000000000000000000000000000000000000000000000000000000000ffffffff07044c86041b0146ffffffff0100f2052a01000000434104e18f7afbe4721580e81e8414fc8c24d7cfacf254bb5c7b949450c3e997c2dc1242487a8169507b631eb3771f2b425483fb13102c4eb5d858eef260fe70fbfae0ac00000000010000000196608ccbafa16abada902780da4dc35dafd7af05fa0da08cf833575f8cf9e836000000004a493046022100dab24889213caf43ae6adc41cf1c9396c08240c199f5225acf45416330fd7dbd022100fe37900e0644bf574493a07fc5edba06dbc07c311b947520c2d514bc5725dcb401ffffffff0100f2052a010000001976a914f15d1921f52e4007b146dfa60f369ed2fc393ce288ac000000000100000001fb766c1288458c2bafcfec81e48b24d98ec706de6b8af7c4e3c29419bfacb56d000000008c493046022100f268ba165ce0ad2e6d93f089cfcd3785de5c963bb5ea6b8c1b23f1ce3e517b9f022100da7c0f21adc6c401887f2bfd1922f11d76159cbc597fbd756a23dcbb00f4d7290141042b4e8625a96127826915a5b109852636ad0da753c9e1d5606a50480cd0c40f1f8b8d898235e571fe9357d9ec842bc4bba1827daaf4de06d71844d0057707966affffffff0280969800000000001976a9146963907531db72d0ed1a0cfb471ccb63923446f388ac80d6e34c000000001976a914f0688ba1c0d1ce182c7af6741e02658c7d4dfcd388ac000000000100000002c40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff010000008b483045022100f7edfd4b0aac404e5bab4fd3889e0c6c41aa8d0e6fa122316f68eddd0a65013902205b09cc8b2d56e1cd1f7f2fafd60a129ed94504c4ac7bdc67b56fe67512658b3e014104732012cb962afa90d31b25d8fb0e32c94e513ab7a17805c14ca4c3423e18b4fb5d0e676841733cb83abaf975845c9f6f2a8097b7d04f4908b18368d6fc2d68ecffffffffca5065ff9617cbcba45eb23726df6498a9b9cafed4f54cbab9d227b0035ddefb000000008a473044022068010362a13c7f9919fa832b2dee4e788f61f6f5d344a7c2a0da6ae740605658022006d1af525b9a14a35c003b78b72bd59738cd676f845d1ff3fc25049e01003614014104732012cb962afa90d31b25d8fb0e32c94e513ab7a17805c14ca4c3423e18b4fb5d0e676841733cb83abaf975845c9f6f2a8097b7d04f4908b18368d6fc2d68ecffffffff01001ec4110200000043410469ab4181eceb28985b9b4e895c13fa5e68d85761b7eee311db5addef76fa8621865134a221bd01f28ec9999ee3e021e60766e9d1f3458c115fb28650605f11c9ac000000000100000001cdaf2f758e91c514655e2dc50633d1e4c84989f8aa90a0dbc883f0d23ed5c2fa010000008b48304502207ab51be6f12a1962ba0aaaf24a20e0b69b27a94fac5adf45aa7d2d18ffd9236102210086ae728b370e5329eead9accd880d0cb070aea0c96255fae6c4f1ddcce1fd56e014104462e76fd4067b3a0aa42070082dcb0bf2f388b6495cf33d789904f07d0f55c40fbd4b82963c69b3dc31895d0c772c812b1d5fbcade15312ef1c0e8ebbb12dcd4ffffffff02404b4c00000000001976a9142b6ba7c9d796b75eef7942fc9288edd37c32f5c388ac002d3101000000001976a9141befba0cdc1ad56529371864d9f6cb042faa06b588ac000000000100000001b4a47603e71b61bc3326efd90111bf02d2f549b067f4c4a8fa183b57a0f800cb010000008a4730440220177c37f9a505c3f1a1f0ce2da777c339bd8339ffa02c7cb41f0a5804f473c9230220585b25a2ee80eb59292e52b987dad92acb0c64eced92ed9ee105ad153cdb12d001410443bd44f683467e549dae7d20d1d79cbdb6df985c6e9c029c8d0c6cb46cc1a4d3cf7923c5021b27f7a0b562ada113bc85d5fda5a1b41e87fe6e8802817cf69996ffffffff0280651406000000001976a9145505614859643ab7b547cd7f1f5e7e2a12322d3788ac00aa0271000000001976a914ea4720a7a52fc166c55ff2298e07baf70ae67e1b88ac00000000010000000586c62cd602d219bb60edb14a3e204de0705176f9022fe49a538054fb14abb49e010000008c493046022100f2bc2aba2534becbdf062eb993853a42bbbc282083d0daf9b4b585bd401aa8c9022100b1d7fd7ee0b95600db8535bbf331b19eed8d961f7a8e54159c53675d5f69df8c014104462e76fd4067b3a0aa42070082dcb0bf2f388b6495cf33d789904f07d0f55c40fbd4b82963c69b3dc31895d0c772c812b1d5fbcade15312ef1c0e8ebbb12dcd4ffffffff03ad0e58ccdac3df9dc28a218bcf6f1997b0a93306faaa4b3a28ae83447b2179010000008b483045022100be12b2937179da88599e27bb31c3525097a07cdb52422d165b3ca2f2020ffcf702200971b51f853a53d644ebae9ec8f3512e442b1bcb6c315a5b491d119d10624c83014104462e76fd4067b3a0aa42070082dcb0bf2f388b6495cf33d789904f07d0f55c40fbd4b82963c69b3dc31895d0c772c812b1d5fbcade15312ef1c0e8ebbb12dcd4ffffffff2acfcab629bbc8685792603762c921580030ba144af553d271716a95089e107b010000008b483045022100fa579a840ac258871365dd48cd7552f96c8eea69bd00d84f05b283a0dab311e102207e3c0ee9234814cfbb1b659b83671618f45abc1326b9edcc77d552a4f2a805c0014104462e76fd4067b3a0aa42070082dcb0bf2f388b6495cf33d789904f07d0f55c40fbd4b82963c69b3dc31895d0c772c812b1d5fbcade15312ef1c0e8ebbb12dcd4ffffffffdcdc6023bbc9944a658ddc588e61eacb737ddf0a3cd24f113b5a8634c517fcd2000000008b4830450221008d6df731df5d32267954bd7d2dda2302b74c6c2a6aa5c0ca64ecbabc1af03c75022010e55c571d65da7701ae2da1956c442df81bbf076cdbac25133f99d98a9ed34c014104462e76fd4067b3a0aa42070082dcb0bf2f388b6495cf33d789904f07d0f55c40fbd4b82963c69b3dc31895d0c772c812b1d5fbcade15312ef1c0e8ebbb12dcd4ffffffffe15557cd5ce258f479dfd6dc6514edf6d7ed5b21fcfa4a038fd69f06b83ac76e010000008b483045022023b3e0ab071eb11de2eb1cc3a67261b866f86bf6867d4558165f7c8c8aca2d86022100dc6e1f53a91de3efe8f63512850811f26284b62f850c70ca73ed5de8771fb451014104462e76fd4067b3a0aa42070082dcb0bf2f388b6495cf33d789904f07d0f55c40fbd4b82963c69b3dc31895d0c772c812b1d5fbcade15312ef1c0e8ebbb12dcd4ffffffff01404b4c00000000001976a9142b6ba7c9d796b75eef7942fc9288edd37c32f5c388ac00000000010000000166d7577163c932b4f9690ca6a80b6e4eb001f0a2fa9023df5595602aae96ed8d000000008a4730440220262b42546302dfb654a229cefc86432b89628ff259dc87edd1154535b16a67e102207b4634c020a97c3e7bbd0d4d19da6aa2269ad9dded4026e896b213d73ca4b63f014104979b82d02226b3a4597523845754d44f13639e3bf2df5e82c6aab2bdc79687368b01b1ab8b19875ae3c90d661a3d0a33161dab29934edeb36aa01976be3baf8affffffff02404b4c00000000001976a9144854e695a02af0aeacb823ccbc272134561e0a1688ac40420f00000000001976a914abee93376d6b37b5c2940655a6fcaf1c8e74237988ac0000000001000000014e3f8ef2e91349a9059cb4f01e54ab2597c1387161d3da89919f7ea6acdbb371010000008c49304602210081f3183471a5ca22307c0800226f3ef9c353069e0773ac76bb580654d56aa523022100d4c56465bdc069060846f4fbf2f6b20520b2a80b08b168b31e66ddb9c694e240014104976c79848e18251612f8940875b2b08d06e6dc73b9840e8860c066b7e87432c477e9a59a453e71e6d76d5fe34058b800a098fc1740ce3012e8fc8a00c96af966ffffffff02c0e1e400000000001976a9144134e75a6fcb6042034aab5e18570cf1f844f54788ac404b4c00000000001976a9142b6ba7c9d796b75eef7942fc9288edd37c32f5c388ac00000000
\ No newline at end of file
diff --git a/bitcoin/tests/data/merkle_block.hex b/bitcoin/tests/data/merkle_block.hex
deleted file mode 100644
index c9a32c9a..00000000
--- a/bitcoin/tests/data/merkle_block.hex
+++ /dev/null
@@ -1 +0,0 @@
-0100000090f0a9f110702f808219ebea1173056042a714bad51b916cb6800000000000005275289558f51c9966699404ae2294730c3c9f9bda53523ce50e9b95e558da2fdb261b4d4c86041b1ab1bf930900000005fac7708a6e81b2a986dea60db2663840ed141130848162eb1bd1dee54f309a1b2ee1e12587e497ada70d9bd10d31e83f0a924825b96cb8d04e8936d793fb60db7ad8b910d0c7ba2369bc7f18bb53d80e1869ba2c32274996cebe1ae264bc0e2289189ff0316cdc10511da71da757e553cada9f3b5b1434f3923673adb57d83caac392c38af156d6fc30b55fad4112df2b95531e68114e9ad10011e72f7b7cfdb025700
\ No newline at end of file
diff --git a/p2p/src/lib.rs b/p2p/src/lib.rs
index 9ee838d2..e7127398 100644
--- a/p2p/src/lib.rs
+++ b/p2p/src/lib.rs
@@ -14,6 +14,7 @@ mod network_ext;
#[cfg(feature = "std")]
pub mod address;
pub mod bip152;
+pub mod merkle_tree;
#[cfg(feature = "std")]
pub mod message;
pub mod message_blockdata;
diff --git a/p2p/src/merkle_tree.rs b/p2p/src/merkle_tree.rs
new file mode 100644
index 00000000..597999ff
--- /dev/null
+++ b/p2p/src/merkle_tree.rs
@@ -0,0 +1,896 @@
+// SPDX-License-Identifier: CC0-1.0
+//
+// This code was translated from merkleblock.h, merkleblock.cpp and pmt_tests.cpp
+// Copyright (c) 2009-2010 Satoshi Nakamoto
+// Copyright (c) 2009-2018 The Bitcoin Core developers
+// SPDX-License-Identifier: MIT
+
+//! Merkle Block and Partial Merkle Tree.
+//!
+//! Support proofs that transaction(s) belong to a block.
+
+use alloc::vec;
+use alloc::vec::Vec;
+use core::convert::Infallible;
+use core::fmt;
+
+#[cfg(feature = "arbitrary")]
+use arbitrary::{Arbitrary, Unstructured};
+use bitcoin::consensus::encode::{self, Decodable, Encodable, ReadExt, WriteExt, MAX_VEC_SIZE};
+use internals::ToU64 as _;
+use io::{BufRead, Write};
+use primitives::block::{self, Block, Checked};
+use primitives::merkle_tree::TxMerkleNode;
+use primitives::transaction::{Transaction, Txid};
+use primitives::Weight;
+
+/// Data structure that represents a block header paired to a partial Merkle tree.
+///
+/// NOTE: This assumes that the given Block has *at least* 1 transaction. If the Block has 0 txs,
+/// it will hit an assertion.
+#[derive(PartialEq, Eq, Clone, Debug)]
+pub struct MerkleBlock {
+ /// The block header
+ pub header: block::Header,
+ /// Transactions making up a partial Merkle tree
+ pub txn: PartialMerkleTree,
+}
+
+impl MerkleBlock {
+ /// Constructs a new [`MerkleBlock`] from a block, that contains proofs for specific txids.
+ ///
+ /// The `block` is a full block containing the header and transactions and `match_txids` is a
+ /// function that returns true for the ids that should be included in the partial Merkle tree.
+ ///
+ /// # Examples
+ ///
+ /// ```rust
+ /// use bitcoin::hex::FromHex;
+ /// use bitcoin_p2p_messages::merkle_tree::MerkleBlock;
+ /// use primitives::{Block, Txid};
+ ///
+ /// // Block 80000
+ /// let block_bytes = Vec::from_hex("01000000ba8b9cda965dd8e536670f9ddec10e53aab14b20bacad2\
+ /// 7b9137190000000000190760b278fe7b8565fda3b968b918d5fd997f993b23674c0af3b6fde300b38f33\
+ /// a5914ce6ed5b1b01e32f5702010000000100000000000000000000000000000000000000000000000000\
+ /// 00000000000000ffffffff0704e6ed5b1b014effffffff0100f2052a01000000434104b68a50eaa0287e\
+ /// ff855189f949c1c6e5f58b37c88231373d8a59809cbae83059cc6469d65c665ccfd1cfeb75c6e8e19413\
+ /// bba7fbff9bc762419a76d87b16086eac000000000100000001a6b97044d03da79c005b20ea9c0e1a6d9d\
+ /// c12d9f7b91a5911c9030a439eed8f5000000004948304502206e21798a42fae0e854281abd38bacd1aee\
+ /// d3ee3738d9e1446618c4571d1090db022100e2ac980643b0b82c0e88ffdfec6b64e3e6ba35e7ba5fdd7d\
+ /// 5d6cc8d25c6b241501ffffffff0100f2052a010000001976a914404371705fa9bd789a2fcd52d2c580b6\
+ /// 5d35549d88ac00000000").unwrap();
+ /// let block: Block = bitcoin::consensus::deserialize(&block_bytes).unwrap();
+ /// let block = block.validate().expect("valid block");
+ ///
+ /// // Constructs a new Merkle block containing a single transaction
+ /// let txid = "5a4ebf66822b0b2d56bd9dc64ece0bc38ee7844a23ff1d7320a88c5fdb2ad3e2".parse::<Txid>().unwrap();
+ /// let match_txids: Vec<Txid> = vec![txid].into_iter().collect();
+ /// let mb = MerkleBlock::from_block_with_predicate(&block, |t| match_txids.contains(t));
+ ///
+ /// // Authenticate and extract matched transaction ids
+ /// let mut matches: Vec<Txid> = vec![];
+ /// let mut index: Vec<u32> = vec![];
+ /// assert!(mb.extract_matches(&mut matches, &mut index).is_ok());
+ /// assert_eq!(txid, matches[0]);
+ /// ```
+ pub fn from_block_with_predicate<F>(block: &Block<Checked>, match_txids: F) -> Self
+ where
+ F: Fn(&Txid) -> bool,
+ {
+ let block_txids: Vec<_> =
+ block.transactions().iter().map(Transaction::compute_txid).collect();
+ Self::from_header_txids_with_predicate(block.header(), &block_txids, match_txids)
+ }
+
+ /// Constructs a new [`MerkleBlock`] from the block's header and txids, that contain proofs for specific txids.
+ ///
+ /// The `header` is the block header, `block_txids` is the full list of txids included in the block and
+ /// `match_txids` is a function that returns true for the ids that should be included in the partial Merkle tree.
+ pub fn from_header_txids_with_predicate<F>(
+ header: &block::Header,
+ block_txids: &[Txid],
+ match_txids: F,
+ ) -> Self
+ where
+ F: Fn(&Txid) -> bool,
+ {
+ let matches: Vec<bool> = block_txids.iter().map(match_txids).collect();
+
+ let pmt = PartialMerkleTree::from_txids(block_txids, &matches);
+ Self { header: *header, txn: pmt }
+ }
+
+ /// Extracts the matching txid's represented by this partial Merkle tree
+ /// and their respective indices within the partial tree.
+ /// returns Ok(()) on success, or error in case of failure
+ ///
+ /// # Errors
+ ///
+ /// See [`MerkleBlockError`] for cases.
+ pub fn extract_matches(
+ &self,
+ matches: &mut Vec<Txid>,
+ indexes: &mut Vec<u32>,
+ ) -> Result<(), MerkleBlockError> {
+ let merkle_root = self.txn.extract_matches(matches, indexes)?;
+
+ if merkle_root.eq(&self.header.merkle_root) {
+ Ok(())
+ } else {
+ Err(MerkleBlockError::MerkleRootMismatch)
+ }
+ }
+}
+
+impl Encodable for MerkleBlock {
+ fn consensus_encode<W: Write + ?Sized>(&self, w: &mut W) -> Result<usize, io::Error> {
+ let len = self.header.consensus_encode(w)? + self.txn.consensus_encode(w)?;
+ Ok(len)
+ }
+}
+
+impl Decodable for MerkleBlock {
+ fn consensus_decode<R: BufRead + ?Sized>(r: &mut R) -> Result<Self, encode::Error> {
+ Ok(Self { header: Decodable::consensus_decode(r)?, txn: Decodable::consensus_decode(r)? })
+ }
+}
+
+/// 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 are 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)
+/// - `CompactSize` number of hashes (1-3 bytes)
+/// - uint256[] hashes in depth-first order (<= 32*N bytes)
+/// - `CompactSize` 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.
+#[derive(PartialEq, Eq, Clone, Debug)]
+pub struct PartialMerkleTree {
+ /// The total number of transactions in the block
+ num_transactions: u32,
+ /// node-is-parent-of-matched-txid bits
+ bits: Vec<bool>,
+ /// Transaction ids and internal hashes
+ hashes: Vec<TxMerkleNode>,
+}
+
+impl PartialMerkleTree {
+ /// Returns the total number of transactions in the block.
+ pub fn num_transactions(&self) -> u32 { self.num_transactions }
+
+ /// Returns the node-is-parent-of-matched-txid bits of the partial Merkle tree.
+ pub fn bits(&self) -> &Vec<bool> { &self.bits }
+
+ /// Returns the transaction ids and internal hashes of the partial Merkle tree.
+ pub fn hashes(&self) -> &Vec<TxMerkleNode> { &self.hashes }
+
+ /// Constructs a new partial Merkle tree.
+ ///
+ /// The `txids` are the transaction hashes of the block and `matches` contains flags indicating
+ /// whether each txid should be included in the proof.
+ ///
+ /// # Panics
+ ///
+ /// Panics when `txids` is empty or when `matches` has a different length.
+ ///
+ /// # Examples
+ ///
+ /// ```rust
+ /// use bitcoin_p2p_messages::merkle_tree::PartialMerkleTree;
+ /// use primitives::Txid;
+ ///
+ /// // 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 from_txids(txids: &[Txid], matches: &[bool]) -> Self {
+ // We can never have zero txs in a Merkle block, we always need the coinbase tx
+ assert_ne!(txids.len(), 0);
+ assert_eq!(txids.len(), matches.len());
+
+ let mut pmt = Self {
+ num_transactions: txids.len() as u32,
+ bits: Vec::with_capacity(txids.len()),
+ hashes: vec![],
+ };
+ let height = pmt.calc_tree_height();
+
+ // traverse the partial tree
+ pmt.traverse_and_build(height, 0, txids, matches);
+ pmt
+ }
+
+ /// Extracts the matching txid's represented by this partial Merkle tree
+ /// and their respective indices within the partial tree.
+ /// returns the Merkle root
+ ///
+ /// # Errors
+ ///
+ /// See [`MerkleBlockError`] for cases.
+ pub fn extract_matches(
+ &self,
+ matches: &mut Vec<Txid>,
+ indexes: &mut Vec<u32>,
+ ) -> Result<TxMerkleNode, MerkleBlockError> {
+ matches.clear();
+ indexes.clear();
+ // An empty set will not work
+ if self.num_transactions == 0 {
+ return Err(MerkleBlockError::NoTransactions);
+ };
+ // check for excessively high numbers of transactions
+ if self.num_transactions.to_u64() > Weight::MAX_BLOCK / Weight::MIN_TRANSACTION {
+ return Err(MerkleBlockError::TooManyTransactions);
+ }
+ // there can never be more hashes provided than one for every txid
+ if self.hashes.len() as u32 > self.num_transactions {
+ return Err(MerkleBlockError::TooManyHashes);
+ };
+ // there must be at least one bit per node in the partial tree, and at least one node per hash
+ if self.bits.len() < self.hashes.len() {
+ return Err(MerkleBlockError::NotEnoughBits);
+ };
+
+ let height = self.calc_tree_height();
+
+ // traverse the partial tree
+ let mut bits_used = 0u32;
+ let mut hash_used = 0u32;
+ let hash_merkle_root =
+ self.traverse_and_extract(height, 0, &mut bits_used, &mut hash_used, matches, indexes)?;
+ // Verify that all bits were consumed (except for the padding caused by
+ // serializing it as a byte sequence)
+ if bits_used.div_ceil(8) != self.bits.len().div_ceil(8) as u32 {
+ return Err(MerkleBlockError::NotAllBitsConsumed);
+ }
+ // Verify that all hashes were consumed
+ if hash_used != self.hashes.len() as u32 {
+ return Err(MerkleBlockError::NotAllHashesConsumed);
+ }
+ Ok(hash_merkle_root)
+ }
+
+ /// Calculates the height of the tree.
+ fn calc_tree_height(&self) -> u32 {
+ let mut height = 0;
+ while self.calc_tree_width(height) > 1 {
+ height += 1;
+ }
+ height
+ }
+
+ /// Helper function to efficiently calculate the number of nodes at given height
+ /// in the Merkle tree
+ #[inline]
+ fn calc_tree_width(&self, height: u32) -> u32 {
+ (self.num_transactions + (1 << height) - 1) >> height
+ }
+
+ /// Calculates the hash of a node in the Merkle tree (at leaf level: the txid's themselves)
+ fn calc_hash(&self, height: u32, pos: u32, txids: &[Txid]) -> TxMerkleNode {
+ if height == 0 {
+ // Hash at height 0 is the txid itself
+ TxMerkleNode::from_byte_array(txids[pos as usize].to_byte_array())
+ } else {
+ // Calculate left hash
+ let left = self.calc_hash(height - 1, pos * 2, txids);
+ // Calculate right hash if not beyond the end of the array - copy left hash otherwise
+ let right = if pos * 2 + 1 < self.calc_tree_width(height - 1) {
+ self.calc_hash(height - 1, pos * 2 + 1, txids)
+ } else {
+ left
+ };
+ // Combine subhashes
+ left.combine(&right)
+ }
+ }
+
+ /// Recursive function that traverses tree nodes, storing the data as bits and hashes
+ fn traverse_and_build(&mut self, height: u32, pos: u32, txids: &[Txid], matches: &[bool]) {
+ // Determine whether this node is the parent of at least one matched txid
+ let mut parent_of_match = false;
+ let mut p = pos << height;
+ while p < (pos + 1) << height && p < self.num_transactions {
+ parent_of_match |= matches[p as usize];
+ p += 1;
+ }
+ // Store as flag bit
+ self.bits.push(parent_of_match);
+
+ if height == 0 || !parent_of_match {
+ // If at height 0, or nothing interesting below, store hash and stop
+ let hash = self.calc_hash(height, pos, txids);
+ self.hashes.push(hash);
+ } else {
+ // Otherwise, don't store any hash, but descend into the subtrees
+ self.traverse_and_build(height - 1, pos * 2, txids, matches);
+ if pos * 2 + 1 < self.calc_tree_width(height - 1) {
+ self.traverse_and_build(height - 1, pos * 2 + 1, txids, matches);
+ }
+ }
+ }
+
+ /// 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.
+ fn traverse_and_extract(
+ &self,
+ height: u32,
+ pos: u32,
+ bits_used: &mut u32,
+ hash_used: &mut u32,
+ matches: &mut Vec<Txid>,
+ indexes: &mut Vec<u32>,
+ ) -> Result<TxMerkleNode, MerkleBlockError> {
+ if *bits_used as usize >= self.bits.len() {
+ return Err(MerkleBlockError::BitsArrayOverflow);
+ }
+ let parent_of_match = self.bits[*bits_used as usize];
+ *bits_used += 1;
+ if height == 0 || !parent_of_match {
+ // If at height 0, or nothing interesting below, use stored hash and do not descend
+ if *hash_used as usize >= self.hashes.len() {
+ return Err(MerkleBlockError::HashesArrayOverflow);
+ }
+ let hash = self.hashes[*hash_used as usize];
+ *hash_used += 1;
+ if height == 0 && parent_of_match {
+ // in case of height 0, we have a matched txid
+ matches.push(Txid::from_byte_array(hash.to_byte_array()));
+ indexes.push(pos);
+ }
+ Ok(hash)
+ } else {
+ // otherwise, descend into the subtrees to extract matched txids and hashes
+ let left = self.traverse_and_extract(
+ height - 1,
+ pos * 2,
+ bits_used,
+ hash_used,
+ matches,
+ indexes,
+ )?;
+ let right;
+ if pos * 2 + 1 < self.calc_tree_width(height - 1) {
+ right = self.traverse_and_extract(
+ height - 1,
+ pos * 2 + 1,
+ bits_used,
+ hash_used,
+ matches,
+ indexes,
+ )?;
+ if right == left {
+ // The left and right branches should never be identical, as the transaction
+ // hashes covered by them must each be unique.
+ return Err(MerkleBlockError::IdenticalHashesFound);
+ }
+ } else {
+ right = left;
+ }
+ // and combine them before returning
+ Ok(left.combine(&right))
+ }
+ }
+}
+
+impl Encodable for PartialMerkleTree {
+ fn consensus_encode<W: Write + ?Sized>(&self, w: &mut W) -> Result<usize, io::Error> {
+ let mut ret = self.num_transactions.consensus_encode(w)?;
+ ret += self.hashes.consensus_encode(w)?;
+
+ let nb_bytes_for_bits = self.bits.len().div_ceil(8);
+ ret += w.emit_compact_size(nb_bytes_for_bits)?;
+ for chunk in self.bits.chunks(8) {
+ let mut byte = 0u8;
+ for (i, bit) in chunk.iter().enumerate() {
+ byte |= u8::from(*bit) << i;
+ }
+ ret += byte.consensus_encode(w)?;
+ }
+ Ok(ret)
+ }
+}
+
+impl Decodable for PartialMerkleTree {
+ fn consensus_decode_from_finite_reader<R: BufRead + ?Sized>(
+ r: &mut R,
+ ) -> Result<Self, encode::Error> {
+ let num_transactions: u32 = Decodable::consensus_decode(r)?;
+ let hashes: Vec<TxMerkleNode> = Decodable::consensus_decode(r)?;
+
+ let nb_bytes_for_bits = r.read_compact_size()? as usize;
+ if nb_bytes_for_bits > MAX_VEC_SIZE {
+ return Err(encode::ParseError::OversizedVectorAllocation {
+ requested: nb_bytes_for_bits,
+ max: MAX_VEC_SIZE,
+ }
+ .into());
+ }
+ let mut bits = vec![false; nb_bytes_for_bits * 8];
+ for chunk in bits.chunks_mut(8) {
+ let byte = u8::consensus_decode(r)?;
+ for (i, bit) in chunk.iter_mut().enumerate() {
+ *bit = (byte & (1 << i)) != 0;
+ }
+ }
+
+ Ok(Self { num_transactions, bits, hashes })
+ }
+}
+
+/// An error when verifying the Merkle block.
+#[derive(Debug, Clone, PartialEq, Eq)]
+#[non_exhaustive]
+pub enum MerkleBlockError {
+ /// Merkle root in the header doesn't match to the root calculated from partial Merkle tree.
+ MerkleRootMismatch,
+ /// Partial Merkle tree contains no transactions.
+ NoTransactions,
+ /// There are too many transactions.
+ TooManyTransactions,
+ /// There are too many hashes
+ TooManyHashes,
+ /// There must be at least one bit per node in the partial tree,
+ /// and at least one node per hash
+ NotEnoughBits,
+ /// Not all bits were consumed
+ NotAllBitsConsumed,
+ /// Not all hashes were consumed
+ NotAllHashesConsumed,
+ /// Overflowed the bits array
+ BitsArrayOverflow,
+ /// Overflowed the hashes array
+ HashesArrayOverflow,
+ /// The left and right branches should never be identical
+ IdenticalHashesFound,
+}
+
+impl From<Infallible> for MerkleBlockError {
+ fn from(never: Infallible) -> Self { match never {} }
+}
+
+impl fmt::Display for MerkleBlockError {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ match self {
+ Self::MerkleRootMismatch => write!(f, "Merkle header root doesn't match to the root calculated from the partial Merkle tree"),
+ Self::NoTransactions => write!(f, "partial Merkle tree contains no transactions"),
+ Self::TooManyTransactions => write!(f, "too many transactions"),
+ Self::TooManyHashes => write!(f, "proof contains more hashes than transactions"),
+ Self::NotEnoughBits => write!(f, "proof contains fewer bits than hashes"),
+ Self::NotAllBitsConsumed => write!(f, "not all bits were consumed"),
+ Self::NotAllHashesConsumed => write!(f, "not all hashes were consumed"),
+ Self::BitsArrayOverflow => write!(f, "overflowed the bits array"),
+ Self::HashesArrayOverflow => write!(f, "overflowed the hashes array"),
+ Self::IdenticalHashesFound => write!(f, "found identical transaction hashes"),
+ }
+ }
+}
+
+#[cfg(feature = "std")]
+impl std::error::Error for MerkleBlockError {
+ fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
+ match self {
+ Self::MerkleRootMismatch
+ | Self::NoTransactions
+ | Self::TooManyTransactions
+ | Self::TooManyHashes
+ | Self::NotEnoughBits
+ | Self::NotAllBitsConsumed
+ | Self::NotAllHashesConsumed
+ | Self::BitsArrayOverflow
+ | Self::HashesArrayOverflow
+ | Self::IdenticalHashesFound => None,
+ }
+ }
+}
+
+#[cfg(feature = "arbitrary")]
+impl<'a> Arbitrary<'a> for PartialMerkleTree {
+ fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
+ Ok(Self {
+ num_transactions: u.arbitrary()?,
+ bits: Vec::<bool>::arbitrary(u)?,
+ hashes: Vec::<TxMerkleNode>::arbitrary(u)?,
+ })
+ }
+}
+
+#[cfg(feature = "arbitrary")]
+impl<'a> Arbitrary<'a> for MerkleBlock {
+ fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
+ Ok(Self { header: u.arbitrary()?, txn: u.arbitrary()? })
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use core::cmp;
+
+ use hex::{DisplayHex, FromHex};
+ use hex_lit::hex;
+ use primitives::block::Unchecked;
+
+ use super::*;
+
+ // `bloc` in hex.
+ const PRNG_SEED: usize = 0x626C_6F63;
+
+ // Simple and deterministic PRNG, not suitable for cryptographic use cases.
+ struct LcgPrng {
+ state: usize,
+ }
+
+ impl LcgPrng {
+ const P: usize = 1039;
+ const Q: usize = 677;
+
+ const fn new(seed: usize) -> Self { Self { state: seed } }
+
+ #[inline]
+ fn next_usize(&mut self) -> usize {
+ self.state = self.state.wrapping_mul(Self::P).wrapping_add(Self::Q);
+ self.state
+ }
+
+ #[inline]
+ fn next_in_range(&mut self, max: usize) -> usize { self.next_usize() % max }
+
+ #[inline]
+ fn next_u8(&mut self) -> u8 { self.next_usize().to_le_bytes()[0] }
+ }
+
+ macro_rules! pmt_tests {
+ ($($name:ident),* $(,)?) => {
+ $(
+ #[test]
+ fn $name() {
+ pmt_test_from_name(stringify!($name));
+ }
+ )*
+ }
+ }
+
+ pmt_tests!(
+ pmt_test_1,
+ pmt_test_4,
+ pmt_test_7,
+ pmt_test_17,
+ pmt_test_56,
+ pmt_test_100,
+ pmt_test_127,
+ pmt_test_256,
+ pmt_test_312,
+ pmt_test_513,
+ pmt_test_1000,
+ pmt_test_4095
+ );
+
+ /// Parses the transaction count out of `name` with form: `pmt_test_$num`.
+ fn pmt_test_from_name(name: &str) { pmt_test(name[9..].parse().unwrap()) }
+
+ fn pmt_test(tx_count: usize) {
+ let mut rng = LcgPrng::new(PRNG_SEED ^ tx_count);
+ // Create some fake tx ids
+ let tx_ids = (1..=tx_count)
+ .map(|i| alloc::format!("{:064x}", i).parse::<Txid>().unwrap())
+ .collect::<Vec<_>>();
+
+ // Calculate the Merkle root and height
+ let hashes = tx_ids.iter().copied();
+ let merkle_root_1 = TxMerkleNode::calculate_root(hashes).expect("hashes is not empty");
+ let mut height = 1;
+ let mut ntx = tx_count;
+ while ntx > 1 {
+ ntx = ntx.div_ceil(2);
+ height += 1;
+ }
+
+ // Check with random subsets with inclusion chances 1, 1/2, 1/4, ..., 1/128
+ for att in 1..15 {
+ let mut matches = vec![false; tx_count];
+ let mut match_txid1 = vec![];
+ for j in 0..tx_count {
+ // Generate `att / 2` random bits
+ let rand_bits = match att / 2 {
+ 0 => 0,
+ bits => rng.next_usize().rotate_right(64 - bits),
+ };
+ let include = rand_bits == 0;
+ matches[j] = include;
+
+ if include {
+ match_txid1.push(tx_ids[j]);
+ };
+ }
+
+ // Build the partial Merkle tree
+ let pmt1 = PartialMerkleTree::from_txids(&tx_ids, &matches);
+ let serialized = encode::serialize(&pmt1);
+
+ // Verify PartialMerkleTree's size guarantees
+ let n = cmp::min(tx_count, 1 + match_txid1.len() * height);
+ assert!(serialized.len() <= 10 + (258 * n).div_ceil(8));
+
+ // Deserialize into a tester copy
+ let pmt2: PartialMerkleTree =
+ encode::deserialize(&serialized).expect("could not deserialize own data");
+
+ // Extract Merkle root and matched txids from copy
+ let mut match_txid2: Vec<Txid> = vec![];
+ let mut indexes = vec![];
+ let merkle_root_2 = pmt2
+ .extract_matches(&mut match_txid2, &mut indexes)
+ .expect("could not extract matches");
+
+ // Check that it has the same Merkle root as the original, and a valid one
+ assert_eq!(merkle_root_1, merkle_root_2);
+ assert_ne!(merkle_root_2, TxMerkleNode::from_byte_array([0; 32]));
+
+ // check that it contains the matched transactions (in the same order!)
+ assert_eq!(match_txid1, match_txid2);
+
+ // check that random bit flips break the authentication
+ for _ in 0..4 {
+ let mut pmt3: PartialMerkleTree = encode::deserialize(&serialized).unwrap();
+ pmt3.damage(&mut rng);
+ let mut match_txid3 = vec![];
+ let merkle_root_3 = pmt3.extract_matches(&mut match_txid3, &mut indexes).unwrap();
+ assert_ne!(merkle_root_3, merkle_root_1);
+ }
+ }
+ }
+
+ #[test]
+ fn pmt_malleability() {
+ // Create some fake tx ids with the last 2 hashes repeating
+ let txids: Vec<Txid> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 10]
+ .iter()
+ .map(|i| alloc::format!("{:064x}", i).parse::<Txid>().unwrap())
+ .collect();
+
+ let matches =
+ vec![false, false, false, false, false, false, false, false, false, true, true, false];
+
+ let tree = PartialMerkleTree::from_txids(&txids, &matches);
+ // Should fail due to duplicate txs found
+ let result = tree.extract_matches(&mut vec![], &mut vec![]);
+ assert!(result.is_err());
+ }
+
+ #[test]
+ fn merkleblock_serialization() {
+ // Got it by running the rpc call
+ // `gettxoutproof '["220ebc64e21abece964927322cba69180ed853bb187fbc6923bac7d010b9d87a"]'`
+ let mb_hex = include_str!("../tests/data/merkle_block.hex");
+
+ let bytes = Vec::from_hex(mb_hex).unwrap();
+ let mb: MerkleBlock = encode::deserialize(&bytes).unwrap();
+ assert_eq!(get_block_13b8a().block_hash(), mb.header.block_hash());
+ assert_eq!(
+ mb.header.merkle_root,
+ mb.txn.extract_matches(&mut vec![], &mut vec![]).unwrap()
+ );
+ // Serialize again and check that it matches the original bytes
+ assert_eq!(mb_hex, encode::serialize(&mb).to_lower_hex_string().as_str());
+ }
+
+ /// Constructs a new [`MerkleBlock`] using a list of txids which will be found in the
+ /// given block.
+ #[test]
+ fn merkleblock_construct_from_txids_found() {
+ let block = get_block_13b8a();
+
+ let txids: Vec<Txid> = [
+ "74d681e0e03bafa802c8aa084379aa98d9fcd632ddc2ed9782b586ec87451f20",
+ "f9fc751cb7dc372406a9f8d738d5e6f8f63bab71986a39cf36ee70ee17036d07",
+ ]
+ .iter()
+ .map(|hex| hex.parse::<Txid>().unwrap())
+ .collect();
+
+ let txid1 = txids[0];
+ let txid2 = txids[1];
+ let txids = [txid1, txid2];
+
+ let merkle_block = MerkleBlock::from_block_with_predicate(&block, |t| txids.contains(t));
+
+ assert_eq!(merkle_block.header.block_hash(), block.block_hash());
+
+ let mut matches: Vec<Txid> = vec![];
+ let mut index: Vec<u32> = vec![];
+
+ assert_eq!(
+ merkle_block.txn.extract_matches(&mut matches, &mut index).unwrap(),
+ block.header().merkle_root
+ );
+ assert_eq!(matches.len(), 2);
+
+ // Ordered by occurrence in depth-first tree traversal.
+ assert_eq!(matches[0], txid2);
+ assert_eq!(index[0], 1);
+
+ assert_eq!(matches[1], txid1);
+ assert_eq!(index[1], 8);
+ }
+
+ /// Constructs a new [`MerkleBlock`] using a list of txids which will not be found in the given block
+ #[test]
+ fn merkleblock_construct_from_txids_not_found() {
+ let block = get_block_13b8a();
+ let txids: Vec<Txid> = ["c0ffee00003bafa802c8aa084379aa98d9fcd632ddc2ed9782b586ec87451f20"]
+ .iter()
+ .map(|hex| hex.parse::<Txid>().unwrap())
+ .collect();
+
+ let merkle_block = MerkleBlock::from_block_with_predicate(&block, |t| txids.contains(t));
+
+ assert_eq!(merkle_block.header.block_hash(), block.block_hash());
+
+ let mut matches: Vec<Txid> = vec![];
+ let mut index: Vec<u32> = vec![];
+
+ assert_eq!(
+ merkle_block.txn.extract_matches(&mut matches, &mut index).unwrap(),
+ block.header().merkle_root
+ );
+ assert_eq!(matches.len(), 0);
+ assert_eq!(index.len(), 0);
+ }
+
+ impl PartialMerkleTree {
+ /// Flip one bit in one of the hashes - this should break the authentication
+ fn damage(&mut self, rng: &mut LcgPrng) {
+ let n = rng.next_in_range(self.hashes.len());
+ let bit = rng.next_u8();
+ let hashes = &mut self.hashes;
+ let mut hash = hashes[n].to_byte_array();
+ hash[(bit >> 3) as usize] ^= 1 << (bit & 7);
+ hashes[n] = TxMerkleNode::from_byte_array(hash);
+ }
+ }
+
+ /// Returns a real block (0000000000013b8ab2cd513b0261a14096412195a72a0c4827d229dcc7e0f7af)
+ /// with 9 txs.
+ fn get_block_13b8a() -> Block<Checked> {
+ let block_hex = include_str!("../tests/data/block_13b8a.hex");
+ let block: Block<Unchecked> =
+ encode::deserialize(&Vec::from_hex(block_hex).unwrap()).unwrap();
+ block.validate().expect("block should be valid")
+ }
+
+ macro_rules! check_calc_tree_width {
+ ($($test_name:ident, $num_transactions:literal, $height:literal, $expected_width:literal);* $(;)?) => {
+ $(
+ #[test]
+ fn $test_name() {
+ let pmt = PartialMerkleTree {
+ num_transactions: $num_transactions,
+ bits: vec![],
+ hashes: vec![],
+ };
+ let got = pmt.calc_tree_width($height);
+ assert_eq!(got, $expected_width)
+ }
+ )*
+ }
+ }
+
+ // tree_width_<id> <num txs> <height> <expected_width>
+ //
+ // height 0 is the bottom of the tree, where the leaves are.
+ check_calc_tree_width! {
+ tree_width_01, 1, 0, 1;
+ //
+ tree_width_02, 2, 0, 2;
+ tree_width_03, 2, 1, 1;
+ //
+ tree_width_04, 3, 0, 3;
+ tree_width_05, 3, 1, 2;
+ tree_width_06, 3, 2, 1;
+ //
+ tree_width_07, 4, 0, 4;
+ tree_width_08, 4, 1, 2;
+ tree_width_09, 4, 2, 1;
+ //
+ tree_width_10, 5, 0, 5;
+ tree_width_11, 5, 1, 3;
+ tree_width_12, 5, 2, 2;
+ tree_width_13, 5, 3, 1;
+ //
+ tree_width_14, 6, 0, 6;
+ tree_width_15, 6, 1, 3;
+ tree_width_16, 6, 2, 2;
+ tree_width_17, 6, 3, 1;
+ //
+ tree_width_18, 7, 0, 7;
+ tree_width_19, 7, 1, 4;
+ tree_width_20, 7, 2, 2;
+ tree_width_21, 7, 3, 1;
+ }
+
+ #[test]
+ fn regression_2606() {
+ // Attempt to deserialize a partial Merkle tree with a number of hashes that would
+ // overflow the maximum allowed size.
+ let bytes = hex!(
+ "000006000000000000000004ee00000004c7f1ccb1000000ffff000000010000\
+ 0000ffffffffff1f000000000400000000000002000000000500000000000000\
+ 000000000300000000000003000000000200000000ff00000000c7f1ccb10407\
+ 00000000000000ccb100c76538b100000004bfa9c251681b1b00040000000025\
+ 00000004bfaac251681b1b25\
+ "
+ );
+ let deser = encode::deserialize::<MerkleBlock>(&bytes);
+
+ // The attempt to deserialize should result in an error.
+ assert!(deser.is_err());
+ }
+
+ #[test]
+ fn extract_matches_from_merkleblock() {
+ // Get the proof from a bitcoind by running in the terminal:
+ // $ TXID="5a4ebf66822b0b2d56bd9dc64ece0bc38ee7844a23ff1d7320a88c5fdb2ad3e2"
+ // $ bitcoin-cli gettxoutproof [\"$TXID\"]
+ let mb_bytes = Vec::from_hex("01000000ba8b9cda965dd8e536670f9ddec10e53aab14b20bacad27b913719\
+ 0000000000190760b278fe7b8565fda3b968b918d5fd997f993b23674c0af3b6fde300b38f33a5914ce6ed5b\
+ 1b01e32f570200000002252bf9d75c4f481ebb6278d708257d1f12beb6dd30301d26c623f789b2ba6fc0e2d3\
+ 2adb5f8ca820731dff234a84e78ec30bce4ec69dbd562d0b2b8266bf4e5a0105").unwrap();
+ let mb: MerkleBlock = encode::deserialize(&mb_bytes).unwrap();
+
+ // Authenticate and extract matched transaction ids
+ let mut matches: Vec<Txid> = vec![];
+ let mut index: Vec<u32> = vec![];
+ assert!(mb.extract_matches(&mut matches, &mut index).is_ok());
+
+ // The matches and index vectors are coupled, should be the same length.
+ assert_eq!(matches.len(), index.len());
+
+ // There should only be one match.
+ assert_eq!(matches.len(), 1);
+
+ // The match should come from index 1.
+ assert_eq!(index[0], 1);
+
+ // And we know the txid we want.
+ let want = "5a4ebf66822b0b2d56bd9dc64ece0bc38ee7844a23ff1d7320a88c5fdb2ad3e2"
+ .parse::<Txid>()
+ .expect("failed to parse txid");
+ assert_eq!(matches[0], want);
+ }
+}
diff --git a/p2p/src/message.rs b/p2p/src/message.rs
index e6f7f4d7..9fbab9f8 100644
--- a/p2p/src/message.rs
+++ b/p2p/src/message.rs
@@ -16,7 +16,6 @@ use core::{cmp, fmt};
#[cfg(feature = "arbitrary")]
use arbitrary::{Arbitrary, Unstructured};
use bitcoin::consensus::encode::{self, Decodable, Encodable, ReadExt, WriteExt};
-use bitcoin::merkle_tree::MerkleBlock;
use encoding::{self, CompactSizeEncoder, Encoder2, SliceEncoder, VecDecoder};
use hashes::sha256d;
use internals::ToU64 as _;
@@ -27,6 +26,7 @@ use units::FeeRate;
use crate::address::{AddrV2Message, Address};
use crate::consensus::{impl_consensus_encoding, impl_vec_wrapper};
+use crate::merkle_tree::MerkleBlock;
use crate::{
bip152, message_blockdata, message_bloom, message_compact_blocks, message_filter,
message_network, Magic,
diff --git a/p2p/tests/data/block_13b8a.hex b/p2p/tests/data/block_13b8a.hex
new file mode 100644
index 00000000..6e83915b
--- /dev/null
+++ b/p2p/tests/data/block_13b8a.hex
@@ -0,0 +1 @@
+0100000090f0a9f110702f808219ebea1173056042a714bad51b916cb6800000000000005275289558f51c9966699404ae2294730c3c9f9bda53523ce50e9b95e558da2fdb261b4d4c86041b1ab1bf930901000000010000000000000000000000000000000000000000000000000000000000000000ffffffff07044c86041b0146ffffffff0100f2052a01000000434104e18f7afbe4721580e81e8414fc8c24d7cfacf254bb5c7b949450c3e997c2dc1242487a8169507b631eb3771f2b425483fb13102c4eb5d858eef260fe70fbfae0ac00000000010000000196608ccbafa16abada902780da4dc35dafd7af05fa0da08cf833575f8cf9e836000000004a493046022100dab24889213caf43ae6adc41cf1c9396c08240c199f5225acf45416330fd7dbd022100fe37900e0644bf574493a07fc5edba06dbc07c311b947520c2d514bc5725dcb401ffffffff0100f2052a010000001976a914f15d1921f52e4007b146dfa60f369ed2fc393ce288ac000000000100000001fb766c1288458c2bafcfec81e48b24d98ec706de6b8af7c4e3c29419bfacb56d000000008c493046022100f268ba165ce0ad2e6d93f089cfcd3785de5c963bb5ea6b8c1b23f1ce3e517b9f022100da7c0f21adc6c401887f2bfd1922f11d76159cbc597fbd756a23dcbb00f4d7290141042b4e8625a96127826915a5b109852636ad0da753c9e1d5606a50480cd0c40f1f8b8d898235e571fe9357d9ec842bc4bba1827daaf4de06d71844d0057707966affffffff0280969800000000001976a9146963907531db72d0ed1a0cfb471ccb63923446f388ac80d6e34c000000001976a914f0688ba1c0d1ce182c7af6741e02658c7d4dfcd388ac000000000100000002c40297f730dd7b5a99567eb8d27b78758f607507c52292d02d4031895b52f2ff010000008b483045022100f7edfd4b0aac404e5bab4fd3889e0c6c41aa8d0e6fa122316f68eddd0a65013902205b09cc8b2d56e1cd1f7f2fafd60a129ed94504c4ac7bdc67b56fe67512658b3e014104732012cb962afa90d31b25d8fb0e32c94e513ab7a17805c14ca4c3423e18b4fb5d0e676841733cb83abaf975845c9f6f2a8097b7d04f4908b18368d6fc2d68ecffffffffca5065ff9617cbcba45eb23726df6498a9b9cafed4f54cbab9d227b0035ddefb000000008a473044022068010362a13c7f9919fa832b2dee4e788f61f6f5d344a7c2a0da6ae740605658022006d1af525b9a14a35c003b78b72bd59738cd676f845d1ff3fc25049e01003614014104732012cb962afa90d31b25d8fb0e32c94e513ab7a17805c14ca4c3423e18b4fb5d0e676841733cb83abaf975845c9f6f2a8097b7d04f4908b18368d6fc2d68ecffffffff01001ec4110200000043410469ab4181eceb28985b9b4e895c13fa5e68d85761b7eee311db5addef76fa8621865134a221bd01f28ec9999ee3e021e60766e9d1f3458c115fb28650605f11c9ac000000000100000001cdaf2f758e91c514655e2dc50633d1e4c84989f8aa90a0dbc883f0d23ed5c2fa010000008b48304502207ab51be6f12a1962ba0aaaf24a20e0b69b27a94fac5adf45aa7d2d18ffd9236102210086ae728b370e5329eead9accd880d0cb070aea0c96255fae6c4f1ddcce1fd56e014104462e76fd4067b3a0aa42070082dcb0bf2f388b6495cf33d789904f07d0f55c40fbd4b82963c69b3dc31895d0c772c812b1d5fbcade15312ef1c0e8ebbb12dcd4ffffffff02404b4c00000000001976a9142b6ba7c9d796b75eef7942fc9288edd37c32f5c388ac002d3101000000001976a9141befba0cdc1ad56529371864d9f6cb042faa06b588ac000000000100000001b4a47603e71b61bc3326efd90111bf02d2f549b067f4c4a8fa183b57a0f800cb010000008a4730440220177c37f9a505c3f1a1f0ce2da777c339bd8339ffa02c7cb41f0a5804f473c9230220585b25a2ee80eb59292e52b987dad92acb0c64eced92ed9ee105ad153cdb12d001410443bd44f683467e549dae7d20d1d79cbdb6df985c6e9c029c8d0c6cb46cc1a4d3cf7923c5021b27f7a0b562ada113bc85d5fda5a1b41e87fe6e8802817cf69996ffffffff0280651406000000001976a9145505614859643ab7b547cd7f1f5e7e2a12322d3788ac00aa0271000000001976a914ea4720a7a52fc166c55ff2298e07baf70ae67e1b88ac00000000010000000586c62cd602d219bb60edb14a3e204de0705176f9022fe49a538054fb14abb49e010000008c493046022100f2bc2aba2534becbdf062eb993853a42bbbc282083d0daf9b4b585bd401aa8c9022100b1d7fd7ee0b95600db8535bbf331b19eed8d961f7a8e54159c53675d5f69df8c014104462e76fd4067b3a0aa42070082dcb0bf2f388b6495cf33d789904f07d0f55c40fbd4b82963c69b3dc31895d0c772c812b1d5fbcade15312ef1c0e8ebbb12dcd4ffffffff03ad0e58ccdac3df9dc28a218bcf6f1997b0a93306faaa4b3a28ae83447b2179010000008b483045022100be12b2937179da88599e27bb31c3525097a07cdb52422d165b3ca2f2020ffcf702200971b51f853a53d644ebae9ec8f3512e442b1bcb6c315a5b491d119d10624c83014104462e76fd4067b3a0aa42070082dcb0bf2f388b6495cf33d789904f07d0f55c40fbd4b82963c69b3dc31895d0c772c812b1d5fbcade15312ef1c0e8ebbb12dcd4ffffffff2acfcab629bbc8685792603762c921580030ba144af553d271716a95089e107b010000008b483045022100fa579a840ac258871365dd48cd7552f96c8eea69bd00d84f05b283a0dab311e102207e3c0ee9234814cfbb1b659b83671618f45abc1326b9edcc77d552a4f2a805c0014104462e76fd4067b3a0aa42070082dcb0bf2f388b6495cf33d789904f07d0f55c40fbd4b82963c69b3dc31895d0c772c812b1d5fbcade15312ef1c0e8ebbb12dcd4ffffffffdcdc6023bbc9944a658ddc588e61eacb737ddf0a3cd24f113b5a8634c517fcd2000000008b4830450221008d6df731df5d32267954bd7d2dda2302b74c6c2a6aa5c0ca64ecbabc1af03c75022010e55c571d65da7701ae2da1956c442df81bbf076cdbac25133f99d98a9ed34c014104462e76fd4067b3a0aa42070082dcb0bf2f388b6495cf33d789904f07d0f55c40fbd4b82963c69b3dc31895d0c772c812b1d5fbcade15312ef1c0e8ebbb12dcd4ffffffffe15557cd5ce258f479dfd6dc6514edf6d7ed5b21fcfa4a038fd69f06b83ac76e010000008b483045022023b3e0ab071eb11de2eb1cc3a67261b866f86bf6867d4558165f7c8c8aca2d86022100dc6e1f53a91de3efe8f63512850811f26284b62f850c70ca73ed5de8771fb451014104462e76fd4067b3a0aa42070082dcb0bf2f388b6495cf33d789904f07d0f55c40fbd4b82963c69b3dc31895d0c772c812b1d5fbcade15312ef1c0e8ebbb12dcd4ffffffff01404b4c00000000001976a9142b6ba7c9d796b75eef7942fc9288edd37c32f5c388ac00000000010000000166d7577163c932b4f9690ca6a80b6e4eb001f0a2fa9023df5595602aae96ed8d000000008a4730440220262b42546302dfb654a229cefc86432b89628ff259dc87edd1154535b16a67e102207b4634c020a97c3e7bbd0d4d19da6aa2269ad9dded4026e896b213d73ca4b63f014104979b82d02226b3a4597523845754d44f13639e3bf2df5e82c6aab2bdc79687368b01b1ab8b19875ae3c90d661a3d0a33161dab29934edeb36aa01976be3baf8affffffff02404b4c00000000001976a9144854e695a02af0aeacb823ccbc272134561e0a1688ac40420f00000000001976a914abee93376d6b37b5c2940655a6fcaf1c8e74237988ac0000000001000000014e3f8ef2e91349a9059cb4f01e54ab2597c1387161d3da89919f7ea6acdbb371010000008c49304602210081f3183471a5ca22307c0800226f3ef9c353069e0773ac76bb580654d56aa523022100d4c56465bdc069060846f4fbf2f6b20520b2a80b08b168b31e66ddb9c694e240014104976c79848e18251612f8940875b2b08d06e6dc73b9840e8860c066b7e87432c477e9a59a453e71e6d76d5fe34058b800a098fc1740ce3012e8fc8a00c96af966ffffffff02c0e1e400000000001976a9144134e75a6fcb6042034aab5e18570cf1f844f54788ac404b4c00000000001976a9142b6ba7c9d796b75eef7942fc9288edd37c32f5c388ac00000000
\ No newline at end of file
diff --git a/p2p/tests/data/merkle_block.hex b/p2p/tests/data/merkle_block.hex
new file mode 100644
index 00000000..c9a32c9a
--- /dev/null
+++ b/p2p/tests/data/merkle_block.hex
@@ -0,0 +1 @@
+0100000090f0a9f110702f808219ebea1173056042a714bad51b916cb6800000000000005275289558f51c9966699404ae2294730c3c9f9bda53523ce50e9b95e558da2fdb261b4d4c86041b1ab1bf930900000005fac7708a6e81b2a986dea60db2663840ed141130848162eb1bd1dee54f309a1b2ee1e12587e497ada70d9bd10d31e83f0a924825b96cb8d04e8936d793fb60db7ad8b910d0c7ba2369bc7f18bb53d80e1869ba2c32274996cebe1ae264bc0e2289189ff0316cdc10511da71da757e553cada9f3b5b1434f3923673adb57d83caac392c38af156d6fc30b55fad4112df2b95531e68114e9ad10011e72f7b7cfdb025700
\ No newline at end of file
Risk score
Our methodology →Why this scored 19/100
Human-validated context
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
No validated notes yet.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.