Merkle Tree

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.

Referencing off-chain data

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 labeled 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 of Merkle trees is the witness, also known as a Merkle proof or Merkle path. The witness is the path from one specific leaf node to the very top of the tree (the root). Merkle witnesses are proofs of inclusion that prove that one specific piece of data (for example, 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 a player's score 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. You will quickly run out of on-chain space with eight or more participants.

A possible solution to that problem is to use the power of Merkle trees, 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. For example, to map a player's id to score points:

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.

info

Sometimes the variable root is 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

info

Guessing a simple hash like this example can easily be brute forced, especially if the preimage is simple (like a 5-letter word or a small number with only a few digits).

Ensure that your zkApps are always secure, especially when dealing with funds.

The first method allows a player to make a guess; if the guess is correct, the player gains one point. The method takes the player's guess and hashes 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 scoreboard.

A second method is required to take care of the reward. It checks if the player's 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 if it matches the on-chain stored Merkle root.

note

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 async guessPreimage(guess: Field, account: Account, path: MerkleWitness) {
    // we fetch z from the chain
    const z = this.z.get();
    this.z.requireEquals(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.requireEquals(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 async claimReward(account: Account, path: MerkleWitness) {
    // we fetch the on-chain commitment
    const root = this.root.get();
    this.root.requireEquals(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 reference off-chain data easily by only adding a couple of lines of code. However, it is your responsibility as the developer of the zkApp to make sure that the Merkle tree that is 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.

info

Merkle trees are great for referencing off-chain state, but you must also store this off-chain state somewhere.

Where and how to store the data off-chain storage is left up to you, the developer. Tell us how you are using Merkle trees in the #zkapps-developers channel in Mina Protocol Discord.

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);