Over the Proofs: 🌎 a World of Trees Merkle Mountain Ranges Edition 🛰️
At Herodotus, we’re building on top of zero-knowledge and storage proofs. This cryptographic concept allows proving the existence of any storage value (and more) stored on-chain for both historical and current data.
This primitive unlocks new possibilities and enables synchronous cross-layer data access across blockchains.
Our mission is to help builders conceive new architectures that are more synchronous, trustless, and without the need for asynchronous messaging.
While using storage proofs in and of itself is a powerful tool, it can quickly become complex and pretty technical.
Our goal is to provide the needed infrastructure to unleash the potential use cases of those proofs by doing the heavy lifting and removing the friction as much as possible from our users, letting them focus on coding their applications.
🌳 Some words about trees
This article will describe a cryptographic data structure we’ve implemented to solve our needs.
But first, let’s quickly talk about Merkle Trees and what they’re suitable for and not.
Merkle Trees are hash structures commonly used in the blockchain industry due to their efficiency in data storage. Indeed, using recursive hashes, only the root hash eventually needs to be stored, saving a lot of space.
Merkle proofs can be generated to prove the existence of an element in the tree, i.e., by proving that recursively hashing the nodes lead to the same root hash.
Ethereum, at the time of writing, widely uses Merkle Patricia Trees (and might upgrade to Verkle trees in the future) to store its state, storage, and transactions.
While Merkle Trees work well for a finite set of data (i.e., leaves), they’re not optimized for ever-changing sets.
Herodotus is developing an API that allows developers to prove many things on-chain. To do that, we verify the existence and integrity of block headers (alongside other things) on a given chain.
Since there is a new header generated at every block, we’re keeping track of it in a verifiable manner, i.e., on-chain.
It is important to us to be a provider of verifiable data. As the saying goes, “don’t trust, verify”.
For that reason, after some research, we discovered that a less-known variant of Merkle Trees would better fit our need to accumulate verified headers in our contract’s Merkle tree.
Let’s dive into it.
Introducing ⛰️ Merkle Mountain Ranges
MMRs can be considered a list of Merkle trees, each Merkle tree is represented as a mountain, and the whole list forms the range.
MMRs share the common properties of Merkle Trees while adding some benefits:
- Appending an element to an MMR is much more efficient as, in most cases, we don’t need to navigate through the entire tree to include the new element. The underlying complexity is log2(n) “mountain tips.”
- Proving happens with log2(n) sized proofs consisting of a Merkle path to the tip of the tree.
- Updating an element is also doable efficiently.
- It is possible to optimize further by batching updates and insertions.
- Both insertions and updates can be implemented on-chain, achieving full transparency on how the tree is updated.
Using MMRs to store block headers permits us to append a header by providing the list of peak hashes (mountain tips) and the new element to insert.
With a traditional Merkle tree, we’d have to pass the entire list of values contained in the tree.
By design, the number of peaks grows very slowly; only 10 hashes are needed for a tree of size 10 million.
Thank you for reading. We hope you enjoyed this article featuring Merkle Mountain Ranges and their benefits.
If you’re interested in knowing more about MMRs, here are some useful links:
- https://youtu.be/uA1dw1qDytM?t=69
- https://docs.grin.mw/wiki/chain-state/merkle-mountain-range/
- https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-May/012715.html
If you liked this article, don’t hesitate to follow us on Twitter, and if you want more details about the infrastructure we’re building, visit our documentation.
Our Cairo MMR implementation
We’ve implemented an MMR using Cairo. You can look at it, but remember that the “library” is not yet ready to use.
Note: this repository contains a work in progress and should not be viewed as production-ready.
Keep BUIDLING 🛰️
