Merge bitcoin/bitcoin#35161: consensus: document merkle mutation root invariant
What the developer wrote
Authored by Ava Chow
Merge bitcoin/bitcoin#35161: consensus: document merkle mutation root invariant
ef501a63d9d65fce49bd633c424e0bbabead7ef6 consensus: document merkle mutation root invariant (Lőrinc)
Pull request description:
**Problem:** `ComputeMerkleRoot`'s optional mutation flag and the reasoning behind its per-level check are undocumented, and the behavior is only exercised indirectly by merkle_test through random duplications and old-vs-new comparisons, so a refactor could silently change it, as the discussions in #22046 and #28430 illustrate.
**Fix:** Document the flag on the function declaration, explain inside the inner loop why the mutation check runs at every tree level even after a duplicate is found, and add direct API coverage for the CVE-2012-2459 construction.
**Coverage check:** Both `merkle_test` and the new `merkle_test_mutated_return_value` would fail under a refactor that stops the outer reduction once mutation is detected, e.g.:
<details><summary>Hypothetical regression</summary>
```patch
diff --git a/src/consensus/merkle.cpp b/src/consensus/merkle.cpp
index dfa23cf897..40bc3f8efa 100644
--- a/src/consensus/merkle.cpp
+++ b/src/consensus/merkle.cpp
@@ -59,6 +59,7 @@ uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
if (hashes[pos] == hashes[pos + 1]) mutation = true;
}
}
+ if (mutation) break;
if (hashes.size() & 1) {
hashes.push_back(hashes.back());
}
```
</details>
Fixes #28457
ACKs for top commit:
optout21:
reACK ef501a63d9d65fce49bd633c424e0bbabead7ef6
achow101:
ACK ef501a63d9d65fce49bd633c424e0bbabead7ef6
w0xlt:
reACK ef501a63d9d65fce49bd633c424e0bbabead7ef6
hodlinator:
ACK ef501a63d9d65fce49bd633c424e0bbabead7ef6
Tree-SHA512: 5a54eed071079a0a37333d5ba7c2d8eb81ae318ee4c84e15e3c050198daea6282453d4f7727b75f7dab90696b3d9bc946b8b33e6456a7f190b2297c15aca390c
What changed, and why it matters
This commit only adds documentation comments and a new unit test for an existing Bitcoin consensus function. It does not change any behavior of the code that runs on the network, so it cannot introduce or fix a live security vulnerability by itself. It is a defensive maintenance change meant to prevent future developers from accidentally breaking a known anti-attack check.
No security response needed. Treat as normal code-review/merge maintenance. The change improves test coverage and documentation for an already-implemented CVE-2012-2459 mitigation.
Security signals we found
References CVE-2012-2459 in a newly added regression test
Documents an existing consensus-level mutation-detection invariant
Adds test coverage to detect a hypothetical future refactor that would stop scanning for duplicate pairs after the first match
Evidence from the diff
The patch documents the mutated output parameter of ComputeMerkleRoot in src/consensus/merkle.h, adds an inline comment in src/consensus/merkle.cpp explaining why duplicate-pair detection is performed at every Merkle tree level, and adds a new Boost test case (merkle_test_mutated_return_value) that directly exercises the CVE-2012-2459 duplicate-leaf construction. No logic in ComputeMerkleRoot is changed; the diff is purely comments and tests.
Changed components
src/consensus/merkle.cppsrc/consensus/merkle.hsrc/test/merkle_tests.cppInspect captured patch +30 / −2
### src/consensus/merkle.cpp
@@ -49,12 +49,15 @@
known ways of changing the transactions without affecting the merkle
root.
*/
-
-
uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
bool mutation = false;
while (hashes.size() > 1) {
if (mutated) {
+ // Check every level because equal pairs can appear above the leaves,
+ // as in the [1,2,3,4,5,6,5,6] construction described above.
+ // Continuing after finding one is redundant, but mutated blocks should
+ // not propagate through the network anyway, and the total number of
+ // comparisons is the same as for an unmutated input of the same length.
for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
if (hashes[pos] == hashes[pos + 1]) mutation = true;
}
### src/consensus/merkle.h
@@ -12,6 +12,11 @@
class CBlock;
+/**
+ * Compute a Merkle root from the provided leaf hashes.
+ * If non-null, `*mutated` is set to true if two identical hashes are paired at
+ * any tree level before the odd-count hash duplication step, and false otherwise.
+ */
uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated = nullptr);
/*
### src/test/merkle_tests.cpp
@@ -200,6 +200,26 @@ BOOST_AUTO_TEST_CASE(merkle_test_OddTxWithRepeatedLastTx_block)
BOOST_CHECK_EQUAL(mutated, true);
}
+BOOST_AUTO_TEST_CASE(merkle_test_mutated_return_value)
+{
+ // CVE-2012-2459 construction: [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] produce the same root.
+ const std::vector leaves{uint256{1}, uint256{2}, uint256{3}, uint256{4}, uint256{5}, uint256{6}};
+ auto mutated_leaves{leaves};
+ mutated_leaves.insert(mutated_leaves.end(), leaves.end() - 2, leaves.end()); // repeat last two elements
+
+ bool mutated{true};
+ const uint256 unmutated_root{ComputeMerkleRoot(leaves, &mutated)};
+ BOOST_CHECK(!mutated);
+ BOOST_CHECK_EQUAL(unmutated_root, ComputeMerkleRoot(mutated_leaves, &mutated));
+ BOOST_CHECK( mutated);
+
+ const std::vector nontrailing_duplicate_leaves{uint256{1}, uint256{1}, uint256{3}, uint256{4}};
+ mutated = false;
+ const uint256 nontrailing_duplicate_root{ComputeMerkleRoot(nontrailing_duplicate_leaves, &mutated)};
+ BOOST_CHECK(nontrailing_duplicate_root == ComputeMerkleRoot(nontrailing_duplicate_leaves));
+ BOOST_CHECK(mutated);
+}
+
BOOST_AUTO_TEST_CASE(merkle_test_LeftSubtreeRightSubtree)
{
CBlock block, leftSubtreeBlock, rightSubtreeBlock;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.