primitives: add test comparing batch and stacked-based merkle root
What the developer wrote
Authored by jrakibi
primitives: add test comparing batch and stacked-based merkle root
compare the old stack-based approach to calculate the merkle root
against the new batched level-by-level approach.
What changed, and why it matters
This commit only adds a new unit test. It does not change any production code, fix a bug, or alter behavior. The test compares two different ways of computing the same merkle root to make sure they produce identical results.
No security action needed. This is a test-only addition and can be reviewed as normal code quality.
Security signals we found
No strong security signals were identified.
Evidence from the diff
The diff adds a single test function, test_merkle_root_batched, in primitives/src/merkle_tree.rs. It embeds a copy of the old stack-based Merkle root calculation and compares its output against the existing batched level-by-level implementation (TxMerkleNode::calculate_root) for 32 and 33 leaves. No library code is modified.
Changed components
Inspect captured patch +56 / −0
diff --git a/primitives/src/merkle_tree.rs b/primitives/src/merkle_tree.rs
index 2e061897..49ed1f0a 100644
--- a/primitives/src/merkle_tree.rs
+++ b/primitives/src/merkle_tree.rs
@@ -317,6 +317,62 @@ mod tests {
assert_ne!(root, None);
}
+ #[test]
+ #[cfg(feature = "alloc")]
+ fn test_merkle_root_batched() {
+ use alloc::vec::Vec;
+
+ // copy of `MerkleNode::calculate_root` (stack-based) implementation to test against the new batched approach
+ fn stack_based_root<I: Iterator<Item = Txid>>(iter: I) -> Option<TxMerkleNode> {
+ let mut stack = Vec::<(usize, TxMerkleNode)>::with_capacity(32);
+
+ for (mut n, leaf) in iter.enumerate() {
+ stack.push((0, TxMerkleNode::from_leaf(leaf)));
+
+ while n & 1 == 1 {
+ let right = stack.pop().unwrap();
+ let left = stack.pop().unwrap();
+ if left.1 == right.1 {
+ return None;
+ }
+ debug_assert_eq!(left.0, right.0);
+ stack.push((left.0 + 1, left.1.combine(&right.1)));
+ n >>= 1;
+ }
+ }
+
+ 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)
+ }
+
+ fn make_leaves(count: usize) -> Vec<Txid> {
+ (0..count as u32)
+ .map(|i| {
+ let mut buf = [0u8; 32];
+ buf[..4].copy_from_slice(&i.to_le_bytes());
+ Txid::from_byte_array(buf)
+ })
+ .collect()
+ }
+
+ // test odd and even count
+ for size in [32, 33] {
+ let leaves = make_leaves(size);
+ let got = TxMerkleNode::calculate_root(leaves.iter().copied());
+ let expected = stack_based_root(leaves.iter().copied());
+ assert_eq!(got, expected);
+ }
+ }
+
#[test]
fn witness_merkle_node_single_leaf() {
let leaf = Wtxid::from_byte_array([1; 32]);
Why this scored 15/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.