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[0].begin(), hashes[0].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[0];
}

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[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();
    }
    return ComputeMerkleRoot(std::move(leaves), mutated);
}

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

Return to commented Bitcoin Core sources index.

Links

Investopedia; Merkle Root (Cryptocurrency)

Wikipedia: Merkle tree

Merkle Root

What is the Merkle root?

Merkle root of a bitcoin block calculated in C#