primitives: Move MerkleNode and TxIdentifier into primitives

diff --git a/.cargo/mutants.toml b/.cargo/mutants.toml
index 8d2cba2a..83a47a2e 100644
--- a/.cargo/mutants.toml
+++ b/.cargo/mutants.toml
@@ -50,6 +50,7 @@ exclude_re = [
     "primitives/.* <impl Encoder for .*Encoder<'_>>::advance", # Replacing the return with true causes an infinite loop.
     "primitives/.* <impl Decoder for WitnessDecoder>::push_bytes", # Replacing == with != causes an infinite loop
     "primitives/.* WitnessDecoder::resize_if_needed", # Replacing *= with += still resizes the buffer making the mutant untestable.
+    "primitives/.* replace \\+ with \\* in MerkleNode::calculate_root", # Replacing + with * causes an infinite loop
 
     # consensus_encoding - most of these are for mutations in the logic used to determine when to stop encoding or decoding.
     "consensus_encoding/.* <impl Decoder for ArrayDecoder<N>>::push_bytes", # Mutations cause an infinite loop
diff --git a/api/primitives/all-features.txt b/api/primitives/all-features.txt
index 04d7c50b..71d56616 100644
--- a/api/primitives/all-features.txt
+++ b/api/primitives/all-features.txt
@@ -1318,13 +1318,16 @@ pub fn bitcoin_primitives::TxMerkleNode::as_ref(&self) -> &[u8; 32]
 pub fn bitcoin_primitives::TxMerkleNode::as_ref(&self) -> &[u8]
 pub fn bitcoin_primitives::TxMerkleNode::borrow(&self) -> &[u8; 32]
 pub fn bitcoin_primitives::TxMerkleNode::borrow(&self) -> &[u8]
+pub fn bitcoin_primitives::TxMerkleNode::calculate_root<I: core::iter::traits::iterator::Iterator<Item = bitcoin_primitives::Txid>>(iter: I) -> core::option::Option<Self>
 pub fn bitcoin_primitives::TxMerkleNode::clone(&self) -> bitcoin_primitives::TxMerkleNode
 pub fn bitcoin_primitives::TxMerkleNode::cmp(&self, other: &bitcoin_primitives::TxMerkleNode) -> core::cmp::Ordering
+pub fn bitcoin_primitives::TxMerkleNode::combine(&self, other: &Self) -> Self
 pub fn bitcoin_primitives::TxMerkleNode::decoder() -> Self::Decoder
 pub fn bitcoin_primitives::TxMerkleNode::deserialize<D: serde::de::Deserializer<'de>>(d: D) -> core::result::Result<bitcoin_primitives::TxMerkleNode, <D as serde::de::Deserializer>::Error>
 pub fn bitcoin_primitives::TxMerkleNode::encoder(&self) -> Self::Encoder
 pub fn bitcoin_primitives::TxMerkleNode::eq(&self, other: &bitcoin_primitives::TxMerkleNode) -> bool
 pub fn bitcoin_primitives::TxMerkleNode::fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result
+pub fn bitcoin_primitives::TxMerkleNode::from_leaf(leaf: bitcoin_primitives::Txid) -> Self
 pub fn bitcoin_primitives::TxMerkleNode::from_str(s: &str) -> core::result::Result<Self, Self::Err>
 pub fn bitcoin_primitives::TxMerkleNode::hash<__H: core::hash::Hasher>(&self, state: &mut __H)
 pub fn bitcoin_primitives::TxMerkleNode::partial_cmp(&self, other: &bitcoin_primitives::TxMerkleNode) -> core::option::Option<core::cmp::Ordering>
@@ -1364,11 +1367,14 @@ pub fn bitcoin_primitives::WitnessMerkleNode::as_ref(&self) -> &[u8; 32]
 pub fn bitcoin_primitives::WitnessMerkleNode::as_ref(&self) -> &[u8]
 pub fn bitcoin_primitives::WitnessMerkleNode::borrow(&self) -> &[u8; 32]
 pub fn bitcoin_primitives::WitnessMerkleNode::borrow(&self) -> &[u8]
+pub fn bitcoin_primitives::WitnessMerkleNode::calculate_root<I: core::iter::traits::iterator::Iterator<Item = bitcoin_primitives::Wtxid>>(iter: I) -> core::option::Option<Self>
 pub fn bitcoin_primitives::WitnessMerkleNode::clone(&self) -> bitcoin_primitives::WitnessMerkleNode
 pub fn bitcoin_primitives::WitnessMerkleNode::cmp(&self, other: &bitcoin_primitives::WitnessMerkleNode) -> core::cmp::Ordering
+pub fn bitcoin_primitives::WitnessMerkleNode::combine(&self, other: &Self) -> Self
 pub fn bitcoin_primitives::WitnessMerkleNode::deserialize<D: serde::de::Deserializer<'de>>(d: D) -> core::result::Result<bitcoin_primitives::WitnessMerkleNode, <D as serde::de::Deserializer>::Error>
 pub fn bitcoin_primitives::WitnessMerkleNode::eq(&self, other: &bitcoin_primitives::WitnessMerkleNode) -> bool
 pub fn bitcoin_primitives::WitnessMerkleNode::fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result
+pub fn bitcoin_primitives::WitnessMerkleNode::from_leaf(leaf: bitcoin_primitives::Wtxid) -> Self
 pub fn bitcoin_primitives::WitnessMerkleNode::from_str(s: &str) -> core::result::Result<Self, Self::Err>
 pub fn bitcoin_primitives::WitnessMerkleNode::hash<__H: core::hash::Hasher>(&self, state: &mut __H)
 pub fn bitcoin_primitives::WitnessMerkleNode::partial_cmp(&self, other: &bitcoin_primitives::WitnessMerkleNode) -> core::option::Option<core::cmp::Ordering>
diff --git a/api/primitives/alloc-only.txt b/api/primitives/alloc-only.txt
index bd56264d..48915858 100644
--- a/api/primitives/alloc-only.txt
+++ b/api/primitives/alloc-only.txt
@@ -1175,12 +1175,15 @@ pub fn bitcoin_primitives::TxMerkleNode::as_ref(&self) -> &[u8; 32]
 pub fn bitcoin_primitives::TxMerkleNode::as_ref(&self) -> &[u8]
 pub fn bitcoin_primitives::TxMerkleNode::borrow(&self) -> &[u8; 32]
 pub fn bitcoin_primitives::TxMerkleNode::borrow(&self) -> &[u8]
+pub fn bitcoin_primitives::TxMerkleNode::calculate_root<I: core::iter::traits::iterator::Iterator<Item = bitcoin_primitives::Txid>>(iter: I) -> core::option::Option<Self>
 pub fn bitcoin_primitives::TxMerkleNode::clone(&self) -> bitcoin_primitives::TxMerkleNode
 pub fn bitcoin_primitives::TxMerkleNode::cmp(&self, other: &bitcoin_primitives::TxMerkleNode) -> core::cmp::Ordering
+pub fn bitcoin_primitives::TxMerkleNode::combine(&self, other: &Self) -> Self
 pub fn bitcoin_primitives::TxMerkleNode::decoder() -> Self::Decoder
 pub fn bitcoin_primitives::TxMerkleNode::encoder(&self) -> Self::Encoder
 pub fn bitcoin_primitives::TxMerkleNode::eq(&self, other: &bitcoin_primitives::TxMerkleNode) -> bool
 pub fn bitcoin_primitives::TxMerkleNode::fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result
+pub fn bitcoin_primitives::TxMerkleNode::from_leaf(leaf: bitcoin_primitives::Txid) -> Self
 pub fn bitcoin_primitives::TxMerkleNode::hash<__H: core::hash::Hasher>(&self, state: &mut __H)
 pub fn bitcoin_primitives::TxMerkleNode::partial_cmp(&self, other: &bitcoin_primitives::TxMerkleNode) -> core::option::Option<core::cmp::Ordering>
 pub fn bitcoin_primitives::Txid::as_ref(&self) -> &[u8; 32]
@@ -1209,10 +1212,13 @@ pub fn bitcoin_primitives::WitnessMerkleNode::as_ref(&self) -> &[u8; 32]
 pub fn bitcoin_primitives::WitnessMerkleNode::as_ref(&self) -> &[u8]
 pub fn bitcoin_primitives::WitnessMerkleNode::borrow(&self) -> &[u8; 32]
 pub fn bitcoin_primitives::WitnessMerkleNode::borrow(&self) -> &[u8]
+pub fn bitcoin_primitives::WitnessMerkleNode::calculate_root<I: core::iter::traits::iterator::Iterator<Item = bitcoin_primitives::Wtxid>>(iter: I) -> core::option::Option<Self>
 pub fn bitcoin_primitives::WitnessMerkleNode::clone(&self) -> bitcoin_primitives::WitnessMerkleNode
 pub fn bitcoin_primitives::WitnessMerkleNode::cmp(&self, other: &bitcoin_primitives::WitnessMerkleNode) -> core::cmp::Ordering
+pub fn bitcoin_primitives::WitnessMerkleNode::combine(&self, other: &Self) -> Self
 pub fn bitcoin_primitives::WitnessMerkleNode::eq(&self, other: &bitcoin_primitives::WitnessMerkleNode) -> bool
 pub fn bitcoin_primitives::WitnessMerkleNode::fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result
+pub fn bitcoin_primitives::WitnessMerkleNode::from_leaf(leaf: bitcoin_primitives::Wtxid) -> Self
 pub fn bitcoin_primitives::WitnessMerkleNode::hash<__H: core::hash::Hasher>(&self, state: &mut __H)
 pub fn bitcoin_primitives::WitnessMerkleNode::partial_cmp(&self, other: &bitcoin_primitives::WitnessMerkleNode) -> core::option::Option<core::cmp::Ordering>
 pub fn bitcoin_primitives::Wtxid::as_ref(&self) -> &[u8; 32]
diff --git a/bitcoin/src/blockdata/block.rs b/bitcoin/src/blockdata/block.rs
index 2eb7890d..c970db19 100644
--- a/bitcoin/src/blockdata/block.rs
+++ b/bitcoin/src/blockdata/block.rs
@@ -15,7 +15,7 @@ use internals::{compact_size, ToU64};
 use io::{BufRead, Write};
 
 use crate::consensus::encode::{self, Decodable, Encodable, WriteExt as _};
-use crate::merkle_tree::{MerkleNode as _, TxMerkleNode, WitnessMerkleNode};
+use crate::merkle_tree::{TxMerkleNode, WitnessMerkleNode};
 use crate::network::Params;
 use crate::prelude::Vec;
 use crate::script::{self, ScriptIntError, ScriptExt as _};
diff --git a/bitcoin/src/merkle_tree/block.rs b/bitcoin/src/merkle_tree/block.rs
index 73daf03c..9b068220 100644
--- a/bitcoin/src/merkle_tree/block.rs
+++ b/bitcoin/src/merkle_tree/block.rs
@@ -19,7 +19,7 @@ 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::{MerkleNode as _, TxMerkleNode};
+use crate::merkle_tree::TxMerkleNode;
 use crate::prelude::Vec;
 use crate::transaction::{Transaction, Txid};
 use crate::Weight;
diff --git a/bitcoin/src/merkle_tree/mod.rs b/bitcoin/src/merkle_tree/mod.rs
index bd677931..81995949 100644
--- a/bitcoin/src/merkle_tree/mod.rs
+++ b/bitcoin/src/merkle_tree/mod.rs
@@ -6,7 +6,7 @@
 //!
 //! ```
 //! # use bitcoin::Txid;
-//! # use bitcoin::merkle_tree::{MerkleNode as _, TxMerkleNode};
+//! # use bitcoin::merkle_tree::TxMerkleNode;
 //! # let tx1 = Txid::from_byte_array([0xAA; 32]);  // Arbitrary dummy hash values.
 //! # let tx2 = Txid::from_byte_array([0xFF; 32]);
 //! let tx_hashes = [tx1, tx2]; // All the hashes we wish to merkelize.
@@ -16,13 +16,8 @@
 
 mod block;
 
-use hashes::{sha256d, HashEngine as _};
 use io::{BufRead, Write};
 
-use crate::prelude::Vec;
-use crate::transaction::TxIdentifier;
-use crate::{Txid, Wtxid};
-
 #[rustfmt::skip]
 #[doc(inline)]
 pub use self::block::{MerkleBlock, MerkleBlockError, PartialMerkleTree};
@@ -53,105 +48,3 @@ impl Decodable for WitnessMerkleNode {
         Ok(Self::from_byte_array(<[u8; 32]>::consensus_decode(r)?))
     }
 }
-
-/// A node in a Merkle tree of transactions or witness data within a block.
-///
-/// This trait is used to compute the transaction Merkle root contained in
-/// a block header. This is a particularly weird algorithm -- it interprets
-/// the list of transactions as a balanced binary tree, duplicating branches
-/// as needed to fill out the tree to a power of two size.
-///
-/// Other Merkle trees in Bitcoin, such as those used in Taproot commitments,
-/// do not use this algorithm and cannot use this trait.
-pub trait MerkleNode: Copy + PartialEq {
-    /// The hash (TXID or WTXID) of a transaction in the tree.
-    type Leaf: TxIdentifier;
-
-    /// Convert a hash to a leaf node of the tree.
-    fn from_leaf(leaf: Self::Leaf) -> Self;
-    /// Combine two nodes to get a single node. The final node of a tree is called the "root".
-    fn combine(&self, other: &Self) -> Self;
-
-    /// Given an iterator of leaves, compute the Merkle root.
-    ///
-    /// Returns `None` if the iterator was empty, or if the transaction list contains
-    /// consecutive duplicates which would trigger CVE 2012-2459. Blocks with duplicate
-    /// transactions will always be invalid, so there is no harm in us refusing to
-    /// compute their merkle roots.
-    ///
-    /// Unless you are certain your transaction list is nonempty and has no duplicates,
-    /// you should not unwrap the `Option` returned by this method!
-    fn calculate_root<I: Iterator<Item = Self::Leaf>>(iter: I) -> Option<Self> {
-        let mut stack = Vec::<(usize, Self)>::with_capacity(32);
-        // Start with a standard Merkle tree root computation...
-        for (mut n, leaf) in iter.enumerate() {
-            stack.push((0, Self::from_leaf(leaf)));
-
-            while n & 1 == 1 {
-                let right = stack.pop().unwrap();
-                let left = stack.pop().unwrap();
-                if left.1 == right.1 {
-                    // Reject duplicate trees since they are guaranteed-invalid (Bitcoin does
-                    // not allow duplicate transactions in block) but can be used to confuse
-                    // nodes about legitimate blocks. See CVE 2012-2459 and the block comment
-                    // below.
-                    return None;
-                }
-                debug_assert_eq!(left.0, right.0);
-                stack.push((left.0 + 1, left.1.combine(&right.1)));
-                n >>= 1;
-            }
-        }
-        // ...then, deal with incomplete trees. Bitcoin does a weird thing in
-        // which it doubles-up nodes of the tree to fill out the tree, rather
-        // than treating incomplete branches specially. This makes this tree
-        // construction vulnerable to collisions (see CVE 2012-2459).
-        //
-        // (It is also vulnerable to collisions because it does not distinguish
-        // between internal nodes and transactions, but this collisions of this
-        // form are probably impractical. It is likely that 64-byte transactions
-        // will be forbidden in the future which will close this for good.)
-        //
-        // This is consensus logic so we cannot fix the Merkle tree construction.
-        // Instead we just have to reject the clearly-invalid half of the collision
-        // (see previous comment).
-        while stack.len() > 1 {
-            let mut right = stack.pop().unwrap();
-            let left = stack.pop().unwrap();
-            while right.0 != left.0 {
-                assert!(right.0 < left.0);
-                right = (right.0 + 1, right.1.combine(&right.1)); // combine with self
-            }
-            stack.push((left.0 + 1, left.1.combine(&right.1)));
-        }
-
-        stack.pop().map(|(_, h)| h)
-    }
-}
-
-// These two impl blocks are identical. FIXME once we have nailed down
-// our hash traits, it should be possible to put bounds on `MerkleNode`
-// and `MerkleNode::Leaf` which are sufficient to turn both methods into
-// provided methods in the trait definition.
-impl MerkleNode for TxMerkleNode {
-    type Leaf = Txid;
-    fn from_leaf(leaf: Self::Leaf) -> Self { Self::from_byte_array(leaf.to_byte_array()) }
-
-    fn combine(&self, other: &Self) -> Self {
-        let mut encoder = sha256d::Hash::engine();
-        encoder.input(self.as_byte_array());
-        encoder.input(other.as_byte_array());
-        Self::from_byte_array(sha256d::Hash::from_engine(encoder).to_byte_array())
-    }
-}
-impl MerkleNode for WitnessMerkleNode {
-    type Leaf = Wtxid;
-    fn from_leaf(leaf: Self::Leaf) -> Self { Self::from_byte_array(leaf.to_byte_array()) }
-
-    fn combine(&self, other: &Self) -> Self {
-        let mut encoder = sha256d::Hash::engine();
-        encoder.input(self.as_byte_array());
-        encoder.input(other.as_byte_array());
-        Self::from_byte_array(sha256d::Hash::from_engine(encoder).to_byte_array())
-    }
-}
diff --git a/primitives/src/hash_types/transaction_merkle_node.rs b/primitives/src/hash_types/transaction_merkle_node.rs
index a2aa1e02..e95821c1 100644
--- a/primitives/src/hash_types/transaction_merkle_node.rs
+++ b/primitives/src/hash_types/transaction_merkle_node.rs
@@ -12,6 +12,11 @@ use arbitrary::{Arbitrary, Unstructured};
 use hashes::sha256d;
 use internals::write_err;
 
+#[cfg(feature = "alloc")]
+use crate::merkle_tree::MerkleNode;
+#[cfg(feature = "alloc")]
+use crate::Txid;
+
 /// A hash of the Merkle tree branch or root for transactions.
 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub struct TxMerkleNode(sha256d::Hash);
@@ -23,6 +28,27 @@ type Inner = sha256d::Hash;
 
 include!("./generic.rs");
 
+#[cfg(feature = "alloc")]
+impl TxMerkleNode {
+    /// Convert a [`Txid`] hash to a leaf node of the tree.
+    pub fn from_leaf(leaf: Txid) -> Self { MerkleNode::from_leaf(leaf) }
+
+    /// Combine two nodes to get a single node. The final node of a tree is called the "root".
+    #[must_use]
+    pub fn combine(&self, other: &Self) -> Self { MerkleNode::combine(self, other) }
+
+    /// Given an iterator of leaves, compute the Merkle root.
+    ///
+    /// Returns `None` if the iterator was empty, or if the transaction list contains
+    /// consecutive duplicates which would trigger CVE 2012-2459. Blocks with duplicate
+    /// transactions will always be invalid, so there is no harm in us refusing to
+    /// compute their merkle roots.
+    ///
+    /// Unless you are certain your transaction list is nonempty and has no duplicates,
+    /// you should not unwrap the `Option` returned by this method!
+    pub fn calculate_root<I: Iterator<Item = Txid>>(iter: I) -> Option<Self> { MerkleNode::calculate_root(iter) }
+}
+
 encoding::encoder_newtype! {
     /// The encoder for the [`TxMerkleNode`] type.
     pub struct TxMerkleNodeEncoder(encoding::ArrayEncoder<32>);
diff --git a/primitives/src/hash_types/witness_merkle_node.rs b/primitives/src/hash_types/witness_merkle_node.rs
index 49b9ed12..d10c579d 100644
--- a/primitives/src/hash_types/witness_merkle_node.rs
+++ b/primitives/src/hash_types/witness_merkle_node.rs
@@ -11,6 +11,11 @@ use core::str;
 use arbitrary::{Arbitrary, Unstructured};
 use hashes::sha256d;
 
+#[cfg(feature = "alloc")]
+use crate::merkle_tree::MerkleNode;
+#[cfg(feature = "alloc")]
+use crate::Wtxid;
+
 /// A hash corresponding to the Merkle tree root for witness data.
 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub struct WitnessMerkleNode(sha256d::Hash);
@@ -21,3 +26,24 @@ type HashType = WitnessMerkleNode;
 type Inner = sha256d::Hash;
 
 include!("./generic.rs");
+
+#[cfg(feature = "alloc")]
+impl WitnessMerkleNode {
+    /// Convert a [`Wtxid`] hash to a leaf node of the tree.
+    pub fn from_leaf(leaf: Wtxid) -> Self { MerkleNode::from_leaf(leaf) }
+
+    /// Combine two nodes to get a single node. The final node of a tree is called the "root".
+    #[must_use]
+    pub fn combine(&self, other: &Self) -> Self { MerkleNode::combine(self, other) }
+
+    /// Given an iterator of leaves, compute the Merkle root.
+    ///
+    /// Returns `None` if the iterator was empty, or if the transaction list contains
+    /// consecutive duplicates which would trigger CVE 2012-2459. Blocks with duplicate
+    /// transactions will always be invalid, so there is no harm in us refusing to
+    /// compute their merkle roots.
+    ///
+    /// Unless you are certain your transaction list is nonempty and has no duplicates,
+    /// you should not unwrap the `Option` returned by this method!
+    pub fn calculate_root<I: Iterator<Item = Wtxid>>(iter: I) -> Option<Self> { MerkleNode::calculate_root(iter) }
+}
diff --git a/primitives/src/merkle_tree.rs b/primitives/src/merkle_tree.rs
index e037644b..e6bb0b65 100644
--- a/primitives/src/merkle_tree.rs
+++ b/primitives/src/merkle_tree.rs
@@ -9,6 +9,254 @@
 // - We define all the other hash types in some module so the merkle tree hash types need a module.
 //
 // C'est la vie.
+#[cfg(feature = "alloc")]
+use alloc::vec::Vec;
+
+#[cfg(feature = "alloc")]
+use hashes::{HashEngine, sha256d};
+
+#[cfg(feature = "alloc")]
+use crate::hash_types::{Txid, Wtxid};
+#[cfg(feature = "alloc")]
+use crate::transaction::TxIdentifier;
 
 #[doc(inline)]
 pub use crate::hash_types::{TxMerkleNode, TxMerkleNodeEncoder, WitnessMerkleNode};
+
+/// A node in a Merkle tree of transactions or witness data within a block.
+///
+/// This trait is used to compute the transaction Merkle root contained in
+/// a block header. This is a particularly weird algorithm -- it interprets
+/// the list of transactions as a balanced binary tree, duplicating branches
+/// as needed to fill out the tree to a power of two size.
+///
+/// Other Merkle trees in Bitcoin, such as those used in Taproot commitments,
+/// do not use this algorithm and cannot use this trait.
+#[cfg(feature = "alloc")]
+pub(crate) trait MerkleNode: Copy + PartialEq {
+    /// The hash (TXID or WTXID) of a transaction in the tree.
+    type Leaf: TxIdentifier;
+
+    /// Convert a hash to a leaf node of the tree.
+    fn from_leaf(leaf: Self::Leaf) -> Self;
+    /// Combine two nodes to get a single node. The final node of a tree is called the "root".
+    #[must_use]
+    fn combine(&self, other: &Self) -> Self;
+
+    /// Given an iterator of leaves, compute the Merkle root.
+    ///
+    /// Returns `None` if the iterator was empty, or if the transaction list contains
+    /// consecutive duplicates which would trigger CVE 2012-2459. Blocks with duplicate
+    /// transactions will always be invalid, so there is no harm in us refusing to
+    /// compute their merkle roots.
+    ///
+    /// Unless you are certain your transaction list is nonempty and has no duplicates,
+    /// you should not unwrap the `Option` returned by this method!
+    fn calculate_root<I: Iterator<Item = Self::Leaf>>(iter: I) -> Option<Self> {
+        {
+            let mut stack = Vec::<(usize, Self)>::with_capacity(32);
+            // Start with a standard Merkle tree root computation...
+            for (mut n, leaf) in iter.enumerate() {
+                stack.push((0, Self::from_leaf(leaf)));
+
+                while n & 1 == 1 {
+                    let right = stack.pop().unwrap();
+                    let left = stack.pop().unwrap();
+                    if left.1 == right.1 {
+                        // Reject duplicate trees since they are guaranteed-invalid (Bitcoin does
+                        // not allow duplicate transactions in block) but can be used to confuse
+                        // nodes about legitimate blocks. See CVE 2012-2459 and the block comment
+                        // below.
+                        return None;
+                    }
+                    debug_assert_eq!(left.0, right.0);
+                    stack.push((left.0 + 1, left.1.combine(&right.1)));
+                    n >>= 1;
+                }
+            }
+            // ...then, deal with incomplete trees. Bitcoin does a weird thing in
+            // which it doubles-up nodes of the tree to fill out the tree, rather
+            // than treating incomplete branches specially. This makes this tree
+            // construction vulnerable to collisions (see CVE 2012-2459).
+            //
+            // (It is also vulnerable to collisions because it does not distinguish
+            // between internal nodes and transactions, but this collisions of this
+            // form are probably impractical. It is likely that 64-byte transactions
+            // will be forbidden in the future which will close this for good.)
+            //
+            // This is consensus logic so we cannot fix the Merkle tree construction.
+            // Instead we just have to reject the clearly-invalid half of the collision
+            // (see previous comment).
+            while stack.len() > 1 {
+                let mut right = stack.pop().unwrap();
+                let left = stack.pop().unwrap();
+                while right.0 != left.0 {
+                    assert!(right.0 < left.0);
+                    right = (right.0 + 1, right.1.combine(&right.1)); // combine with self
+                }
+                stack.push((left.0 + 1, left.1.combine(&right.1)));
+            }
+
+            stack.pop().map(|(_, h)| h)
+        }
+    }
+}
+
+// These two impl blocks are identical. FIXME once we have nailed down
+// our hash traits, it should be possible to put bounds on `MerkleNode`
+// and `MerkleNode::Leaf` which are sufficient to turn both methods into
+// provided methods in the trait definition.
+#[cfg(feature = "alloc")]
+impl MerkleNode for TxMerkleNode {
+    type Leaf = Txid;
+    fn from_leaf(leaf: Self::Leaf) -> Self { Self::from_byte_array(leaf.to_byte_array()) }
+
+    fn combine(&self, other: &Self) -> Self {
+        let mut encoder = sha256d::Hash::engine();
+        encoder.input(self.as_byte_array());
+        encoder.input(other.as_byte_array());
+        Self::from_byte_array(sha256d::Hash::from_engine(encoder).to_byte_array())
+    }
+}
+#[cfg(feature = "alloc")]
+impl MerkleNode for WitnessMerkleNode {
+    type Leaf = Wtxid;
+    fn from_leaf(leaf: Self::Leaf) -> Self { Self::from_byte_array(leaf.to_byte_array()) }
+
+    fn combine(&self, other: &Self) -> Self {
+        let mut encoder = sha256d::Hash::engine();
+        encoder.input(self.as_byte_array());
+        encoder.input(other.as_byte_array());
+        Self::from_byte_array(sha256d::Hash::from_engine(encoder).to_byte_array())
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    #[cfg(feature = "alloc")]
+    use crate::hash_types::*;
+
+    // Helper to make a Txid, TxMerkleNode pair with a single number byte array
+    #[cfg(feature = "alloc")]
+    fn make_leaf_node(byte: u8) -> (Txid, TxMerkleNode) {
+        let leaf = Txid::from_byte_array([byte; 32]);
+        let node = TxMerkleNode::from_leaf(leaf);
+        (leaf, node)
+    }
+
+    #[test]
+    #[cfg(feature = "alloc")]
+    fn tx_merkle_node_single_leaf() {
+        let (leaf, node) = make_leaf_node(1);
+        let root = TxMerkleNode::calculate_root([leaf].into_iter());
+        assert!(root.is_some(), "Root should exist for a single leaf");
+        assert_eq!(root.unwrap(), node, "Root should equal the leaf node");
+    }
+
+    #[test]
+    #[cfg(feature = "alloc")]
+    fn tx_merkle_node_two_leaves() {
+        let (leaf1, node1) = make_leaf_node(1);
+        let (leaf2, node2) = make_leaf_node(2);
+        let combined = node1.combine(&node2);
+
+        let root = TxMerkleNode::calculate_root([leaf1, leaf2].into_iter());
+        assert_eq!(
+            root.unwrap(),
+            combined,
+            "Root of two leaves should equal combine of the two leaf nodes"
+        );
+    }
+
+    #[test]
+    #[cfg(feature = "alloc")]
+    fn tx_merkle_node_duplicate_leaves() {
+        let leaf = Txid::from_byte_array([3; 32]);
+        // Duplicate transaction list should be rejected (CVE 2012‑2459).
+        let root = TxMerkleNode::calculate_root([leaf, leaf].into_iter());
+        assert!(root.is_none(), "Duplicate leaves should return None");
+    }
+
+    #[test]
+    #[cfg(feature = "alloc")]
+    fn tx_merkle_node_empty() {
+        assert!(TxMerkleNode::calculate_root([].into_iter()).is_none(), "Empty iterator should return None");
+    }
+
+    #[test]
+    #[cfg(feature = "alloc")]
+    fn tx_merkle_node_2n_minus_1_unbalanced_tree() {
+        // Test a tree with 2^n - 1 unique nodes and at least 3 layers deep.
+        let (leaf1, node1) = make_leaf_node(1);
+        let (leaf2, node2) = make_leaf_node(2);
+        let (leaf3, node3) = make_leaf_node(3);
+        let (leaf4, node4) = make_leaf_node(4);
+        let (leaf5, node5) = make_leaf_node(5);
+        let (leaf6, node6) = make_leaf_node(6);
+        let (leaf7, node7) = make_leaf_node(7);
+
+        // Combine leaf nodes
+        let subtree_a = node1.combine(&node2);
+        let subtree_b = node3.combine(&node4);
+        let subtree_c = node5.combine(&node6);
+        let subtree_d = node7.combine(&node7); // doubled
+
+        // Combine the subtrees
+        let subtree_ab = subtree_a.combine(&subtree_b);
+        let subtree_cd = subtree_c.combine(&subtree_d);
+        let expected = subtree_ab.combine(&subtree_cd);
+
+        let root = TxMerkleNode::calculate_root(
+            [leaf1, leaf2, leaf3, leaf4, leaf5, leaf6, leaf7].into_iter()
+        );
+        assert_eq!(root, Some(expected));
+    }
+
+    #[test]
+    #[cfg(feature = "alloc")]
+    fn tx_merkle_node_balanced_multi_level_tree() {
+        use alloc::vec::Vec;
+
+        let leaves: Vec<_> = (0..16)
+            .map(|i| Txid::from_byte_array([i; 32]))
+            .collect();
+
+        // Create nodes for the txids.
+        let mut level = leaves
+            .iter()
+            .map(|l| TxMerkleNode::from_leaf(*l))
+            .collect::<Vec<_>>();
+
+        // Combine the leaves into a tree, ordered from left-to-right in the initial vector.
+        while level.len() > 1 {
+            level = level
+                .chunks(2)
+                .map(|chunk| chunk[0].combine(&chunk[1]))
+                .collect();
+        }
+
+        // Take the final node, which should be the root of the full tree.
+        let expected = level.pop().unwrap();
+
+        let root = TxMerkleNode::calculate_root(leaves.into_iter());
+        assert_eq!( root, Some(expected) );
+    }
+
+    #[test]
+    #[cfg(feature = "alloc")]
+    fn witness_merkle_node_single_leaf() {
+        let leaf = Wtxid::from_byte_array([1; 32]);
+        let root = WitnessMerkleNode::calculate_root([leaf].into_iter());
+        assert!(root.is_some(), "Root should exist for a single witness leaf");
+        let node = WitnessMerkleNode::from_leaf(leaf);
+        assert_eq!(root.unwrap(), node, "Root should equal the leaf node");
+    }
+
+    #[test]
+    #[cfg(feature = "alloc")]
+    fn witness_merkle_node_duplicate_leaves() {
+        let leaf = Wtxid::from_byte_array([2; 32]);
+        let root = WitnessMerkleNode::calculate_root([leaf, leaf].into_iter());
+        assert!(root.is_none(), "Duplicate witness leaves should return None");
+    }
+}
diff --git a/primitives/src/transaction.rs b/primitives/src/transaction.rs
index d7312e99..ab9adbc7 100644
--- a/primitives/src/transaction.rs
+++ b/primitives/src/transaction.rs
@@ -238,6 +238,15 @@ impl From<&Transaction> for Wtxid {
     fn from(tx: &Transaction) -> Self { tx.compute_wtxid() }
 }
 
+/// Trait that abstracts over a transaction identifier i.e., `Txid` and `Wtxid`.
+#[cfg(feature = "alloc")]
+pub(crate) trait TxIdentifier: AsRef<[u8]> {}
+
+#[cfg(feature = "alloc")]
+impl TxIdentifier for Txid {}
+#[cfg(feature = "alloc")]
+impl TxIdentifier for Wtxid {}
+
 // Duplicated in `bitcoin`.
 /// The marker MUST be a 1-byte zero value: 0x00. (BIP-0141)
 #[cfg(feature = "alloc")]