Merkle Trees

The paper detailing the mechanics of Bitcoin is a fascinating read. However, the technology involved requires several re-readings of the paper to make sense of what is going on.  I’ve been attacking the concepts piece by piece as time permits. In particular, the Bitcoin paper’s comments regarding the use of the Merkle Tree caught my eye. I had never encountered the concept of a Merkle Tree before in any applications I’d worked with, so I figured some investigation would be worthwhile.

Within Bitcoin, the Merkle Tree is a disk-space saving mechanism.   From the Bitcoin paper:

” Once the latest transaction in a coin is buried under enough blocks, the spent transactions before it can be discarded to save disk space. To facilitate this without breaking the block’s hash, transactions are hashed in a Merkle Tree […], with only the root included in the block’s hash. Old blocks can then be compacted by stubbing off branches of the tree. The interior hashes do not need to be stored.

I did some digging into the Merkle Tree and read some of the implementation code to understand it. I found that the Wikipedia page does a pretty good job summarizing the data structure:

“In cryptography and computer science a hash tree or Merkle tree is a tree in which every non-leaf node is labelled with the hash of the labels of its children nodes. Hash trees are useful because they allow efficient and secure verification of the contents of larger data structures. Hash trees are a generalisation of hash lists and hash chains. To demonstrate that a leaf node is part of a given hash tree requires an amount of data proportional to the log of the number of nodes of the tree. (This contrasts with hash lists, where the amount is proportional to the number of nodes.) The concept is named after Ralph Merkle.”

The bitcoin source code helps make some of the concepts clearer.  Within the code, the CBlockHeader shows a member variable ‘uint256 hashMerkleRoot’ that refers to the concept mentioned in the paper:

class CBlockHeader
{
public:
    // header
    static const int CURRENT_VERSION=2;
    int nVersion;
    uint256 hashPrevBlock;
    uint256 hashMerkleRoot;
    unsigned int nTime;
    unsigned int nBits;
    unsigned int nNonce;
    ...

And, as far as the actual construction of the Merkle Tree:

uint256 BuildMerkleTree() const
{
    vMerkleTree.clear();
    BOOST_FOREACH(const CTransaction& tx, vtx)
        vMerkleTree.push_back(tx.GetHash());
    int j = 0;
    for (int nSize = vtx.size(); nSize > 1; 
         nSize = (nSize + 1) / 2)
    {
        for (int i = 0; i < nSize; i += 2)
        {
            int i2 = std::min(i+1, nSize-1);
            vMerkleTree.push_back(
                Hash( BEGIN(vMerkleTree[j+i]),
                      END(vMerkleTree[j+i]),
                      BEGIN(vMerkleTree[j+i2]), 
                      END(vMerkleTree[j+i2])));
        }
        j += nSize;
    }
    return (vMerkleTree.empty() ? 0 : vMerkleTree.back());
}

The first thing to note is that the Hash() function mentioned in this code is actually a SHA256 double hash. (You can look into the code for yourself to validate this.)

The code appears to iterate over a vector of transactions and pushes their hashes into a vector representing the nodes of the Merkle tree. It then loops in such a manner that it appears to hash adjacent transaction hashes together (if an adjacent node is available — if one isn’t, the node is concatenated with itself). So if there are 3 transactions (nSize=3), [1, 2, 3]. The first pass of the outer loop, nSize = 3, you get an inner loop where there’s a hash of the hash computed over the hashes of element 1 and element 2 (we’ll call it dhash[1,2]), then a hash of the hash of element 3 concatenated with itself (dhash[3,3]). The variable j increments forward, so that on the next loop iteration, the double hash of dhash[1,2] and dhash[3,3] (both from the previous iteration) is computed, etc., etc. and the process continues until the tree gets built within a vector. The last node (vMerkelTree.back()) ends up being the root hash.

When I queried some people on various forums as to the necessity of the double hash as opposed to a single hash, they claimed it was desirable as a means of increasing the cost of calculation within the bitcoin framework.

Interesting, right? I hope to look more into the transaction mechanisms as I dig further into the system. Nevertheless, the exercise of going through the code to construct the Merkle Tree was educational and enlightening.