info

zkApp programmability is not yet available on the Mina Mainnet. You can get started now by deploying zkApps to the Berkeley Testnet.

Tutorial 9: Recursion

One of the most powerful features of zkApps is recursion.

With recursion, you can realize composability between zero knowledge proofs. Recursion unlocks many powerful technical abilities, such as creating high-throughput applications, creating proofs of large computations, and constructing multi-party proofs.

Scaling Throughput with zkRollups and App Chains

Verifying large amounts of information is usually challenging for blockchains. With zero knowledge proofs (ZKPs), and particularly recursive ZKPs, this becomes far easier.

By leveraging recursive verification, it is possible to easily construct zkRollups and app chains. This tutorial provides an example of a simple zkRollup.

Recursive composition gives you the flexibility to handle live demand by letting you choose between a high tree height (higher throughput, but logarithmically slower latency) and a lower tree height (lower throughput, but faster latency). You can modify the depth of the tree to handle whatever traffic is present on the network while still offering optimal latency to commit transactions back to the chain.

For an example of an app chain, one could imagine an on-chain trading pair that uses an order book. Rolling up the transactions for the application with zero knowledge proofs lets the app handle the expensive computations of keeping buy and sell orders sorted while still posting complete verification to the chain.

This tutorial guides you through a review of a simple zkRollup example that can be used to implement a zkRollup or an app chain.

Scaling Proof Size

Recursive ZKPs allow you to construct very large transactions that wouldn't otherwise be possible.

For example, recursive ZKPs can be used to prove the output of a machine learning (ML) model to prove an inference is genuinely generated by a model or, for a more computationally intensive case, to verify that a model has been trained on a particular dataset.

Off-chain, multi-party proof construction

Recursive ZKPs also make it easy to allow multiple parties to construct transactions. One or more parties can recursively update a ZKP and its associated public state to accomplish off-chain proof construction. When the multi-party stage is completed, that state and its proof can then be sent as part of an on-chain transaction or used as part of an off-chain application leveraging ZKPs.

ZkProgram Example

You build recursive zkApps with ZkProgram, the o1js general purpose API for creating zero knowledge proofs. A ZkProgram is similar to zkApp smart contracts but isn't tied to an on-chain account.

Proofs generated using a ZkProgram can be passed into zkApp smart contracts for them to verify recursively. They can even be passed recursively into their own functions for off-chain recursive composition.

The full source code for the following ZkProgram tutorial is provided in the main.ts directory on GitHub. While you're there, give the /docs2 repository a star so that other zk developers can learn to build a zkApp!

info

To prevent copying line numbers and command prompts as shown in the examples, use the copy code to clipboard button that appears at the top right of the snippet box when you hover over it.

Prerequisites

Ensure your environment meets the Prerequisites for zkApp Developer Tutorials.

In particular, make sure you have the zkApp CLI installed:

$ npm install -g zkapp-cli

Create a new project

Now that you have the tooling installed, you can start building your application.

Create or change to a directory where you have write privileges.
Now, create a project using the zk project command:

$ zk project 09-recursion

The zk project command has the ability to scaffold the UI for your project. For this tutorial, select none:

? Create an accompanying UI project too? …
  next
  svelte
  nuxt
  empty
❯ none

The expected output is:

✔ Create an accompanying UI project too? · none
✔ UI: Set up project
✔ Initialize Git repo
✔ Set up project
✔ NPM install
✔ NPM build contract
✔ Set project name
✔ Git init commit

Success!

Next steps:
  cd 09-recursion
  git remote add origin <your-repo-url>
  git push -u origin main

The zk project command creates the 09-recursion directory that contains the scaffolding for your project, including tools such as the Prettier code formatting tool, the ESLint static code analysis tool, and the Jest JavaScript testing framework.

Change into the 09-recursion directory and list the contents:

$ cd 09-recursion
$ ls

The output shows these results:

LICENSE
README.md
babel.config.cjs
build
config.json
jest-resolver.cjs
jest.config.js
keys
node_modules
package-lock.json
package.json
src
tsconfig.json

For this tutorial, you run commands from the root of the 09-recursion directory as you work in the src directory on files that contain the TypeScript code for the smart contract. Each time you make updates, then build or deploy, the TypeScript code is compiled into JavaScript in the build directory.

Prepare the project

Start by deleting the default files that come with the new project.

To delete the old files:

$ rm src/Add.ts
$ rm src/Add.test.ts
$ rm src/interact.ts

Now, create the new files for your project:

$ zk file src/Add
$ touch src/main.ts

The zk file command created the src/Add.ts and src/Add.test.ts test files.
However, this tutorial does not include writing tests, so you just use the main.ts file as a script to interact with the smart contract and observe how it works.

In later tutorials, you learn how to interact with a smart contract from the browser, like a typical end user.

Now, open src/index.ts in a text editor and change it to look like:

1 import { Add } from './Add.js';
2
3 export { Add };

The src/index.ts file contains all of the exports you want to make available for consumption from outside your smart contract project, such as from a UI.

Write the ZkProgram

Now, the fun part! Write your smart contract in the src/Add.ts file.

Line numbers are provided for convenience. A final version of the smart contract is provided in the Add.ts example file.

This part of the tutorial walks you through the Add ZkProgram code already completed in the src/Add.ts example file.

Copy the example

This tutorial describes each part of the completed code in the Add.ts example file.

First, open the Add.ts example file.
Copy the entire contents of the file into your ZkProgram in the src/Add.ts file.

Now you are ready to review the imports in the ZkProgram.

Imports

The import statement brings in other packages and dependencies to use in your ZkProgram.

info

All functions used inside a ZkProgram must operate on o1js compatible data types: Field types and other types built on top of Field types.

1 import { Field, SelfProof, ZkProgram } from 'o1js';

These items are:

Field: The native number type in o1js. You can think of Field elements as unsigned integers. Field elements are the most basic type in o1js. All other o1js-compatible types are built on top of Field elements.
ZkProgram: The o1js general purpose API for creating zero knowledge proofs. A ZkProgram is similar to zkApp smart contracts but isn't tied to an on-chain account.

ZkProgram

To create a ZkProgram, start with the init() method.

For each method, declare the inputs it will receive.
The first argument of a ZkProgram method is always the state of the ZkProgram, named publicInput since it is public.

export const Add = ZkProgram({
name: 'add-example',
publicInput: Field,
6
methods: {
  init: {
    privateInputs: [],
10
    method(state: Field) {
      state.assertEquals(Field(0));
    },
  },
},
});
17

Add another method that takes an existing proof, adds a new number to it, and produces a new proof:

15
  addNumber: {
    privateInputs: [SelfProof, Field],
18
    method(
      newState: Field,
      earlierProof: SelfProof<Field, void>,
      numberToAdd: Field
    ) {
      earlierProof.verify();
      newState.assertEquals(earlierProof.publicInput.add(numberToAdd));
    },
  },
},
});

Use recursion to combine two proofs:

28
  add: {
    privateInputs: [SelfProof, SelfProof],
31
    method(
      newState: Field,
      earlierProof1: SelfProof<Field, void>,
      earlierProof2: SelfProof<Field, void>
    ) {
      earlierProof1.verify();
      earlierProof2.verify();
      newState.assertEquals(
        earlierProof1.publicInput.add(earlierProof2.publicInput)
      );
    },
  },
},
});

Interact with a smart contract

Next, write a script that interacts with your smart contract. As before, the complete main.ts example file is provided. Follow these steps to build the main.ts file so you can interact with the smart contract.

To use ZkProgram, compile it and then call methods on it:

  console.log('compiling...');

  const { verificationKey } = await Add.compile();

  console.log('making proof 0')

  const proof0 = await Add.init(Field(0));

  console.log('making proof 1')

  const proof1 = await Add.addNumber(Field(4), proof0, Field(4));

  console.log('making proof 2')

  const proof2 = await Add.add(Field(4), proof1, proof0);

  console.log('verifying proof 2');
  console.log('proof 2 data', proof2.publicInput.toString());

  const ok = await verify(proof2.toJSON(), verificationKey);
  console.log('ok', ok);

Verification of the proof can occur off-chain using the verify() method. This is useful for applications where you want to prove something to an off-chain entity.

Voting Example

Another example of off-chain multi-party proof construction with recursive ZKPs is provided in the vote.ts example file.

Using ZkProgram in Smart Contracts

After you build a recursive ZKP, use a method on a smart contract to settle the proof to the Mina blockchain.

Build a zkRollup to use ZkProgram from a smart contract.

This example code builds a zkRollup to operate over a MerkleMap of accounts that each store a number. The update rule increments the value stored at an account - though you could imagine using more substantial rules to implement a particular application.

The zkApp will store the Merkle root of this MerkleMap of accounts on chain. Updates occur only when authorized by a recursive zero knowledge proof generated by the ZkProgram.

This zkRollup design is flexible to how much compute is being demanded of it (for latency) and allows it to scale to arbitrary numbers of proofs (for throughput).

On a single machine, the example code does not offer a high throughput. However, you can achieve very high throughputs by switching the mapreduce here for a mapreduce that runs over tens or hundreds of machines. In fact, you can achieve any level of throughput as long as you're willing to incur log(N) latency when constructing the proof of N transactions.

The following code for the ZkProgram part of a rollup is provided in the rollup.ts example file.

A community-contributed implementation distributes compute over AWS instances in this proof_aggregator example.

Set up ZkProgram

class RollupState extends Struct({
  initialRoot: Field,
  latestRoot: Field,
}) { 

  static createOneStep(
    initialRoot: Field, 
    latestRoot: Field, 
    key: Field, 
    currentValue: Field,
    incrementAmount: Field, 
    merkleMapWitness: MerkleMapWitness,
  ) {
    const [ witnessRootBefore, witnessKey ] = merkleMapWitness.computeRootAndKey(currentValue);
    initialRoot.assertEquals(witnessRootBefore);
    witnessKey.assertEquals(key);
    const [ witnessRootAfter, _ ] = merkleMapWitness.computeRootAndKey(currentValue.add(incrementAmount));
    latestRoot.assertEquals(witnessRootAfter);

    return new RollupState({
      initialRoot,
      latestRoot
    });
  }

A proof generated by the merge() method indicates there is a valid sequence of transactions (for example, the applications of oneStep):

Get from an initialRoot, the root of a MerkleMap
To a latestRoot root of the Merkle map after transactions are applied

Consume the proofs

To consume these proofs in a smart contract (SmartContract) that uses the recursive proof to update its internal state:

class RollupContract extends SmartContract {
  @state(Field) state = State<Field>();

  deploy(args: DeployArgs) {
    super.deploy(args);
    this.setPermissions({
      ...Permissions.default(),
      editState: Permissions.proofOrSignature(),
    });
  }

  @method initStateRoot(stateRoot: Field) {
    this.state.set(stateRoot);
  }

  @method update(rollupStateProof: RollupProof) {
    const currentState = this.state.get();
    this.state.assertEquals(currentState);

    rollupStateProof.publicInput.initialRoot.assertEquals(currentState);

    rollupStateProof.verify();

    this.state.set(rollupStateProof.publicInput.latestRoot);
  }
}

Verify the value at account is incremented

Fill in the previous methods, particularly oneStep() and createOneStep().

This step of the rollup checks that the value at an account was incremented by a particular amount.

The code computes an updated state inside the recursive SNARK by calling RollupState.createOneStep().
Then, asserting that the new state of the recursive SNARK is equivalent to the computed state.
Inside createOneStep(), a single step of the rollup is created.

class RollupState extends Struct({
...
}) {
  static createOneStep(
    initialRoot: Field,
    latestRoot: Field,
    key: Field,
    currentValue: Field,
    incrementAmount: Field,
    merkleMapWitness: MerkleMapWitness,
  ) {
    const [ witnessRootBefore, witnessKey ] = 
      merkleMapWitness.computeRootAndKey(currentValue);
    initialRoot.assertEquals(witnessRootBefore);
    witnessKey.assertEquals(key);
    const [ witnessRootAfter, _ ] = 
      merkleMapWitness.computeRootAndKey(currentValue.add(incrementAmount));
    latestRoot.assertEquals(witnessRootAfter);

    return new RollupState({
      initialRoot,
      latestRoot
    });
  }
...
}

const Rollup = ZkProgram({
  name: "rollup-example",
  publicInput: Field,

  methods: {
    oneStep: {
    privateInputs: [ Field, Field, Field, Field, Field, MerkleMapWitness ],

    method(
      state: RollupState,
      initialRoot: Field,
      latestRoot: Field,
      key: Field,
      currentValue: Field,
      incrementAmount: Field,
      merkleMapWitness: MerkleMapWitness
    ) {
      const computedState = RollupState.createOneStep(
        initialRoot,
        latestRoot,
        key,
        currentValue,
        incrementAmount,
        merkleMapWitness
      );
      RollupState.assertEquals(computedState, state);
    }
},

The createOneStep() method returns a proof that acts as the leaf in a tree of recursive proofs.

To use this rollup, first you construct all of the leafs in parallel then recursively merge these leafs until you get a proof for the entire sequence. This parallel merging gives the high throughput properties for the rollup.

You can reimplement the example code for more substantial functionality, just by changing createOneStep(). For example, to implement a DEX zkRollup that uses an orderbook change the code to:

Update buy/sell orders on an order book
Execute those buy/sell orders
Add a queue of tokens to move to the app chain in the smart contract
Add a queue of tokens to move out of the app chain in the ZkProgram

Conclusion

You learned about:

Recursion with zkApps, both on-chain and off-chain
Potential use cases to create high-throughput applications
Larger proof sizes
Create multi-party proof constructions

Recursive zero knowledge proofs can help you build powerful zkApps.

Check out Tutorial 10: Account Updates to learn about account updates, the underlying structure of zkApps, and how they enable permissions, preconditions, and composability.

Tutorial 9: Recursion

Scaling Throughput with zkRollups and App Chains​

Scaling Proof Size​

Off-chain, multi-party proof construction​

ZkProgram Example​

Prerequisites​

Create a new project​

Prepare the project​

Write the ZkProgram​

Copy the example​

Imports​

ZkProgram​

Interact with a smart contract​

Voting Example​

Using ZkProgram in Smart Contracts​

Set up ZkProgram​

Consume the proofs​

Verify the value at account is incremented​

Conclusion​

Scaling Throughput with zkRollups and App Chains

Scaling Proof Size

Off-chain, multi-party proof construction

ZkProgram Example

Prerequisites

Create a new project

Prepare the project

Write the ZkProgram

Copy the example

Imports

ZkProgram

Interact with a smart contract

Voting Example

Using ZkProgram in Smart Contracts

Set up ZkProgram

Consume the proofs

Verify the value at account is incremented

Conclusion