Merkle Trees and Merkle Roots Explained
Domov
Články
Merkle Trees and Merkle Roots Explained

Merkle Trees and Merkle Roots Explained

Advanced
Zverejnen├ę Jul 6, 2020Aktualizovan├ę Dec 27, 2022
7m

What is a Merkle tree?

The concept of a Merkle tree was proposed in the early ÔÇś80s by Ralph Merkle ÔÇô a computer scientist renowned for his work on public-key cryptography.

A Merkle tree is a structure used to efficiently verify the integrity of data in a set. TheyÔÇÖre particularly interesting in the context of peer-to-peer networks, where participants need to share and independently validate information.

Hash functions are at the core of Merkle tree structures, so we recommend you check out What is Hashing? before proceeding.


How do Merkle trees work?

Suppose that you want to download a large file. With open-source software, youÔÇÖd typically want to check that the hash of the file you downloaded matches one made public by the developers. If it does, you know that the file you have on your computer is exactly the same as theirs.

If the hashes donÔÇÖt match, you have a problem. YouÔÇÖve either downloaded a malicious file masquerading as the software, or it hasnÔÇÖt downloaded correctly and, therefore, wonÔÇÖt work. If the latter is the case, you probably wonÔÇÖt be too happy if youÔÇÖve had to wait for some time for the file to download. Now, you need to restart the process and hope that it doesnÔÇÖt corrupt again.

If only there were an easier way to go about this, you think. Fortunately, thatÔÇÖs where Merkle trees come in. With one of these, you would have your file broken up into chunks. If it was a 50GB file, you might divide it into one hundred pieces, such that each is 0.5GB in size. Then, it would be downloaded piece-by-piece. This is essentially what you do when you torrent files.┬á

In this case, your source will have provided you with a hash known as the Merkle root. This single hash is a representation of every chunk of data that makes up your file. But the Merkle root makes it much easier to verify the data. 

To keep it simple, letÔÇÖs take an example where we use an 8GB file broken into eight pieces. Call the different fragments A through H. Each fragment is then passed through a hash function, giving us eight different hashes.

We pass each of our eight fragments through a hash function to get their hashes.

We pass each of our eight fragments through a hash function to get their hashes.


Okay, so weÔÇÖve got something that makes a bit more sense. We have the hash of all the fragments, so if one is faulty, weÔÇÖll know by comparing it with the sourceÔÇÖs one, right? Possibly, but thatÔÇÖs also incredibly inefficient. If your file has thousands of fragments, are you really going to hash all of them and meticulously compare the results?

No. Instead weÔÇÖre going to take each pair of hashes, combine them, then hash them together. So we hash hA + hB, hC + hD, hE + hF, and hG + hH. We end up with four hashes. Then we do another round of hashing with these to end up with two. Finally, we hash the remaining two to get to our master hash ÔÇô the Merkle root (or root hash).

The structure looks like an upside-down tree. On the bottom row, we have the leaves, which are combined to produce the nodes and, finally, the root.

The structure looks like an upside-down tree. On the bottom row, we have the leaves, which are combined to produce the nodes and, finally, the root.


We now have the Merkle root that represents the file we downloaded. We can compare this root hash with the one provided by the source. If it matches, perfect! But if the hashes are different, we can be sure that the data was modified. In other words, one or more fragments have produced a different hash. So any slight modification of data will give us a totally different Merkle root. 

Fortunately, thereÔÇÖs a handy way for us to check which fragment is faulty. In our case, letÔÇÖs say itÔÇÖs hE. You would start by asking a peer for the two hashes that produced the Merkle root (hABCD and hEFGH). Your value hABCD should match theirs since thereÔÇÖs no mistake in that subtree. But hEFGH wonÔÇÖt, so you know to check in there. You then request hEF and hGH, and compare them with yours. hGH will look fine, so you know that hEF is our culprit. Lastly, you compare the hashes of hE and hF. You now know that hE is incorrect, so you can redownload that chunk.

Summing it all up, a Merkle tree is created by dividing data into many pieces, which are then hashed repeatedly to form the Merkle root. You can then efficiently verify if something has gone wrong with a piece of data. As weÔÇÖll see in the next section, there are other interesting applications, too.


Looking to get started with cryptocurrency? Buy Bitcoin on Binance!


Why are Merkle roots used in Bitcoin?

There are a handful of use cases for Merkle trees, but here we will focus on their importance in blockchains. Merkle trees are essential in Bitcoin and many other cryptocurrencies. TheyÔÇÖre an integral component of every block, where they can be found in the block headers. To get the leaves for our tree, we use the transaction hash (the TXID) of every transaction included in the block.┬á

The Merkle root serves a couple of purposes in this case. LetÔÇÖs take a look at their applications in cryptocurrency mining and transaction verification.


Mining

A Bitcoin block is made up of two pieces. The first part is the block header, a fixed-size segment containing metadata for the block. The second part is a list of transactions whose size is variable, but tends to be much larger than the header.

Miners need to repeatedly hash data to produce an output that matches certain conditions to mine a valid block. They can make trillions of attempts before finding one. With each attempt, they change a random number in the block header (the nonce) to produce a different output. But much of the block remains the same. There can be thousands of transactions, and youÔÇÖd still need to hash them every time.

A Merkle root streamlines the process considerably. When you start mining, you line up all of the transactions you want to include and construct a Merkle tree. You put the resulting root hash (32 bytes) in the block header. Then, when youÔÇÖre mining, you only need to hash the block header, instead of the whole block.

This works because itÔÇÖs tamper-proof. You effectively summarize all of the blockÔÇÖs transactions in a compact format. You canÔÇÖt find a valid block header and later change the transaction list, because that would change the Merkle root. When the block is sent to other nodes, they calculate the root from the transaction list. If it doesnÔÇÖt match the one in the header, they reject the block.


Verification

ThereÔÇÖs another interesting property of Merkle roots that we can leverage. This one concerns the light clients (nodes that donÔÇÖt hold a full copy of the blockchain). If youÔÇÖre running a node on a device with limited resources, you donÔÇÖt want to download and hash all of a blockÔÇÖs transactions. What you can do instead is simply request a Merkle proof ÔÇô evidence provided by the full node that proves that your transaction is in a particular block. This is more commonly referred to as Simplified Payment Verification, or SPV, and was detailed by Satoshi Nakamoto in the Bitcoin whitepaper.

To check hD, we only need the hashes shown in red.

To check hD, we only need the hashes shown in red.


Consider the scenario where we want to know information about the transaction whose TXID is hD. If hC is provided to us, we can work out hCD. Then, we need hAB to calculate hABCD. Lastly, with hEFGH, we can check that the resulting Merkle root matches the one from the block header. If it does, itÔÇÖs proof that the transaction was included in the block ÔÇô it would be near-impossible to create the same hash with different data.

In the above example, weÔÇÖve only had to hash three times. Without a Merkle proof, we would have needed to do it seven times. Since blocks nowadays contain thousands of transactions, using Merkle proofs saves us a lot of time and computing resources.


Closing thoughts

Merkle trees have proven themselves highly useful in a range of computer science applications ÔÇô┬áas weÔÇÖve seen, theyÔÇÖre incredibly valuable in blockchains. In distributed systems, Merkle trees allow for easy verification of information without flooding the network with unnecessary data.

Without Merkle trees (and Merkle roots), Bitcoin and other cryptocurrenciesÔÇÖ blocks would not be nearly as compact as they are today. And while light clients are lacking on the privacy and security fronts, Merkle proofs enable users to check whether their transactions have been included in a block with minimal overhead.

Zdie─ża┼ą pr├şspevky
Zaregistrujte si ├║─Źet
E┼íte dnes vyu┼żite svoje znalosti v┬ápraxi otvoren├şm ├║─Źtu Binance.