What is a Merkle tree and why is it useful?
Recently I became interested in learning Go.
While looking around for something fun to build with it I came across a data structure called a Merkle tree.
Merkle trees are named after Ralph Merkle who invented it in 1979. They are used as an efficient way to verify large data structures in distributed systems, especially with unreliable or untrusted peers.
To see why Merkle trees are useful, let’s take a look at two high profile examples - Bittorrent and Bitcoin.
Bittorrent works by downloading small pieces of the file called chunks from multiple peers. One immediate problem we might have is that the peers could be anybody, anywhere. The data they send might get corrupted, or even worse, the client might deliberately send malicious data. So how can we be sure your shiny new pirated copy of Angry Birds doesn’t secretly contain code that turns your PC into a Russian botnet slave?
The answer is of course, hashing. A basic approach would be to include a hash of the entire file from the original “trusted” source. Then when you have finished downloading all the pieces you could hash your copy of the file and make sure it matches the original hash.
This isn’t very efficient though. You have to wait until the entire file is downloaded before you can check it, and if the hash doesn’t match, you have no way of knowing which part of the file is bad so you would have to download the entire thing again.
For a file that’s several hundred gigabytes, that could take a while.
Enter Merkle trees.
When you download a magnet link from your favourite torrent site, what you are actually getting is the Merkle tree root hash of the file.
This root hash is generated like so:
- The file is partitioned into lots of little chunks
- The hash of each chunk is calculated
- These hashes are used as the leaves of a tree
- You work your way up, each node contains a hash of the concatenation of its child hashes. Usually there are two children per node but this isn’t mandatory.
- When you get to the top you have your root hash
Now we have our root hash, we can go out and get its direct children from untrusted peers. We can be sure we are getting the correct child hashes by concatenating them, taking the hash of that and confirming it’s equal to the root hash.
We can repeat this process to download the entire Merkle tree which is a fairly lightweight data structure compared to the base file.
When we’ve finished downloading the Merkle tree we have a verified set of leaf node hashes, each of which verifies a small chunk of data. Now we can individually verify each chunk - so if a malicious peer sends us bad data, we only have to throw away and re-download a few kilobytes instead of the entire file.
Bitcoin could technically work without Merkle trees, but they make it more practical for lightweight clients to verify individual transactions.
Let’s first consider how Bitcoin would work without Merkle trees.
Imagine we want to verify that someone sent us some Bitcoin in block #597876. First we download the header for that block.
The header itself is verifiable due to the intrinsic properties of the blockchain (let’s leave aside explanation of how the blockchain performs that magic for another day). Inside the header there is a hash that verifies the contents of the block attached to the header.
The block is where all the actual transaction data lives.
If this header hash was a simple SHA256 of the whole block, we could download every transaction that made up that block, check that our transaction is indeed there, and verify the entire block to be sure that we have the correct version.
But this isn’t what Bitcoin does - Bitcoin places a Merkle root into the header instead.
This makes verifying individual transactions more efficient.
Not only is it faster to download the block itself, since now we can get it from peers and verify small pieces just like bittorrent, it also means we can verify an individual transaction without fetching the entire block.
All we need is the transaction we care about, and every branch that links it back to the Merkle root. As long as the hashes of all these branches add up, we’re good to go.
This way, even if there are an extremely large number of transactions in the block, the work you need to do (and the number of hashes you need to request/download) in order to verify the integrity is only log(n) instead of n.
So there you have it! Merkle trees are pretty neat. And if you’ve ever bought or sold bitcoin, or downloaded anything with bittorrent, then you’ve used a Merkle tree without even knowing it.