Bitcoin Merkle Roots

tl;dr C++ code for this is on GitHub (｀・ω・´)”

When exploring on-chain transactions for Bitcoin, you may discover that each BTC block header has a field called Merkle root. What exactly this value means and how it is derived will be explored in this article. I am going to explain step-by-step exactly how the Merkle tree of any Bitcoin block is constructed; sample C++ code is provided to make these concepts more concrete.

Let's dive in!

Merkle Roots & Merkle Trees in General

A Merkle tree is constructed from an ordered set of leaves. The parent nodes of these leaves are constructed from some hash of their children. For this reason Merkle trees are also sometimes referred to as hash trees outside the context of blockchain / cryptocurrency.

The top-most node (root) of this tree is called the Merkle root. Because the data of any node in the tree is derived only from its children, it can be shown that a Merkle tree constructed using a perfect hash is unique to the ordered set of leaves which seed the tree.

The Merkle Roots and Trees of Bitcoin

In Bitcoin the Merkle tree is seeded by an ordered list of transaction hashes in a block. A miner creating a Bitcoin block is free to arrange these transactions in any desired order to derive the Merkle root, with the exception that any transaction spending a UTXO generated by another transaction in the same block must come after the generative transaction. This ensures that if traversing the set of transactions in order UTXOs are not consumed before they are produced.

During construction of the Merkle tree, the hashes of each transaction are ordered as above and grouped together in pairs of two. The hash of the second transaction of a pair is then concatenated to the end of the first transaction hash and the resultant data is hashed again to create the data stored in their parent node. This process is repeated for each pair to create the nodes in the next depth of the Merkle tree until there is only one pair to hash. Their parent is the Merkle root and is the ancestor of all nodes in the tree.

Color-mixing example of a binary Merkle tree
Notice the content of each parent node is a function of its children

For many things in Bitcoin, Merkle tree computations included, Satoshi decided to use two rounds of SHA-256. This mostly mitigates length-extension attacks which could be leveraged to exploit aspects of the blockchain where messages are concatenated and hashed together such as during construction of the Merkle tree.

Bitcoin's Simple Payment Verification

The main reason for including a Merkle root in the block header is outlined in Chapter 8 ("Simplified Payment Verification") of the Bitcoin whitepaper. Satoshi describes how this approach allows light-clients to verify that a given transaction occurred in a block by challenging a full-node to provide a Merkle proof of that transaction within the block. If the proof provided by the full-node results in a Merkle root matching the root stored by the light-client then the light-client can be sure the transaction occurred in that block.

The important bit is: the light-client does not need to know the transactions in a block, it only needs to know the Merkle root; this enables the client to only store a chain of block headers, not the blocks themselves. The Merkle proof likewise does not need to have all transactions as leaves, it may include some of the intermediate values (i.e. ancestor nodes derived from the leaves) and the proof would still be viable to use as validation on this transaction.

For blocks with many transactions this saves considerable space on a light-client while still maintaining the integrity of transaction validation on the blockchain.

An Simple Bitcoin Merkle Tree in C++

Now that we've explored Merkle trees in both the general case and the Bitcoin case let's look at some C++ code snippets which put this all together.

This code is written by me and is hosted on GitHub. Feel free to use any part of it you'd like for your own projects or learning experience.

Below is a class representing the entire Merkle tree:

/*
 * https://github.com/wesl-ee/btc-merkle-tree/blob/master/include/MerkleTree.h
 */
#include <iostream>
#include <string>
#include <vector>
#include "MerkleNode.h"

/**
 * Collection of nodes at a given depth in a Merkle tree
 */
typedef std::vector<MerkleNode> MerkleTreeLevel;

/**
 * A full Merkle tree calculated from transactions in one BTC block
 */
class MerkleTree {
public:

    /**
    * Construct a Merkle tree given some set of network-order (big endian) hex
    * strings. BTC transactions are conveniently network-order already.
    * Changing the order of transactions will change the Merkle root!
    */
    void FromNetworkOrderHexSeeds(const std::vector<std::string> leaves);

    /**
    * Recursively walk a (sub)tree to calculate the Merkle root of the current
    * node
    */
    void CalculateSubtree(MerkleNode*);

    /**
    * Summarize the entire tree
    */
    void Print();

    /*
    * Summarize a subtree whose root is the first argument
    */
    void PrintSubtree(MerkleNode* root, unsigned int depth);

private:

    /*
    * Organize nodes by their depth
    */
    std::vector<MerkleTreeLevel> treeLevels;

    /**
    * The Merkle root is the top-most node of the Merkle tree
    */
    MerkleNode *merkleRoot;

    /**
    * Leaves from which the Merkle tree will be constructed
    */
    std::vector<MerkleNode> leafNodes;

    /**
    * Build the rest of the tree once leaves are loaded in
    */
    void construct();
};

Notice the attention to network-order (big endian) data. The canonical representations of BTC transaction hashes are network-order hex strings so special care must be taken within the hashing function to reverse the byte order, otherwise it would be inconsistent with BTC implementation.

I will not break out every method but the most interesting here are CalculateSubtree and construct:

/*
 * https://github.com/wesl-ee/btc-merkle-tree/blob/master/src/MerkleTree.cc
 */
void MerkleTree::CalculateSubtree(MerkleNode *node) {
    if (node->Left() == nullptr)
        return;

    CalculateSubtree(node->Left());
    CalculateSubtree(node->Right());

    node->CalculateFromChildren();
}

Here we can see a clearly recursive pattern which calculates the content of the current node from the content of its children, just as I've explained in the algorithm for construction of the Merkle tree above. First the left child-subtree is calculated, then the right child-subtree. With the contents of the child nodes now known we can calculate the contents of their parent.

This recursive walk is kicked off by CalculateSubtree(merkleRoot) after the tree has been seeded with the leaves in the below method:

/*
 * https://github.com/wesl-ee/btc-merkle-tree/blob/master/src/MerkleTree.cc
 */
void MerkleTree::construct() {
    merkleRoot = nullptr;

    /* Seed the tree's bottom level with leaves */
    treeLevels = std::vector<MerkleTreeLevel>();
    treeLevels.push_back(leafNodes);

    MerkleNode *left, *right;
    for (auto currLevel = &treeLevels.at(0); currLevel->size() > 1; ) {
        bool oddLevel = false;
        MerkleTreeLevel nextLevel;
        /* Construct parent nodes until we reach root */
        auto it = currLevel->begin();
        while (!(it == currLevel->end() || oddLevel)) {
            /* Consider a pair of adjacent nodes */
            left = &(*it++);
            right = &(*it++);

            /* ...give them a parent */
            nextLevel.push_back(MerkleNode());
            MerkleNode *parent = &nextLevel.back();

            /* Pair left element with itself if otherwise unpaired */
            if (right == &(*currLevel->end())) {
                oddLevel = true;
                right = left;
            }

            /* Parent these adjacent nodes to a node in the above level */
            parent->MakeParentOf(left, right);
        }

        /* Finalize this level of the tree and start on next one */
        treeLevels.push_back(nextLevel);
        currLevel = &treeLevels.back();
    }

    /* The top-most element will always be the merkle root */
    merkleRoot = &treeLevels.back().back();

    /* Calculate the hash of the merkle root recursively */
    CalculateSubtree(merkleRoot);
}

If you're familiar with modern C++ you'll notice the move / copy semantics I use to fill out the tree with empty nodes, beginning with the parents of leaf-pairs and continuing up to the allocation of the root node.

Note that in the case of an odd number of leaves at a given depth the last leaf is doubled up, making the node its own sibling. This mirrors the Bitcoin implementation of Merkle trees. At the end of this method we see the call to CalculateSubtree using the Merkle root as the entry-point for the tree traversal.

Next we look at the representation of individual nodes within the tree.

/*
 * https://github.com/wesl-ee/btc-merkle-tree/blob/master/include/MerkleNode.h
 */
#include <string>
#include <vector>
#include <iostream>
#include "NodeHash.h"

/**
 * A single node in a Merkle tree at any depth
 */
class MerkleNode {
    public:

    /**
    * Create an empty node
    */
    MerkleNode();

    /**
    * Create a leaf with a pre-computed hash in hex representation
    */
    MerkleNode(const std::string hex);

    /**
    * Assign this node as the parent of the left and right nodes
    */
    void MakeParentOf(MerkleNode *left, MerkleNode *right);

    /**
    * Textual representation of node's binary content
    */
    std::string Content();

    /**
    * Given the left and right child, compute this node's binary content
    */
    void CalculateFromChildren();

    /**
    * Left child
    */
    MerkleNode *Left();

    /**
    * Right child
    */
    MerkleNode *Right();

    /**
    * Raw binary content of node
    */
    std::vector<std::byte> RawDigest();

    /**
    * Parent this node to a given parent
    */
    void SetParent(MerkleNode *p);

    /**
    * Indicate that this node's content is represented in network (big endian)
    * order
    */
    void SetNetworkOrder(bool);

    private:

    /**
    * Binary content of node
    */
    NodeHash hash;

    /**
    * Left child
    */
    MerkleNode *left;

    /**
    * Right child
    */
    MerkleNode *right;

    /**
    * Parented node
    */
    MerkleNode *parent;
};

Nothing special here! Just context for the tree construction （‐＾▽＾‐） Many of the methods I expose as public are for positioning the node within the tree and relative to other nodes. Calls to SetParent and MakeParentOf essentially define the structure of the binary tree.

Unrelated, but the std::byte bits are interesting if only for their language semantics. I have seen many libraries use std::string as a container for binary data but with new projects I tend to use C++17 idioms when they are available, and std::byte has the most meaning here for the binary data at the node.

Example Output

To illustrate that this produces the correct root of an actual BTC block, I'll run this algorithm over TX hashes of an actual block. I arbitrarily choose Block 82747 which has six transactions. Notice this will result in a Merkle tree with 6 nodes at depth 3, 3 nodes at depth 2, 2 nodes at depth 1 and finally the Merkle root at depth 0.

You can find this in include/main.h:

/**
 * https://www.blockchain.com/btc/block/82747
 *
 * Merkle root
 * 5dc7e96501429df25873a43ad70bd8d9dedf2a432e330236eff600dcebcbdd03
 */
const static std::vector<std::string> TX_IDS = {
        "a0ee4c9066af0916e110391c7c7b33a4513de8cb94c304e305704aa4c9d11947",
        "10cf9efc4356ddc616a8cf5628ee8a3564e37a9cd9f4c7d103a88c15ddf6d2c0",
        "fdf09e486960fb4b649f9838c6bf076d321abae1a8d16795605edc70dfbafc3a",
        "ce7c126f69752425d638451c455b6dab2304004659bc4742139013abc415be53",
        "df56fe9d32474bfbb94d8e6c6d8a83739bbfbe6e6f017e642f40f2cadb1a203c",
        "501ff48af15c99c75334c0416bba672ffa3644789985ad5574a388547f3d9d9b"
};

Finally we can validate that this Merkle root is calculated correctly!

w@kvm-gentoo ~/.../btc-merkle-tree/build $ ./btc-merkle-tree 
+ 5DC7E96501429DF25873A43AD70BD8D9DEDF2A432E330236EFF600DCEBCBDD03
  + 619A9B4C9EC88DDA0CE1935F36237EB1EA16E385EC677FD07FF0ABFF1CF7E526
    + 7A8C6C24FB62EF804DC2F93C6354A024833DC692AC3F5AAE4D99D01FDE7AE9BC
      + A0EE4C9066AF0916E110391C7C7B33A4513DE8CB94C304E305704AA4C9D11947
      + 10CF9EFC4356DDC616A8CF5628EE8A3564E37A9CD9F4C7D103A88C15DDF6D2C0
    + 2D8D9B1EA781FE24A7A8FE00B8C8679DBD07837BF3BD41D867AF4232DEECADF9
      + FDF09E486960FB4B649F9838C6BF076D321ABAE1A8D16795605EDC70DFBAFC3A
      + CE7C126F69752425D638451C455B6DAB2304004659BC4742139013ABC415BE53
  + 35B6DB9685CE99667ADC37EBDF9E625F80511477947F0539D04F1384295C3312
    + 01EB546D12B8EB2F3DEA5276B1970C86E4740E15FEEE1D7879564E399C1D0B2B
      + DF56FE9D32474BFBB94D8E6C6D8A83739BBFBE6E6F017E642F40F2CADB1A203C
      + 501FF48AF15C99C75334C0416BBA672FFA3644789985AD5574A388547F3D9D9B

See how the first value is the Merkle root included in the header of block 82747... how neat! All other values are intermediate and help visualize the body of the Merkle tree; each level of indentation represents a distinct tree depth.

I hope to keep exploring concepts like this in the future, especially as I investigate and play with the nuanced bits of consensus networks. This is really just the tip of the iceberg when it comes to the data structures used in many modern networks but I am glad I've researched and implemented this one in-depth.