Merkle Trees, Simple Yet Powerful

Verify.as
verifyas
Published in
4 min readOct 11, 2017

This is the third in a series of posts where we discuss the core concepts behind the Blockchain, Bitcoin and Ethereum. At Verify, we’re building a reputation protocol on the Ethereum blockchain and are sharing these posts in an effort to share our knowledge with the wider crypto community.

In the previous post we talked about mining, introduced the block in bitcoins and we divided it to the header and the body. In the header we listed

- a timestamp
- a nonce
- a hash reference to a previous block
- hashed list of all transactions that took place since the last created block.

We talked about each one of them, but we left out “hashed list of all transactions that took place since the last created block”. In this post we are going to talk about that.

By now, we know that the blockchain in the bitcoin network is a chain of blocks. What we did not mention is that it is stored in a “multi-level data structure”. Now you know.

The transactions in the blocks are not stored as plain text. Rather, they are stored in a tree structure called the merkle tree. The merkle tree is a type of a binary tree, where the bottom of the tree contains the transactions (hashed), the intermediate tree nodes (leafs) contain the hash of the two nodes that made it, all the way till the top where it is a single hashed tree-node called the root hash.

Let us try to visualize this:

There are 6 transactions at the base/bottom of the tree; each two hashed transactions are combined together to create another hash (leaf). For example transaction A (txA) with transaction B (txB) both create the hash HAB. Note here that I deliberately used 6 transactions, knowing that it would result in an odd number of leafs. The second level has 3 tree-nodes (leafs), so how will a merkle tree handle this? Given that it is a binary tree, meaning it uses two leafs to produce one leaf. The way merkle tree handles this is by adding the single tree-node (leaf) to itself (i.e. hashing the hash).

The result of all hashes is called the root hash. It is this hash that is placed in the block header and this is exactly what I called previously “hashed list of all transactions that took place since the last created block

The merkle tree structure allows for two great features:

1) A node in the bitcoin network can download only the header of the block and a small part of the tree relevant to its type of operation; meaning the node when reading the block does not need to access the whole list of transactions to get what it needs; it simply uses the hash of transaction in the block header and follow the path it needs.

2) It combats any changes to the node; any changes to the tree at any level changes the root hash and hence results in an invalid block (recall the proof of work uses all the details in the block; so when any field in the block is different the proof of work will not be valid, resulting in an invalid block).

I mentioned earlier that a Merkle tree enables partial reading of the tree, meaning there is no need to read the whole tree. This suggests that there is more than one type of node in the bitcoin network. There are basically two types of nodes: “full nodes” and “light nodes”. Full nodes store and process the entirety of every block. Because the Merkle tree allows nodes to process part of the tree, there are also what is called “light nodes”. Light nodes use a protocol called simplified payment verification (SPV). SPV allows the light node to access the header to verify the proof of work and then when it is valid it downloads only what it needs; this is how most “wallets” operate.

That is basically what Merkel Trees are all about. Simple yet powerful. With Merkel trees, nodes in the network can quickly access transactions and also can easily verify the validity of the block.

--

--