Posted by Sacha Saint-Leger on January 30, 2020
Merkle trees are a fundamental part of what makes blockchains tick… Thanks to Merkle trees, it is possible to build Ethereum nodes that run on all computers and laptops large and small, smart phones, and even internet of things devices… –Vitalik Buterin
In this visual essay, we try our best to explain Merkle trees from first principles. The only assumption we make is that you have a basic understanding of what blockchains are, and that you’re familiar with the concept of a binary tree.
If you’ve been in the blockchain space for a while, you’ve likely come across Merkle trees before: the Bitcoin blockchain uses them to store the transactions in every block, while Ethereum contains not just one Merkle tree, but three trees.
While we won’t get into the details here, every block header in Ethereum contains three trees, for three kinds of objects: to handle transactions, receipts (pieces of data showing the effect of each transaction), and state. If you want to find out more, see this excellent post by Vitalik.
Why do we care? At Iden3, one of our major goals is scalability. Specifically, we believe anybody should be able to create as many identities as they want. And that any identity should be able to generate as many claims as they want.
Merkle trees are one of the keys to achieving this goal (we’ll dig deeper into the why’s and how’s in a follow-up post).
But before we get to Merkle trees, it’s important to first understand what a hash function is. Hash functions are a key part of the Merkle tree operating system.
A hash function basically maps an input string of any size to an output string of a fixed size.
It must be efficiently computable – by that we mean that for any given input string, we can figure out the output of the hash function in a reasonable amount of time. More technically, computing the hash of an n‐bit string should take O(n) time.
For a hash function to be cryptographically secure, it must have three additional properties:
While we won’t get into the details here, let’s briefly discuss what each of these properties mean.
Collision resistance means that nobody can find two inputs that map to the same output.
Hiding means that given an output there’s no feasible way to figure out the input that generated it. In other words, the hash function is irreversible.
Puzzle-friendliness is a little more complicated. Intuitively it means it’s very hard to target the hash function to come out to some particular output value y. Don’t worry if you don’t see why this property is useful, for the purposes of this article, it isn’t very important.
To be slightly more formal: Take: y = H(x|r). Where y is the output of the hash function H, and r and x are the inputs.
The hiding property specifies that given an output ( y ), it is infeasible to find an input ( x ) such that y = H(x|r) is satisfied. Note, that in this case r is not given (in other words, hidden).
Puzzle-friendliness means that given the output ( y ) and part of the input ( r ), it is difficult to find an x such that y = H(x|r).
If there’s one thing to take away from all this, it’s that hash functions allow us to store a cryptographic hash of a data value at some fixed point in time.
If at some point in the future, we want to check the data hasn’t changed, we simply hash the data again and check that the new output (cryptographic hash) matches the previous output.
This works because we know by the collision resistance property of the hash function, that nobody can find two inputs that map to the same output. So if the output is the same, the input must also have been the same.
Now that you have an intuitive understanding for what a hash function is, we’re ready to tackle Merkle trees :)
The most common and simple form of Merkle tree is the binary Merkle tree. A binary Merkle tree is a binary tree built using hash functions (since this is the form we’ll be focusing on in this essay, we’ll omit the binary prefix from now on).
Merkle trees are useful when we want a data structure that:
As you can probably see, these properties make them a natural use case for blockchains.
Note: at Iden3 we use a slightly more complex data structure called a sparse Merkle tree. Sparse Merkle trees have an additional property: they make it easy to prove that some data doesn’t exist. But we’ll talk more about that in another post.
Before we take a closer look at proof of membership and tamper resistance, let’s go through how to build a Merkle tree given some data:
It turns out that any attempt to tamper with any piece of data can be detected by simply remembering the hash at the root of the tree.
To understand why this is the case, let’s look at what happens if an adversary wants to tamper with a data block:
Merkle trees allow us to quickly check membership (through a neat mechanism known as Merkle proofs). What do we mean by that?
In technical terms: This means that if there are n nodes in the tree, only about log(n) items need to be shown. And since each step just requires computing the hash of the child block, it takes about log(n) time for us to verify it. And so even if the Merkle tree contains a very large number of blocks, we can still prove membership in a relatively short time. Verification thus runs in time and space that’s logarithmic in the number of nodes in the tree. Source (pg 35)
In sum, Merkle trees are handy because they have some nice properties that help us minimize the amount of data we need to store on-chain. And this is important because storing data on a blockchain is expensive.
More specifically, to ensure tamper resistance and proof of membership we only need to keep track of the root of the tree.
In other words this means that, no matter how big the tree is, the only piece of data we need to store on-chain is the root.
We hope this you found this introduction useful. We’ll be digging deeper into how we use Merkle trees at Iden3 in a series of follow up posts.
In the meantime, if you’re curious to know more about Merkle trees and their applications in Ethereum, we recommend reading throught this excellent essay by Vitalik.
Our sparse Merkle tree implementations: