Before diving into this, if you have not already, I recommend you take a look at what a hash is because having a grasp of what hash is, is essential to fathom merkle tree structures.
Merkle Root is a hash, at the end of a merkle tree which consists of hashes of multiple pieces of data. The name comes from its creator Ralph C. Merkle who patented tree of hashes in 1979.
Satoshi Nakamoto mentioned Ralph C. Merkle in Bitcoin Whitepaper
[7] R.C. Merkle, "Protocols for public key cryptosystems," In Proc. 1980 Symposium on Security and
Privacy, IEEE Computer Society, pages 122-133, April 1980.
To have an understanding of merkle trees, let’s start with eight pieces of data which will be the “leaves” of our tree. Second step is to compute hashes of these each data sets. Now we have eight hashes belonging to eight pieces of data. This data can be anything, a word, a movie file or an information about a transaction. Next, we compute the hashes of these hashes in groups of two which are “branches”, and we repeat that until we left with only one hash which will be the root of the tree, the merkle root.
Like any other hash (SHA-256), merkle root looks like this:
06a8ac9d2a18e0ad1cf8f6919681a98c156ba00716a388ab6506185a95551cb5
As seen in the image above it is a simple tree structure. But what if the number of data pieces is not the power of 2?
The hash of the “data” which has not a pair is attached to the tree in such a way that as if it had a pair. By doing so, it reduces the number of total calculations and prevents generating unnecessary duplicate hashes. An example for this is shown below.
And another example for a 2N+1 sample size.
Merkle Root is one of the essential elements in a Bitcoin block, a crucial one. In fact, merkle tree structure is a vital part of blockchain technology. In every Bitcoin block, which is generated approximately every ten minutes, there is one merkle root. This merkle root is obtained from all the transactions in that block. So, all the transactions in a Bitcoin block are represented by a final hash the merkle root.
Thanks to merkle root we have all the information digested in a hash.
But why do we need such a structure? Why not just concatenate all the transactions and compute a hash? As Satoshi Nakamoto explains it in Bitcoin Whitepaper, it is for saving up disk space and validating transactions quickly. This may seem like a mediocre attribute but without merkle tree blockchain technology would have a hard time at getting invented
Saving up disk space
“Pruning” as Satoshi Nakamoto describes in Bitcoin Whitepaper, is the unnecessity of storing the interior hashes. By pruning the branches and storing only the last hash (merkle root) a lot of disc space is saved.
The interior hashes do not need to be stored. A block header with no transactions would be about 80 bytes. If we suppose blocks are generated every 10 minutes, 80 bytes * 6 * 24 * 365 = 4.2MB per year. With computer systems typically selling with 2GB of RAM as of 2008, and Moore's Law predicting current growth of 1.2GB per year, storage should not be a problem even if the block headers must be kept in memory. -Satoshi Nakamoto, Bitcoin Whitepaper
Merkle root is only 32 bytes of data. Image blow is from Bitcoin Whitepaper
Simplified Payment Verification
In addition to saving up disk space, with the help of merkle tree, validating a transaction is nearly effortless. Let’s say we want to validate Transaction 3. Instead of taking all the transactions and computing the hashes of the whole tree, server returns the value of “Hash01” and “Hash2”. These two are to obtain a merkle root. We can compute “Hash3” because we know the Transaction 3, in fact it is the one we want to validate. With “Hash2” and “Hash3” we compute “Hash23” and then with “Hash23” and “Hash01” we finally compute merkle root. Then we can compare two merkle roots. If it is a match than “Transaction 3” will be valid. Image blow is from Bitcoin Whitepaper.
Let’s say in a block we have eight transactions and you want to validate “Tx f”. Only data you have is merkle root (last hash) in block header.
+: Hey blockchain! I have a transaction. It is “Tx f”. I want to validate it.
- : OK. Let me see. Hmm. There you go. Here is what you need:
“Hash e”
“Hash gh”
“Hash abcd”
Instead of all the seven hashes, only three are sufficient and in practice it is efficient. Let’s follow along with the image above. We only have merkle root(Hash ABCDEFGH). If we want to validate Transaction F, servers returns us: “Hash E”, “Hash GH” and “Hash ABCD”. We have Transaction F which means naturally we have Tx F data and we can compute hash “Hash f”. And with the given “Hash E” we can compute “Hash EF” so it does not need to return from our query. With “Hash EF” and given “Hash GH” we compute “Hash EFGH” and lastly with “Hash ABCD” we compute hash “Hash ABCDEFGH” A.K.A merkle root and compare it with one on the blockchain. If it matches then Transaction F is validated.
If we had 16 transactions we would need 4 hashes. OK, let’s list it to see it clearly.
| Number of Transactions | Hashes Needed | Hashes Needed If There Was not any Merkle Tree |
|---|---|---|
| 8 | 3 | 7 |
| 16 | 4 | 15 |
| 32 | 5 | 31 |
| 64 | 6 | 63 |
| 128 | 7 | 127 |
| 256 | 8 | 256 |
| 512 | 9 | 511 |
| 1024 | 10 | 1023 |
| 2048 | 11 | 2047 |
Since nowadays a bitcoin block has a transaction count around 2000, you see that how merkle tree structure is crucial for rapid transaction validation and saving up disc space and computational power. Imagine how this all would be achieved without a merkle tree. Well do not bother, if merkle tree was not invented there would not have been blockchain nor bitcoin.
Resources:
Thank you for reading. I hope, you enjoyed it and/or it helped you somehow.
Have a nice day :)