Please note that zkApp programmability is not yet available on Mina Mainnet, but zkApps can now be deployed to Berkeley Testnet.
Merkle Tree
Referencing off-chain data
zkApp accounts can store only a limited amount of data on chain so that Mina's chain remains succinct and does not become bloated. But some zkApps might require you to access more than what you can store on-chain in a zkApp account. But how can you achieve that? The answer is a Merkle tree! Merkle trees (or similar structures such as Verkle trees) allow you to reference off-chain data by storing only a single hash on-chain.
How does that work?
Merkle trees are special binary trees in which every leaf (the nodes at the very bottom of the tree!) are cryptographic hashes of the underlying pieces of data and the internal nodes are labelled with the cryptographic hash of the concatenated labels (hashes) of its child nodes.
By following this algorithm to the very top, you end up with one single node (the root node) that stores the root hash of the tree. The root hash is a reference to all pieces of data that were included in the tree's leaves so you can reference large amounts of data by using one small hash! Another benefit that Merkle trees provide is something called the witness (sometimes also called Merkle proof or Merkle path). The witness is the path from one specific leaf node to the very top of the tree to the root! Merkle witnesses are proofs of inclusion that prove that one specific piece of data (an account in the ledger or the scores on a leaderboard) exists within the entire tree.
How are Merkle trees useful for zkApps?
You can reference large amounts of off-chain data and prove inclusion of very specific parts of that data with only a small hash - the root - and a witness.
To use Merkle trees and reference off-chain data in your zkApps on Mina, store the root of the tree on-chain and voilà, you now have access to more data off-chain.
Imagine a zkApp that manages a game with a leaderboard. The zkApp has a method to update the score of a player if the player guesses a number correctly. After a player reaches a threshold score, the player can invoke another method to get a reward. Because you want many players to participate in the game, you are drastically limited by how much data can be stored on-chain. With eight or more participants, you will quickly run out of on-chain space.
A possible solution to that problem is to use the power of Merkle trees and store the public keys of each player and their corresponding scores off-chain and reference the keys in the smart contract.
Look at the data structure first. Imagine you want to map a player's id to score points, so this:
0: 5 points
1: 3 points
2: 0 points
3: 8 points
... : ...
7: 2 points
Implementing the smart contract
Now it's time to look at what a leaderboard zkApp might look like. To have on-chain state that points to the off-chain Merkle tree, call this variable the root.
Sometimes the variable root is also called commitment, because it commits to something.
Additionally, you want to store a variable z that is the hash of the value a player has to guess: H(guess) = z
Guessing a simple hash like in this example can easily be brute forced, especially if the preimage is something simple (like a 5-letter word or a small number with only a few digits).
Be sure that your zkApps are always secure, especially when dealing with funds!
The first method allows a player to make a guess, and if the guess is correct, the player gains one point.
The method takes the players guess and hashes it, it then checks if the hash H(guess) equals the on-chain state z and if that's the case, then the player gains one point on the score board.
A second method is required to take care of the reward. It checks if the players score is over a threshold and pays out a reward if that's the case. This method must also verify the Merkle witness and check it if it matches the on-chain stored Merkle root!
The examples folder in the o1js repository includes a working Merkle tree example with all of the required boilerplate code.
class Leaderboard extends SmartContract {
// the root is the root hash of our off-chain Merkle tree
@state(Field) root = State<Field>();
// z is the hashed number we want to guess!
@state(Field) z = State<Field>();
init() {
super.init();
// this is our hash we want to guess! its the hash of the preimage "22", but keep it a secret!
this.z.set(
Field(
'17057234437185175411792943285768571642343179330449434169483610110583519635705'
)
);
}
@method guessPreimage(guess: Field, account: Account, path: MerkleWitness) {
// we fetch z from the chain
const z = this.z.get();
this.z.assertEquals(z);
// if our guess preimage hashes to our target, we won a point!
Poseidon.hash([guess]).assertEquals(z);
// we fetch the on-chain commitment/root
const root = this.root.get();
this.root.assertEquals(root);
// we check that the account is within the committed Merkle Tree
path.calculateRoot(account.hash()).assertEquals(root);
// we update the account and grant one point!
let newAccount = account.addPoints(1);
// we calculate the new Merkle Root, based on the account changes
const newRoot = path.calculateRoot(newAccount.hash());
this.root.set(newRoot);
}
@method claimReward(account: Account, path: MerkleWitness) {
// we fetch the on-chain commitment
const root = this.root.get();
this.root.assertEquals(root);
// we check that the account is within the committed Merkle Tree
path.calculateRoot(account.hash()).assertEquals(root);
// we check that the account has at least 10 score points in order to claim the reward
account.score.assertGte(UInt32.from(10));
// finally, we send the player a reward
this.send({
to: account.address,
amount: 100_000_000,
});
}
}
Merkle trees allow you to easily reference off-chain data by only adding a couple of lines of code. However, it is the responsibility of the developer of the zkApp to make sure that the Merkle tree that is being referenced on-chain is always in sync with the actual off-chain data structure.
You can look at the Merkle tree example in the o1js repository to get a better understanding of how you can leverage the power of Merkle trees.
Merkle trees are great for referencing off-chain state. But just referencing the state is not enough - you also need to actually store it somewhere.
Where and how to store the data off-chain storage is left up to you, the developer. We are exploring solutions and are very interested to see and hear about approaches from others in the community.
Merkle Tree - API reference
const treeHeight = 8;
// creates a tree of height 8
const Tree = new MerkleTree(treeHeight);
// creates the corresponding MerkleWitness class that is circuit-compatible
class MyMerkleWitness extends MerkleWitness(treeHeight) {}
// sets a value at position 0n
Tree.setLeaf(0n, Field(123));
// gets the current root of the tree
const root = Tree.getRoot();
// gets a plain witness for leaf at index 0n
const witness = Tree.getWitness(0n);
// creates a circuit-compatible witness
const circuitWitness = new MyMerkleWitness(witness);
// calculates the root of the witness
const calculatedRoot = circuitWitness.calculateRoot(Field(123));
calculatedRoot.assertEquals(root);