Contents
What is a Merkle tree?
How do Merkle trees work?
Why are Merkle roots used in Bitcoin?
Mining
Verification
Concluding thoughts
What is a Merkle tree?
The idea of a Merkle tree came about in the early 1980s by Ralph Merkle – a computer scientist best known for his work in the field of public-key cryptography.
A Merkle tree is a structure used to effectively verify the integrity of data in a given dataset, and is particularly important in the context of peer-to-peer networks where participants need to share and verify information independently.
Hash functions are an essential part of Merkle tree structures, so we recommend reading the article entitled What is Hash? Before continuing reading this article.
How do Merkle trees work?
Let's say you want to download a large file. In the case of open source software, you'll typically want to check that the hash value of the file you downloaded matches the value the developers made publicly available. If they are, then you know that the file you have on your computer matches theirs.
If the hash values do not match, then you have a problem. Either you downloaded a malware file impersonating the program, or the download was unsuccessful, so it doesn't work. If the download is not successful, you probably won't be happy if you have to wait a while for the file to download. You will then have to start the process over and hope that it goes well this time.
You might be thinking in this case if only there was an easier way to do this. Fortunately, this is where the Merkle tree comes in. Using this tree, the file is divided into parts. If the file size is 50 GB, you may be able to split it into 100 pieces, each 0.5 GB in size, and download it piece by piece. This is basically what you do when you use torrent files.
In this case, the file source will provide you with a hash value known as the Merkle root. This single value is a representation of each piece of data that makes up your file, but the Merkle root makes it much easier to verify the data.
To keep it simple, we'll look at this example where we're using an 8GB file that's divided into 8 parts, and we'll label these different parts with letters A to H. Then each part will go through a hash function, resulting in 8 different hash values.
We will pass each of the eight parts through a hash function to get their hash values.
Well, now we have something that makes a little more sense. We have the hash values of all the parts, so if one of them is wrong, you'll know that by comparing it to the source hash value, right? Maybe, but this is also hugely inefficient. If the file has thousands of parts, are you really going to partition them all and then compare the results so carefully?
No, instead we'll take each pair of hash values, add them together, and then hash them together. So, we hash hA + hB, hC + hD, hE + hF, and hG + hH so that we end up with 4 hash values, then we perform another round of hashing for these values, eventually reaching 2 hash values. Finally, we hash the remaining two values to get the main hash value – the Merkle root (or root hash value).
The structure looks like an upside-down tree, where in the last row we have the leaves that come together to produce the nodes and eventually the root.
We now have the Merkle root that represents the file we downloaded. This root hash value can be compared to the one provided by the source, and if they match, great! But if the hash values are different, this makes us certain that the data has been modified, that is, one or more parts have produced a different hash value, so any simple modification to the data will give us a completely different Merkle root.
Fortunately, there is an easy way for all of us to check which part is wrong. In this case, let's say this part is hE. First, ask a peer for the two hash values that produced the Merkle root (hABCD and hEFGH). Your hABCD value should match his as there is no error in this subtree. But this does not apply to the value hEFGH, hence you should check this value. You then request the hEF and hGH values and compare them to your own values. You will find that the hGH value is fine, and then you realize that the hEF value is the reason behind the problem. Finally, you will compare the hash values of hE and hF, and now you know that hE is incorrect, so you can re-download this fragment.
In short, a Merkle tree is created by dividing data into several parts, which are then hashed iteratively to form a Merkle root. You can then effectively check whether an error has occurred with a piece of data. As we will see in the next section, there are some other interesting applications as well.
Do you want to start trading in digital currencies? Buy Bitcoin (BTC) on Binance now!
Why are Merkle roots used in Bitcoin?
There are a few use cases for Merkle trees, but here we will focus on their importance in blockchains. Merkle trees are of great importance to Bitcoin and other cryptocurrencies. It represents a major component of each block, as it is located in the block storage partitions. To access the leaves of the tree, we use the transaction hash ( transaction ID) of each transaction in the block.
In this case, the Merkle root serves a few purposes, and below we will review its applications in cryptocurrency mining and transaction verification.
Mining
A Bitcoin block consists of two parts, the first part is the block storage partition, which is a fixed-sized part that contains metadata for the block. The second part is a list of variable-sized transactions, but it is usually much larger than the block storage partition.
Miners need to hash data repeatedly to produce output that matches specific conditions for mining a valid block. They can make trillions of attempts before finding a correct block. On each attempt, they change a random number in the block's storage section (the private code) to produce a different output. However, a large portion of the mass remains the same. The number of transactions can be thousands of transactions, and you will have to hash them each time.
The Merkle root makes the process much easier, when you start mining, you put in a row of all the transactions you want to include and create a Merkle tree. You then place the resulting root hash value (32 bytes) into the block storage partition. Then, when mining all you need to do is hash the block storage partition instead of the entire block.
This method works because it cannot be tampered with, effectively summarizing all block transactions into a compact format. And you can't find a valid block storage partition and then change the transaction list later because that would change the Merkle root. When the block is sent to other nodes, it calculates the root from the list of transactions, and if it does not match what is mentioned in the block storage section, the block is rejected.
Verification
There is another interesting property of Merkle roots that we can take advantage of. This feature is important for simple node software (nodes that do not carry the full copy of the blockchain chain). If you're running a node on a resource-constrained machine, you don't want to download and hash all of the block's transactions. Instead, you can request a Merkle proof – a proof provided by the entire node that proves that a transaction exists in a specific block. This is often referred to as simplified payment verification (SPV) and was explained in detail by Satoshi Nakamoto in the Bitcoin technical report.
To verify hD, we only need the hash values shown in red.
Let's consider, for example, a scenario where we want to know information about a transaction with transaction ID hD. If the value hC is available to us, we can find hCD. Then we need hAB to calculate hABCD. Finally, in the case of hEFGH, we can check that the resulting Merkle root matches the one in the block storage partition. If it matches, this is evidence that the transaction existed in the block – as it would be almost impossible to generate the same hash value with different data.
In the previous example, we only had to perform the hash three times, and without Merkle's proof, we would have needed to perform it 7 times. Since blocks today contain thousands of transactions, using Merkle's proof saves a lot of time and computing resources.
Concluding thoughts
Merkle trees have proven to be extremely useful in a range of computer science applications – and as we have seen, they are of enormous importance to blockchains. In distributed systems, Merkle trees make it easy to verify information without flooding the network with a torrent of unnecessary data.
Without Merkle trees (and Merkle roots), the blocks of Bitcoin and other cryptocurrencies would not be as small as they are today. While simple contract software lacks privacy and security, Merkle's proof allows users to verify whether their transactions have joined a block with minimal costs.