primitives: use optimized sha256d for 64-byte in merkle root computation
What the developer wrote
Authored by jrakibi
primitives: use optimized sha256d for 64-byte in merkle root computation
currently we are using stack-based approach to calculate the root.
instead of that, we can batch all pairs at each tree level into one
`hash_64_many()` call
we gate this for aarch64 to use the new batched algorithm. We will
widen to support x86 once we add a 2-way SHA-NI implementation.
for no-alloc we will always keep using the old stack-based approach
What changed, and why it matters
This commit is a performance optimization for Bitcoin merkle root calculation on ARM 64-bit (aarch64) systems. It replaces a stack-based approach with a batched hashing approach using an optimized SHA256 function. It is not a security fix and does not change behavior for most users; the old code path remains for non-aarch64 and no-alloc builds.
No security action required. Treat as a routine performance optimization. Reviewers may want to verify that `hash_64_many` produces byte-identical outputs to the existing `sha256d` engine for all 64-byte inputs, and that the duplicate-pair check correctly rejects malformed merkle trees before batch hashing.
Security signals we found
Preserves existing consecutive-duplicate detection that mitigates CVE-2012-2459
No removal of validation logic or change to consensus-critical result semantics
New code is cfg-gated and does not affect default x86 or no-alloc builds
Performance-only change using an existing optimized hashing primitive
Evidence from the diff
The patch adds calculate_root_batched() in primitives/src/merkle_tree.rs, gated behind #[cfg(feature = "std")] and #[cfg(target_arch = "aarch64")]. It collects leaf hashes into a Vec<[u8; 32]>, checks consecutive duplicate pairs (the same check that mitigates CVE-2012-2459), pads odd-length levels, builds 64-byte input blocks, and calls sha256d::Hash::hash_64_many() to compute all level hashes in one batch. The existing MerkleNode::calculate_root default implementation is overridden only for TxMerkleNode and WitnessMerkleNode on aarch64+std. The duplicate-pair mitigation is preserved, and no-alloc/non-aarch64 builds keep the original stack-based algorithm.
Changed components
primitives/src/merkle_tree.rsMerkleNode::calculate_root for TxMerkleNode and WitnessMerkleNode on aarch64 with std featureInspect captured patch +53 / −0
diff --git a/primitives/src/merkle_tree.rs b/primitives/src/merkle_tree.rs
index ee339aa1..2e061897 100644
--- a/primitives/src/merkle_tree.rs
+++ b/primitives/src/merkle_tree.rs
@@ -114,6 +114,45 @@ pub(crate) trait MerkleNode: Copy + PartialEq {
}
}
+#[cfg(feature = "std")]
+#[cfg(target_arch = "aarch64")]
+fn calculate_root_batched(mut nodes: Vec<[u8; 32]>) -> Option<[u8; 32]> {
+ if nodes.is_empty() {
+ return None;
+ }
+
+ while nodes.len() > 1 {
+ // check consecutive duplicates which would trigger CVE 2012-245
+ for pair in nodes.chunks_exact(2) {
+ if pair[0] == pair[1] {
+ return None;
+ }
+ }
+
+ // if odd count, duplicate last element
+ if nodes.len() % 2 != 0 {
+ let last = *nodes.last().expect("nodes is not emoty");
+ nodes.push(last);
+ }
+
+ let pair_count = nodes.len() / 2;
+ let inputs: Vec<[u8; 64]> = nodes
+ .chunks_exact(2)
+ .map(|pair| {
+ let mut block = [0u8; 64];
+ block[..32].copy_from_slice(&pair[0]);
+ block[32..].copy_from_slice(&pair[1]);
+ block
+ })
+ .collect();
+
+ let mut outputs = alloc::vec![[0u8; 32]; pair_count];
+ sha256d::Hash::hash_64_many(&mut outputs, &inputs);
+ nodes = outputs;
+ }
+
+ Some(nodes[0])
+}
// 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
@@ -128,6 +167,13 @@ impl MerkleNode for TxMerkleNode {
encoder.input(other.as_byte_array());
Self::from_byte_array(sha256d::Hash::from_engine(encoder).to_byte_array())
}
+
+ #[cfg(feature = "std")]
+ #[cfg(target_arch = "aarch64")]
+ fn calculate_root<I: Iterator<Item = Self::Leaf>>(iter: I) -> Option<Self> {
+ let nodes: Vec<[u8; 32]> = iter.map(Txid::to_byte_array).collect();
+ calculate_root_batched(nodes).map(Self::from_byte_array)
+ }
}
impl MerkleNode for WitnessMerkleNode {
type Leaf = Wtxid;
@@ -139,6 +185,13 @@ impl MerkleNode for WitnessMerkleNode {
encoder.input(other.as_byte_array());
Self::from_byte_array(sha256d::Hash::from_engine(encoder).to_byte_array())
}
+
+ #[cfg(feature = "std")]
+ #[cfg(target_arch = "aarch64")]
+ fn calculate_root<I: Iterator<Item = Self::Leaf>>(iter: I) -> Option<Self> {
+ let nodes: Vec<[u8; 32]> = iter.map(Wtxid::to_byte_array).collect();
+ calculate_root_batched(nodes).map(Self::from_byte_array)
+ }
}
#[cfg(test)]
Why this scored 17/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.