Skip to content

merkle: migrate path arg to reference and drop unused args #33805

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
achow101 merged 3 commits into from
Dec 10, 2025
Merged

merkle: migrate path arg to reference and drop unused args #33805

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
be27055
merkle: migrate `path` arg of `MerkleComputation` to a reference
l0rinc Nov 5, 2025
63d640f
merkle: remove unused `proot` and `pmutated` args from `MerkleComputa…
l0rinc Nov 5, 2025
24ed820
merkle: remove unused `mutated` arg from `BlockWitnessMerkleRoot`
l0rinc Nov 6, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
47 changes: 18 additions & 29 deletions src/consensus/merkle.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -73,28 +73,25 @@ uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
return ComputeMerkleRoot(std::move(leaves), mutated);
}

uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated)
uint256 BlockWitnessMerkleRoot(const CBlock& block)
{
std::vector<uint256> leaves;
leaves.resize(block.vtx.size());
leaves[0].SetNull(); // The witness hash of the coinbase is 0.
for (size_t s = 1; s < block.vtx.size(); s++) {
leaves[s] = block.vtx[s]->GetWitnessHash().ToUint256();
}
return ComputeMerkleRoot(std::move(leaves), mutated);
return ComputeMerkleRoot(std::move(leaves));
}

/* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */
static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t leaf_pos, std::vector<uint256>* path)
/* This implements a constant-space merkle path calculator, limited to 2^32 leaves. */
static void MerkleComputation(const std::vector<uint256>& leaves, uint32_t leaf_pos, std::vector<uint256>& path)
Comment thread
l0rinc marked this conversation as resolved.
{
if (path) path->clear();
path.clear();
Assume(leaves.size() <= UINT32_MAX);
if (leaves.size() == 0) {
if (pmutated) *pmutated = false;
if (proot) *proot = uint256();
return;
}
bool mutated = false;
// count is the number of leaves processed so far.
uint32_t count = 0;
// inner is an array of eagerly computed subtree hashes, indexed by tree
Expand All @@ -115,15 +112,12 @@ static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot
// corresponds to an inner value that existed before processing the
// current leaf, and each needs a hash to combine it.
for (level = 0; !(count & ((uint32_t{1}) << level)); level++) {
if (path) {
if (matchh) {
path->push_back(inner[level]);
} else if (matchlevel == level) {
path->push_back(h);
matchh = true;
}
if (matchh) {
path.push_back(inner[level]);
} else if (matchlevel == level) {
path.push_back(h);
matchh = true;
}
mutated |= (inner[level] == h);
Comment thread
l0rinc marked this conversation as resolved.
h = Hash(inner[level], h);
}
// Store the resulting hash at inner position level.
Expand All @@ -147,8 +141,8 @@ static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot
// If we reach this point, h is an inner value that is not the top.
// We combine it with itself (Bitcoin's special rule for odd levels in
// the tree) to produce a higher level one.
if (path && matchh) {
path->push_back(h);
if (matchh) {
path.push_back(h);
}
h = Hash(h, h);
// Increment count to the value it would have if two entries at this
Expand All @@ -157,26 +151,21 @@ static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot
level++;
// And propagate the result upwards accordingly.
while (!(count & ((uint32_t{1}) << level))) {
if (path) {
if (matchh) {
path->push_back(inner[level]);
} else if (matchlevel == level) {
path->push_back(h);
matchh = true;
}
if (matchh) {
path.push_back(inner[level]);
} else if (matchlevel == level) {
path.push_back(h);
matchh = true;
}
h = Hash(inner[level], h);
level++;
}
}
// Return result.
if (pmutated) *pmutated = mutated;
if (proot) *proot = h;
}

static std::vector<uint256> ComputeMerklePath(const std::vector<uint256>& leaves, uint32_t position) {
std::vector<uint256> ret;
MerkleComputation(leaves, nullptr, nullptr, position, &ret);
MerkleComputation(leaves, position, ret);
return ret;
}

Expand Down
3 changes: 1 addition & 2 deletions src/consensus/merkle.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -20,9 +20,8 @@ uint256 BlockMerkleRoot(const CBlock& block, bool* mutated = nullptr);

/*
* Compute the Merkle root of the witness transactions in a block.
* *mutated is set to true if a duplicated subtree was found.
*/
uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated = nullptr);
uint256 BlockWitnessMerkleRoot(const CBlock& block);

/**
* Compute merkle path to the specified transaction
Expand Down
4 changes: 2 additions & 2 deletions src/test/fuzz/merkle.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -51,7 +51,7 @@ FUZZ_TARGET(merkle)
}

// Test ComputeMerkleRoot
bool mutated = fuzzed_data_provider.ConsumeBool();
bool mutated = fuzzed_data_provider.ConsumeBool(); // output param, initial value shouldn't matter
Comment thread
l0rinc marked this conversation as resolved.

@sedited sedited Dec 4, 2025

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Do you think there would be value in also passing in nullptr:

diff --git a/src/test/fuzz/merkle.cpp b/src/test/fuzz/merkle.cpp
index 4bb91faf0b..5b91a97b75 100644
--- a/src/test/fuzz/merkle.cpp
+++ b/src/test/fuzz/merkle.cpp
@@ -55 +55,2 @@ FUZZ_TARGET(merkle)
-    const uint256 merkle_root = ComputeMerkleRoot(tx_hashes, &mutated);
+    bool* pmutated = fuzzed_data_provider.PickValueInArray({&mutated, static_cast<bool*>(nullptr)});
+    const uint256 merkle_root = ComputeMerkleRoot(tx_hashes, pmutated);

@l0rinc l0rinc Dec 5, 2025

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes, we should do that in a follow-up, thanks

@l0rinc l0rinc Dec 11, 2025

Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks, added in #34050

const uint256 merkle_root = ComputeMerkleRoot(tx_hashes, &mutated);

// Basic sanity checks for ComputeMerkleRoot
Expand All @@ -66,7 +66,7 @@ FUZZ_TARGET(merkle)
}

if (!block->vtx.empty()){
const uint256 block_witness_merkle_root = BlockWitnessMerkleRoot(*block, &mutated);
const uint256 block_witness_merkle_root = BlockWitnessMerkleRoot(*block);
if (tx_hashes.size() == 1) {
assert(block_witness_merkle_root == uint256());
}
Expand Down
4 changes: 2 additions & 2 deletions src/validation.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -3996,7 +3996,7 @@ static bool CheckWitnessMalleation(const CBlock& block, bool expect_witness_comm
// The malleation check is ignored; as the transaction tree itself
// already does not permit it, it is impossible to trigger in the
// witness tree.
uint256 hash_witness = BlockWitnessMerkleRoot(block, /*mutated=*/nullptr);
uint256 hash_witness = BlockWitnessMerkleRoot(block);

CHash256().Write(hash_witness).Write(witness_stack[0]).Finalize(hash_witness);
if (memcmp(hash_witness.begin(), &block.vtx[0]->vout[commitpos].scriptPubKey[6], 32)) {
Expand Down Expand Up @@ -4109,7 +4109,7 @@ std::vector<unsigned char> ChainstateManager::GenerateCoinbaseCommitment(CBlock&
int commitpos = GetWitnessCommitmentIndex(block);
std::vector<unsigned char> ret(32, 0x00);
if (commitpos == NO_WITNESS_COMMITMENT) {
uint256 witnessroot = BlockWitnessMerkleRoot(block, nullptr);
uint256 witnessroot = BlockWitnessMerkleRoot(block);
CHash256().Write(witnessroot).Write(ret).Finalize(witnessroot);
CTxOut out;
out.nValue = 0;
Expand Down
Loading