Software engineer: previously at Amazon and now at eBay. Certified Professional Cloud Architect.
Merkle trees, also known as binary hash trees, are a type of binary tree. They can be used to efficiently verify the integrity of large sets of data. They are used in both blockchain and non-blockchain-related projects.
Merkle trees are build from the bottom up:
Hash functions take as input any piece of data (a string, an image, etc.) and produce a fixed-length output. An example of a hash function is SHA-256, which takes data of arbitrary size and produces an output that is 256 bits long.
Good hash functions have the following properties:
Cryptographic hash functions need additional properties to make them more secure:
The properties of a Merkle tree derive from its structure and its use of hash functions:
Introduction to Blockchain
I will use Bitcoin to illustrate how Merkle trees can verify if a transaction belongs to a block.
In case you aren’t familiar with blockchains, we can oversimplify things imagining that a blockchain is a distributed linked list of elements called blocks. Blocks contain a list of transactions and a header that stores metadata. Part of this metadata is the root of the block’s Merkle tree, called Merkle root.
Each block points to the hash of its predecessor, to ensure immutability. If the previous block in the chain changes, even by one bit, its hash would change and it would break the chain.
Imagine you are running an app that needs to verify if a transaction T belongs to a block B. In Bitcoin, full nodes store a block’s Merkle root along with all its transactions. For them, it is easy to verify if T belongs to B. Also, they can generate proofs for any transaction in a block on demand.
What if the app runs on a device with limited disk, computing power, and bandwidth? To determine whether T belongs to B, the device needs information. It can retrieve this information from other participants in the network.
The following problems arise:
Merkle trees can help to solve these problems. From the properties of Merkle trees we covered above:
Simplified Payment Verification(SPV) nodes, commonly known as lightweight nodes or light clients, do not store full blocks. They interact with the network to request the information they need to verify transactions. They can assess whether a transaction belongs to a block requesting an inclusion proof and the block header, where the Merkle root is stored.
The algorithm to generate a Merkle root from a list of transactions is as follows:
You can find here my implementation of a Merkle tree. It can verify a Bitcoin block’s Merkle root and generate and verify proofs of inclusion.
Bitcoin’s Merkle tree duplicates the last node in levels with an odd number of nodes. Also, if Bitcoin finds a block that is not valid, it caches its root to avoid trying to mine it again. This combination makes the tree susceptible to second preimage attacks: for an input x, we can find a second input y, different from x, such that h(x) = h(y).
How does this design suffer from this? Let’s go back to our first example, based on the tree represented in the image below:
B2 contains duplicate transactions, making the block invalid. Nodes would cache this root so that next time they find a block with this root they discard it. Both B1 and B2 produce the same root. Thus, nodes will reject B1, even though B1 might be a valid block.
There is another known vulnerability in Bitcoin’s original Merkle trees (already fixed). Understanding it requires more knowledge of how Bitcoin builds transactions. Since this is an introductory article, I have decided to leave it out. However, I might cover transactions in more depth in future articles and revisit this vulnerability.
A Sparse Merkle Tree (SMT) is a variation of a Merkle Tree, where every leaf node has an index along with its value. All leaves are initialized to an empty (null) value. By design, SMTs have 2^256 leaves.
The Merkle tree I described above can verify that a transaction is part of the block by exploring the path from its corresponding leaf to the root of the tree.
However, they cannot be used to prove that a transaction does not belong to a block. And in general, to prove that elements do not belong to a dataset. SMTs can do this.
SMTs can produce proofs of non-inclusions in an efficient manner. The idea is that we know the index of every element. Thus, you know which leaf contains an element. If an element is not part of the tree, the leaf where the element would be stored will be null. Therefore, to produce a proof of non-inclusion, we produce a proof of inclusion generated from that node initialized to null.
Proofs of inclusion work in the same way as Merkle trees’.
Updating a leaf an SMT is also efficient because we only need to modify the path that goes from that leaf to the root. Since SMTs have 2^256 leaves, only 256 nodes need modification.
SMTs deserve their own article, but I wanted to at least introduce the basic idea behind them.
Now you should have a clearer idea of what Merkle trees are and what they are used for. If you want to learn more, I suggest you investigate how:
Git uses them to keep track of changes in files.DynamoDB uses them to identify any inconsistencies between nodes.
I hope you found this article helpful. Share it, because you could help someone pass their exams or get a job.
Previously published at https://www.yourdevopsguy.com/merkle-trees-and-bitcoin/
Create your free account to unlock your custom reading experience.