consensus: document merkle mutation root invariant #35161

pull l0rinc wants to merge 1 commits into bitcoin:master from l0rinc:l0rinc/doc-merkle-root-mutated changing 3 files +22 −0

l0rinc commented at 6:26 PM on April 26, 2026: contributor
Problem

ComputeMerkleRoot has a subtle two-output contract: an optional mutation flag and a return value that callers expect to always equal the Merkle root of the full input (regardless of mutations). That contract is currently undocumented and only exercised indirectly by merkle_test (random duplications, old-vs-new comparison), so a refactor could silently break it - as the discussion under #22046/#28430 illustrates.

Fix

Document the contract on the function declaration and inside the inner loop, and add a direct regression test for the duplicate-subtree construction described in the code comments for CVE-2012-2459: https://github.com/bitcoin/bitcoin/blob/8faf7b6cdc0c93ddf542d20d9ad0afb3579d47eb/src/consensus/merkle.cpp#L20-L29

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>
```
diff --git a/src/consensus/merkle.cpp b/src/consensus/merkle.cpp
--- a/src/consensus/merkle.cpp
+++ b/src/consensus/merkle.cpp
@@ -53,6 +53,7 @@
                 if (hashes[pos] == hashes[pos + 1]) mutation = true;
             }
         }
+        if (mutation) break;
         if (hashes.size() & 1) {
             hashes.push_back(hashes.back());
         }
```
</details>

Fixes #28457
DrahtBot added the label Consensus on Apr 26, 2026
DrahtBot commented at 6:27 PM on April 26, 2026: contributor



The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.



Reviews

See the guideline for information on the review process.

Type Reviewers

ACK optout21

Concept ACK w0xlt

If your review is incorrectly listed, please copy-paste <code></code> into the comment that the bot should ignore.

Type	Reviewers
ACK	optout21
Concept ACK	w0xlt

consensus: document merkle mutation root invariant

`ComputeMerkleRoot` reports duplicate-subtree mutations through its optional output flag, but callers still rely on the return value being the Merkle root for the whole input.

Document that contract on the function declaration and inside the inner loop, and add a direct regression test for the duplicate-subtree construction described in the code comments for CVE-2012-2459: `[1,2,3,4,5,6]` and `[1,2,3,4,5,6,5,6]` produce the same root.

The existing `merkle_test` already exercises this invariant indirectly through random duplications and old-vs-new comparisons; the new test pins it down explicitly at the `ComputeMerkleRoot` API boundary. Both would fail under a refactor that stops the outer reduction once mutation is detected, e.g.:

```diff
diff --git a/src/consensus/merkle.cpp b/src/consensus/merkle.cpp
--- a/src/consensus/merkle.cpp
+++ b/src/consensus/merkle.cpp
@@ -53,6 +53,7 @@
                 if (hashes[pos] == hashes[pos + 1]) mutation = true;
             }
         }
+        if (mutation) break;
         if (hashes.size() & 1) {
             hashes.push_back(hashes.back());
         }
```

f2dbc6a5fd

l0rinc force-pushed on Apr 26, 2026
DrahtBot added the label CI failed on Apr 26, 2026
DrahtBot commented at 7:14 PM on April 26, 2026: contributor


🚧 At least one of the CI tasks failed. <sub>Task tidy: https://github.com/bitcoin/bitcoin/actions/runs/24963858314/job/73095124395</sub> <sub>LLM reason (✨ experimental): CI failed because clang-tidy reported a bugprone-use-after-move error (moved mutated_leaves then used) in test/merkle_tests.cpp, treated as warnings-as-errors.</sub>

<details><summary>Hints</summary>

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:
- Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
- A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
- An intermittent issue.
Leave a comment here, if you need help tracking down a confusing failure.

</details>
DrahtBot removed the label CI failed on Apr 26, 2026
optout21 commented at 1:47 PM on April 30, 2026: contributor

Concept ACK f2dbc6a5fd582bb125c2a277362a7fe53ea7aa17

Comments added to the ComputeMerkleRoot method, and a new test case with one corner-case test added.
w0xlt commented at 6:28 PM on April 30, 2026: contributor

Concept ACK
optout21 commented at 10:02 PM on April 30, 2026: contributor
ACK f2dbc6a5fd582bb125c2a277362a7fe53ea7aa17

The change documents the method ComputeMerkleRoot, including a CVE-relevant corner case. No behavior change, only comments and test code is affected.

Since ComputeMerkleRoot is being documented here, I would suggest to also include:
- that for optimal performance hashes should be reserved to an even size (#32497).
- the two discarded historical minor optimization opportunities (#22046 & #28430; PR numbers without details).

Contributors

Labels

Linked (view graph)

#22046 consensus: remove redundant checks in merkle root computation #28430 fix: unnecessary continuation after finding mutation #28457 consensus: Better document ComputeMerkleRoot & add test for return value

consensus: document merkle mutation root invariant #35161

Problem

Fix

Coverage check

Reviews