Building On Mina: A guide to writing smart contract implementing Merkle Trees using 01js

This article will explore Merkle Trees within the Mina ecosystem, demonstrating their practical application with a step-by-step creation of a Voting Zk App.

Introduction

A blockchain consists of a chain of blocks, with each block containing one or more transactions. Each block is identified by a cryptographic hash representing its contents, including transactions and metadata.

Within a block, transactions are structured using a Merkle tree, where each transaction is represented by a hash. These transaction hashes serve as the leaves of the tree. Each pair of transaction hashes is recursively hashed together until a single root hash, called the Merkle root, is obtained. This Merkle root, along with other block metadata, is then included in the block header, ensuring data integrity and efficient verification.

In Mina, zkApp accounts can only store a limited amount of data to prevent bloating. Hence, need for a Merkle tree, which allows the referencing of off-chain data by storing only a single hash on-chain, thereby enabling Mina to maintain its succinctness.

The Merkle tree root summarizes and verifies the integrity of a set of data and is used to prove that some data exists in the Merkle tree, the root is considered a compact representation of a large pool of data so this allows an efficient verification and confirmation of data integrity inside the blockchain system.

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 which is the root. Merkle witnesses are proofs of inclusion that prove that one specific piece of data

You can reference large amounts of off-chain data and prove the inclusion of very specific parts of that data with only a small hash - the root - and a witness.

Let's start building.

Imagine we have a zkApp where users can vote for their favourite NFTs. Each vote increases the NFT’s count, and once an NFT reaches a certain number of votes, it can claim a reward. But storing all this data on-chain isn’t practical with so many NFTs and voters—it would quickly run out of space.

We make use Merkle trees to keep NFT vote data off-chain while still allowing the smart contract to verify and update votes securely.

We'll take the first step by installing the zkapp-cli.

npm install -g zkapp-cli

After we have that installed we'll enter this command to create a project

zk project votingNft

We'll have the choice to select one of the options in the image below, navigate the options and select none

After that has been selected, the project will be created, after it's done we will navigate to the folder from the terminal using

cd votingNft

We need to remove some files that have been generated along with the project because we won't be using them. With this command, we'll delete the files

cd src
rm Add.test.ts Add.ts interact.ts

Then while still in the src directory, we run this command to create the necessary files we exit the src directory

touch Voting.ts Voting.test.ts

//exit the directory
cd ..

Navigate to index.ts and replace the content with

import { Voting } from './Voting.js';

export { Voting };

We are ready to start building so let's open the Voting.ts file, we import the necessary packages that we need to get this ball rolling

import { Field, SmartContract, state, State, method, Struct, MerkleWitness, Poseidon, Provable } from "o1js";

We need to define a tree height, The tree height decides how many layers of grouping are needed, affecting how quickly and easily data can be verified and we'll create a corresponding Merkel Witness class

The height states how many leaves we can have when specifying the witness, we'll see this in action when taking a look at the data in the tree

export const treeHeight = 4

export class MerkleWitness4 extends MerkleWitness(treeHeight){}

Now let's create our main Voting smart contract and initialize it

export class Voting extends SmartContract{
    // declare state variables
    @state(Field) voters = State<Field>()
    @state(Field) winningNft = State<Field>()
    @state(Field) winningVotes = State<Field>()

    // root of the merkle tree
    @state(Field) treeRoot = State<Field>()

    init(){
      super.init()
      this.voters.set(Field(1))
    }

   // initialize the state on the contract
       @method async initState(initialRoot: Field){
     this.treeRoot.set(initialRoot)
   }
}

We define the state variables to hold the voters, winningNft, winningVotes and the treeRoot, and then we initialize the state of the contract. We continue by creating a Class for the NFT and create a method to vote.

export class NFT extends Struct({nftName: Field, nftCreator: Field, nftVotes: Field}){

//method for the vote
vote(){
  this.nftVotes = this.nftVotes.add(1)
 }
}

First, we verify that the NFT is present in the Merkle tree. Once confirmed, the voting process takes place. After casting the vote, we check if the currently voted-on NFT has surpassed the current winner in votes. If it has, we update the winner. Otherwise, the existing winning NFT remains unchanged. Finally, the Merkle tree is updated to reflect any changes made to the NFT. we implement the method voteForNft to handle this entire process.

export class Voting extends SmartContract{
  // declare state variables
  @state(Field) voters = State<Field>()
  @state(Field) winningNft = State<Field>()
  @state(Field) winningVotes = State<Field>()

  // root of the merkle tree
  @state(Field) treeRoot = State<Field>()
     init(){
       super.init()
       this.voters.set(Field(1))
     }

  // initialize the state of the contract
  @method async initState(initialRoot: Field){
    this.treeRoot.set(initialRoot)
   }

 //method to vote for the nft
 @method async voteForNft(nft: NFT, witness: MerkleWitness4){

  //Get the tree root and see if the nft is in it
  const treeRoot = this.treeRoot.getAndRequireEquals()

  // check to see whether the nft is in the merkle tree, the way we check to see if the nft is within the tree is by the witness        

  const nftRoot = witness.calculateRoot(Poseidon.hash(NFT.toFields(nft)))

  // check if the nft is in the tree, if it is not in the tree, the transaction will fail and the state will not be updated

   nftRoot.assertEquals(treeRoot)

  //if the nft is in the tree then the nft can be voted on
  nft.vote()

  //update the tree with the new nft hash
  const newNftRoot = witness.calculateRoot(Poseidon.hash(NFT.toFields(nft))
this.treeRoot.set(newNftRoot)

        this.voters.set(this.voters.getAndRequireEquals().add(1)) //we want to increment the number of voters after a vote has been cast

//we are going to check if the nft has more votes than the current winning nft then we will update the winning nft

  const winningNft = this.winningNft.getAndRequireEquals()
  const winningVotes = this.winningVotes.getAndRequireEquals()

  const newWinningNft = Provable.if(winningVotes.lessThan(nft.nftVotes), nft.nftName, winningNft)
  const newWinningVotes = Provable.if(winningVotes.lessThan(nft.nftVotes), nft.nftVotes, winningVotes)

this.winningNft.set(newWinningNft)
this.winningVotes.set(newWinningVotes)
  }
}

This method verifies, votes, and updates the winning NFT on the Merkle tree.

1. First, we verify the nft in the tree by retrieving the Merkle root, hashing with Poseidon, and checking if it exists in the tree via a Merkle witness.

2. We cast the Vote & Update Tree, If it is valid, we call nft.vote(), and update the Merkle root, setting a new root in this.treeRoot.

3. We increase the voter count by increasing voters to track the number of participants.

4. Finally we update the winning NFT, using Provable.if to compare votes, and update winningNft and winningVotes, if the new NFT has more votes.

• Poseidon: Poseidon is a hash function for zero knowledge-proof systems, we use it because it only stores field variables but since the nft is a struct we have to pass it as fields

With this, we have our smart contract ready, and now we can test our smart contract.

We'll navigate to our Voting.test.ts file and start adding some code, the first thing we need to do is import the necessary packages and files

import { AccountUpdate, CircuitString, Field, MerkleTree, Mina, Poseidon, PrivateKey, PublicKey } from 'o1js';
import { treeHeight, NFT, MerkleWitness4, Voting } from './Voting';

Then we set up the tests with

let proofsEnabled = false;

function createNFT(nftName: string, nftCreator: string) {
   const nft = new NFT({
        nftName: Poseidon.hash(CircuitString.fromString(nftName).values.map(char => char.toField())),
        nftCreator: Poseidon.hash(CircuitString.fromString(nftCreator).values.map(char => char.toField()),
        nftVotes: Field(0)
    });
    return nft;
}

function createTree(): MerkleTree {
    const tree = new MerkleTree(treeHeight);

    const nft0 = createNFT("nft0", "creator0");
    const nft1 = createNFT("nft1", "creator1");
    const nft2 = createNFT("nft2", "creator2");
    const nft3 = createNFT("nft3", "creator3");

    tree.setLeaf(0n, Poseidon.hash(NFT.toFields(nft0)));
    tree.setLeaf(1n, Poseidon.hash(NFT.toFields(nft1)));
    tree.setLeaf(2n, Poseidon.hash(NFT.toFields(nft2)));
    tree.setLeaf(3n, Poseidon.hash(NFT.toFields(nft3)));

    return tree;
}


describe('Voting', () => {
    let deployerAccount: Mina.TestPublicKey,
    deployerKey: PrivateKey,
    senderAccount: Mina.TestPublicKey,
    senderKey: PrivateKey,
    zkAppAddress: PublicKey,
    zkAppPrivateKey: PrivateKey,
    zkApp: Voting,
    tree: MerkleTree;

    beforeAll(async () => {
        if (proofsEnabled) await Voting.compile();
    });

    beforeEach(async () => {
        const Local = await Mina.LocalBlockchain({ proofsEnabled });
        Mina.setActiveInstance(Local);
        [deployerAccount, senderAccount] = Local.testAccounts;
        deployerKey = deployerAccount.key;
        senderKey = senderAccount.key;

        zkAppPrivateKey = PrivateKey.random();
        zkAppAddress = zkAppPrivateKey.toPublicKey();
        zkApp = new Voting(zkAppAddress);
        tree = createTree();
    });

async function localDeploy() {
        const txn = await Mina.transaction(deployerAccount, async () => {
            AccountUpdate.fundNewAccount(deployerAccount);
            await zkApp.deploy();
            await zkApp.initState(tree.getRoot());
        });
        await txn.prove();
        await txn.sign([deployerKey, zkAppPrivateKey]).send();
    }
})

In this test setup, we use the createTree function to generate a Merkle tree with dummy data for the NFTs that we will vote on.

The proofsEnabled flag controls whether zero-knowledge proofs will be generated. We set it to false during the initial stages of development to speed up the process.

We define the localDeploy function, which is executed before each test suite to deploy the smart contract and initialize its state."

The describe block in the test is used to group the related tests, providing a clear structure for our testing process.

For our first test suite, we will generate and deploy the contract

it('generates and deploys the contract', async () => {
        await localDeploy();
        const treeRoot = zkApp.treeRoot.get();
        expect(treeRoot).toEqual(tree.getRoot());
    });

Our next step is to check if the votes are incremented correctly

 it('votes on the Nft are incremented correctly', async () => {
        await localDeploy();

        const nft1 = createNFT("nft1", "creator1");
        nft1.vote();
        expect(nft1.nftVotes).toEqual(Field(1));
    });

Now, let's test whether the voting process for an NFT works correctly.

it('correctly votes for NFT', async () => {
        await localDeploy();

        const nft1 = createNFT("nft1", "creator1");
        const witness = new MerkleWitness4(tree.getWitness(1n));

        const txn = await Mina.transaction(senderAccount, async () => {
            zkApp.voteForNft(nft1, witness);
        });

        await txn.prove();
        await txn.sign([senderKey]).send();

        const voters = zkApp.voters.get();
        expect(voters).toEqual(Field(1));

        const winningNft = zkApp.winningNft.get();
        expect(winningNft).toEqual(nft1.nftName);

        const winningVotes = zkApp.winningVotes.get();
        expect(winningVotes).toEqual(Field(1));

        nft1.vote();
        tree.setLeaf(1n, Poseidon.hash(NFT.toFields(nft1)));
        const treeRoot = zkApp.treeRoot.get();
        expect(treeRoot).toEqual(tree.getRoot());
    });

We've just verified that the NFT data is present in the tree using the witness, allowing us to correctly cast a vote. Next, we'll test a scenario where we attempt to vote on an NFT not present in the tree, to observe the system's behavior when provided with incorrect data.

it('does not allow voting for song not in the tree', async () => {
        await localDeploy();

        const nft12 = createNFT("nft12", "creator1");
        const witness = new MerkleWitness4(tree.getWitness(1n));

        await expect(async () => {
            const txn = await Mina.transaction(senderAccount, async () => {
                zkApp.voteForNft(nft12, witness);
            });

            await txn.prove();
            await txn.sign([senderKey]).send();
        }).rejects.toThrow();
    });

In the final test suite, we'll cast votes for multiple NFTs, including voting for one twice, to determine the winner.

it('correctly votes for two songs and chooses the right winner', async () => {
        await localDeploy();
        const nft1 = createNFT("nft1", "creator1");
        const nft2 = createNFT("nft2", "creator2");

        let witness = new MerkleWitness4(tree.getWitness(0n));
        let txn = await Mina.transaction(senderAccount, async () => {
            zkApp.voteForNft(nft1, witness);
        });
        await txn.prove();
        await txn.sign([senderKey]).send();
        nft1.vote();
        tree.setLeaf(0n, Poseidon.hash(NFT.toFields(nft1)));

        let witness2 = new MerkleWitness4(tree.getWitness(1n));
        txn = await Mina.transaction(senderAccount, async () => {
            zkApp.voteForNft(nft2, witness2);
        });
        await txn.prove();
        await txn.sign([senderKey]).send();
        nft2.vote();
        tree.setLeaf(1n, Poseidon.hash(NFT.toFields(nft2)));

        witness = new MerkleWitness4(tree.getWitness(0n));
        txn = await Mina.transaction(senderAccount, async () => {
            zkApp.voteForNft(nft1, witness);
        });
        await txn.prove();
        await txn.sign([senderKey]).send();
        nft1.vote();
        tree.setLeaf(0n, Poseidon.hash(NFT.toFields(nft1)));

        const voters = zkApp.voters.get();
        expect(voters).toEqual(Field(3));

        const winningSong = zkApp.winningNft.get();
        expect(winningSong).toEqual(nft1.nftName);

        const winningVotes = zkApp.winningVotes.get();
        expect(winningVotes).toEqual(Field(3));

        const treeRoot = zkApp.treeRoot.get();
        expect(treeRoot).toEqual(tree.getRoot());
    });

This finalizes our test, after this is done we run the tests using any of these commands

//run all tests

npm run test

or

//run in watch mode

npm run testw

After running our tests, we can deploy our smart contract.

To deploy we first have to config the zkApp, we will go to our terminal and run this command

zk config

It asks the following questions to configure your zkApp

• Create a name: Enter any desired name for your application.
• Choose the target network: Select testnet for testing purposes.
• Set the Mina GraphQL API URL to deploy to: Use https://api.minascan.io/node/devnet/v1/graphql
• Set transaction fee to use when deploying: Set the fee to 1

.

• Choose an account to pay transaction fee: Choose Create a new fee payer key pair.
• Create an alias for this account: Assign a name to the feepayer account (this can be anything).

This is what we get after all the necessary fields are filled

Ensure to fund your account with the provided faucet link, when you open the link you should have something like this. It is necessary to fund your account to ensure the deployment is successful

After we have this completed, we run the command zk deploy voting

zk deploy voting

A single question will be asked to confirm the deployment transaction and we just have to enter yes, and we will have feedback that looks like this which also holds the deployment link

Conclusion

By leveraging Merkle trees, zkApps can handle large-scale data efficiently while keeping Mina’s blockchain lightweight and succinctness, keeping data off-chain while still allowing secure verification.

Beyond NFT voting, they can be used for private identity verification, membership proofs, leaderboards, and decentralized reputation systems.
With this knowledge, go forth and build amazing applications that are powered by the efficiency of Mina's succinct blockchain.