# Commented consensus/merkle.cpp Merkle root on Bitcoin Core Source Code

In this article we take a look at one of the most important components of block validation and overall blockchain integrity: the Merkle Root derivation process.

While it's one of the most critical components in all of Bitcoin Core, its concept and implementation are very simple and straightforward.

The `consensus/merkle.h` header consists solely of 3 declarations, so let's jump straight into `consensus/merkle.cpp` and see how these functions are implemented.

## `consensus/merkle.cpp`

At the top of merkle.cpp we find an interesting comment that's worth the read. I've taken a screenshot to preserve the formatting and the original tree drawings.

First function we encounter is the Merkle Root computation subroutine.

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

It takes a `hashes` vector containing the input hashes and returns a `uint256` digest for the merkle root. The purpose of the `mutated` argument is explained in the vulnerability screenshot posted above: if this tree is ambiguous and can generate a collision then set `*mutated` to true to let the caller know.

I'll comment the `ComputeMerkleRoot` from within the code itself. As always, my comments begin with >, original comments begin with // or /*

``````> Note that a null mutated pointer will ignore mutated check.
uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
> Assume no mutation. Tree collisions are the exception not the rule.
bool mutation = false;
> When we reach the end of computation, hashes should've been reduced
> to a single hash containing the Merkle Root.
while (hashes.size() > 1) {
> Check that the mutated pointer is not null
if (mutated) {
> For every hash still in hashes, if this hash collides with the next
> then set mutation to true. This loop repeats with every iteration of
> the while loop so it checks the tree as it is compiled to the root.
for (size_t pos = 0; pos + 1 < hashes.size(); pos += 2) {
if (hashes[pos] == hashes[pos + 1]) mutation = true;
}
}
> If the size of hashes is odd then push the current hash into the back.
> In the Merkle root algorithm when a leaf is dangling by itself then
> it is hashed against itself. Thus the last leaf is pushed back here to
> generate a tree with an even number of leaves.
if (hashes.size() & 1) {
hashes.push_back(hashes.back());
}
> Call SHA256D64 from crypto/sha256.cpp passing it a pointer for output,
> a pointer for input and the size of the input.
SHA256D64(hashes.begin(), hashes.begin(), hashes.size() / 2);
> Once SHA256D64 is done we have digested half the tree so we reduce the size
> by 2.
hashes.resize(hashes.size() / 2);
}
> Copy the value of local variable mutation to *mutated parameter.
if (mutated) *mutated = mutation;
> If nothing was processed, return an empty uint256 blob
if (hashes.size() == 0) return uint256();
> Otherwise return the single value contained in hashes.
return hashes;
}``````

Now we have a utility function that allows us to pass in a block to compute its Merkle root.

``````uint256 BlockMerkleRoot(const CBlock& block, bool* mutated)
{
std::vector<uint256> leaves;
leaves.resize(block.vtx.size());
for (size_t s = 0; s < block.vtx.size(); s++) {
leaves[s] = block.vtx[s]->GetHash();
}
return ComputeMerkleRoot(std::move(leaves), mutated);
}``````

It declares a `leaves` `std::vector`, resizes `leaves` to the size of the block's number of transactions and copies each TX into `leaves`. Then it calls `ComputeMerkleRoot` to compute the Merkle root on the just assembled vector.

Next up, another utility function to compute the Merkle root of the transaction witness hashes.

``````uint256 BlockWitnessMerkleRoot(const CBlock& block, bool* mutated)
{
std::vector<uint256> leaves;
leaves.resize(block.vtx.size());
leaves.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();
}
return ComputeMerkleRoot(std::move(leaves), mutated);
}``````

It works exactly the same way as `BlockMerkleRoot` except it calls `GetWitnessHash` instead of `GetHash` on each transaction.

Investopedia; Merkle Root (Cryptocurrency)

Wikipedia: Merkle tree

Merkle Root

What is the Merkle root?

Merkle root of a bitcoin block calculated in C#

Help sponsor us by donating to 🔺 `X-avax1n7j2g4arl76l8p0tefdu0w36kcue4v5fr44yfg` 🔺