Using Merkle Trees in your ZK Apps on Mina Protocol (SnarkyJS)
Merkle Trees are a fundamental part of blockchain technology.
In Bitcoin and other blockchains, they’re used to encrypt blockchain data more efficiently and securely.
On Mina Protocol, developers can use a Merkle Tree data structure to efficiently store state in their smart contract.
Let’s take 5 mins to dive into:
- an illustration of Merkle Trees and
- how to use Merkle Trees in ZK Apps with Snarky JS
Merkle Tree Illustration
A blockchain is a chain of blocks and each block has 1 to many transactions.
A block is represented as a hash of all of these transactions.
Each transaction is represented by a hash, but how do we combine these hashes to get one hash for the block?
Let’s consider 8 transactions, T1, T2, … all the way to T8 (see the gif below). Each one of these are considered leaves of the tree and we can create the hash all the way to a single hash which is called the root of the tree. So let’s start hashing.
- hash T1 with T2: H(T1, T2)
- hash T3 with T4: H(T3, T4)
- hash T5 with T6: H(T5, T6)
- hash T7 with T8: H(T7, T8)
So now we have four parents of these leaves, but now we still have four, but we need to get one single hash. So we’re gonna continue again.
- hash H(T1, T2) with H(T3, T4): H{H(T1, T2), H(T3, T4)}
- hash H(T5, T6) with H(T7, T8): H{H(T5, T6), H(T7, T8)}
And then we have two. We do that again. And then finally we get to the top of the tree where we have a single hash.
And this hash is considered the root of the tree, aka, the Merkle Root.
The Merkle root, is the topmost hash value in a Merkle tree data structure. This is computed by hashing each transaction individually, and these transaction hashes are then combined and hashed together in pairs. This process continues until a single hash, the Merkle root, is obtained.
The Merkle root is used to summarize and verify the integrity of a set of data e.g. transactions within a block.
Why are we learning about Merkle Trees Now?
When you write smart contracts for Mina Protocol using snarky JS, you can use a Merkle Tree data structure for storing data on the smart contract.
Instead of storing the entire dataset, only the root of the tree (which is essentially just a hash) is stored on the Blockchain.
If you would like to verify that some data exists in the tree, then you’ll can provide the merkle witness to the smart contract which can be used to prove whether the data at that leaf node exists.
The witness is a path from one specific leaf node all the way to the root of the tree.
A Merkel witness proves that this actual item is included in the tree.
You can watch this 3 min video explanation of Merkle Trees here:
How to Use Merkle Trees with Snarky JS
The problem developers often face when building ZK Apps on Mina Protocol is that you can only store 8 state variables 🤭.
Only a limited amount of data is stored on chain so that Mina’s chain remains succinct and does not become bloated💪.
If you wanted to create a leaderboard application or voting application, you’d definitely need to store more than 8 variables and the solution to this problem is Merkle Trees 🌳.
Only the root of the Merkle tree will be stored as in the smart contract’s state. Since the Merkle root serves as a compact representation of a large amount of data, this is a great data structure for storing data efficiently in your smart contracts.
Check out these docs that explain Merkle Tres on the Mina Protocol Website:
- https://docs.minaprotocol.com/zkapps/snarkyjs/merkle-tree
- https://docs.minaprotocol.com/zkapps/tutorials/common-types-and-functions
Also, here is a full video tutorial teaching you how to use Merkle Trees with Snarky JS. In this tutorial, we will create a voting application where we will vote on the top 10 songs this week (from a web3 platform called sound.xyz).
A merkle tree will be used to store the song information and the number of votes it has received. The smart contract will also store other state such as number of voters, the winning song, etc. Curious? Watch this video and checkout the github repo, https://github.com/alysiahuggins/youtube_tutorials/tree/main/sound-xyz-voting.
Was this helpful? Drop a comment below. 😃
