consensus: document merkle mutation root invariant #35161

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

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>

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

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.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/35161.

Reviews

See the guideline and AI policy for information on the review process.

Type	Reviewers
ACK	w0xlt
Concept ACK	hodlinator
Stale ACK	optout21

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

Conflicts

No conflicts as of last run.

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).

luke-jr referenced this in commit 38f3deb2e8 on May 3, 2026

l0rinc commented at 5:15 PM on May 3, 2026: contributor

that for optimal performance hashes should be reserved to an even size (https://github.com/bitcoin/bitcoin/pull/32497).

That's just an optimization, it would work without the preallocation as well

the two discarded historical minor optimization opportunities (https://github.com/bitcoin/bitcoin/pull/22046 & #28430; PR numbers without details).

Not sure, these docs were added to discourage tinkering with that part without a very good reason.

sedited commented at 7:23 PM on August 10, 2026: contributor

@w0xlt do you want to take another look here?

sedited requested review from hodlinator on Aug 10, 2026

in src/consensus/merkle.cpp:46 in f2dbc6a5fd

hodlinator commented at 8:33 AM on August 12, 2026:

nanonit: The above comment arguably applies to the entire file, but I think it would be preferable to have it adjacent to the core function implementing what it describes.

*/
uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {

hodlinator commented at 7:50 AM on August 13, 2026:

The commit message and PR description are quite verbose. Point 2 quoted in #28457 about getting a different merkle root value was stricken out in the original comment #28430 (comment) as it was based on a misunderstanding of the effects of the suggested change. So I don't think it's really something that needs to be called out. It's pretty axiomatic that a function should return correctly computed values, the added unit test should suffice. The main part I suggest should be removed/shortened is:

ComputeMerkleRoot reports duplicate-subtree mutations through an optional output flag that is always written when provided, but callers still rely on the return value being the Merkle root for the whole input.

I also think this comment in the .CPP is redundant:

// Mutation detection only affects the output flag; root computation
// must still reduce the full input.

And this one in the .H:

 * ... The returned root is always computed from the full input,
 * regardless of whether a mutation is detected.

It's worth documenting surprising behavior, but starting to bloat the codebase with too many redundant comments harms readability IMO. Especially when it's based on a retracted misunderstanding of a closed PR.

l0rinc commented at 6:30 PM on August 13, 2026:

Thanks, pushed

in src/test/merkle_tests.cpp:211 in f2dbc6a5fd

 206 | +    const std::vector leaves{uint256{1}, uint256{2}, uint256{3}, uint256{4}, uint256{5}, uint256{6}};
 207 | +    auto mutated_leaves{leaves};
 208 | +    mutated_leaves.insert(mutated_leaves.end(), leaves.end() - 2, leaves.end()); // repeat last two elements
 209 | +
 210 | +    bool mutated{true};
 211 | +    const auto unmutated_root{ComputeMerkleRoot(leaves, &mutated)};

hodlinator commented at 8:37 AM on August 12, 2026:

nanonit: Preference for calling out the type here:

    const uint256 unmutated_root{ComputeMerkleRoot(leaves, &mutated)};

in src/consensus/merkle.cpp:51 in f2dbc6a5fd

  46 | @@ -47,6 +47,8 @@ uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
  47 |      bool mutation = false;
  48 |      while (hashes.size() > 1) {
  49 |          if (mutated) {
  50 | +            // Mutation detection only affects the output flag.
  51 | +            // The root computation below must still reduce every tree level.

hodlinator commented at 8:44 AM on August 12, 2026:

Something like the following seems more helpful to me:

            // The mutation check needs to happen at every level, not just the
            // lowest one, as that would not catch for example [1,2,1,2].
            // We repeat the check without first checking if mutation has
            // already been detected since blocks with mutated transaction
            // lists should not propagate through the network anyway, and
            // blocks that are invalid in this way are not more expensive to
            // process than valid ones.

l0rinc commented at 9:50 PM on August 12, 2026:

Thanks, added something similar

hodlinator commented at 7:19 AM on August 13, 2026:

Thanks!

Don't you think that mutated blocks not propagating is also a factor in why it's not worth optimizing the mutation check by not repeating it if already detected? See point 1 in #28430 (comment).

l0rinc commented at 6:31 PM on August 13, 2026:

Added, thanks

hodlinator commented at 8:51 AM on August 12, 2026: contributor

Concept ACK f2dbc6a5fd582bb125c2a277362a7fe53ea7aa17

l0rinc force-pushed on Aug 12, 2026

DrahtBot added the label CI failed on Aug 12, 2026

DrahtBot removed the label CI failed on Aug 12, 2026

in src/test/merkle_tests.cpp:212 in 86e115927a

 207 | +    auto mutated_leaves{leaves};
 208 | +    mutated_leaves.insert(mutated_leaves.end(), leaves.end() - 2, leaves.end()); // repeat last two elements
 209 | +
 210 | +    bool mutated{true};
 211 | +    const uint256 unmutated_root{ComputeMerkleRoot(leaves, &mutated)};
 212 | +    BOOST_CHECK_EQUAL(mutated, false);

hodlinator commented at 7:40 AM on August 13, 2026:

Thanks for revealing the types!

nit: Comparing things to boolean literals to see if the boolean result value is true is too verbose in my book.

BOOST_CHECK_EQUAL(mutated, false):
../merkle_tests.cpp(220): error: in "merkle_tests/...": check mutated == false has failed [true != false]

BOOST_CHECK(!mutated):
../merkle_tests.cpp(220): error: in "merkle_tests/...": check !mutated has failed

[On parent master commit 625f951ba2fcd0b7c66de8bb30244b0b2fa63673]

₿ git grep -E "BOOST_CHECK_EQUAL\(\w+, (false|true)\);" | wc -l
59

₿ git grep -E "BOOST_CHECK\(" | wc -l
4087

l0rinc commented at 5:29 PM on August 13, 2026:

I usually do that when I have we have both true and false cases nearby (and the ! may not immediately be obvious, but that can also be clarified with a leading space). Or when I'm doing a characterization test so that the fix commit just changes true to false instead of adding a ! - but here it's not the case, so I'll revert, thanks.

hodlinator commented at 8:08 AM on August 13, 2026: contributor

Reviewed 86e115927a287dc326aa3a167f4b889191692197

w0xlt commented at 6:20 PM on August 13, 2026: contributor

ACK 86e115927a287dc326aa3a167f4b889191692197 The documentation matches the existing mutation and root-computation behavior.

DrahtBot requested review from optout21 on Aug 13, 2026

DrahtBot requested review from hodlinator on Aug 13, 2026

consensus: document merkle mutation root invariant

Document the `mutated` output flag on the `ComputeMerkleRoot` declaration and explain in the inner loop why the mutation check runs at every tree level even after a duplicate is found.
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 test also verifies that mutation detection checks equal pairs before the final pair of a tree level.

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

Co-authored-by: Hodlinator <172445034+hodlinator@users.noreply.github.com>

ef501a63d9

l0rinc force-pushed on Aug 13, 2026

l0rinc requested review from w0xlt on Aug 13, 2026

w0xlt commented at 6:35 PM on August 13, 2026: contributor

reACK ef501a63d9d65fce49bd633c424e0bbabead7ef6