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 following example code for the ZkProgram tutorial is provided in the main.ts file on GitHub. While you're there, give the /docs2 repository a star so that other zk developers can learn to build a zkApp!

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.

1. Create or change to a directory where you have write privileges.

2. Now, create a project using the zk project command:

   $ zk project 09-recursion

   As you learned in earlier tutorials, the zk project command creates the 09-recursion directory that contains the scaffolding for your project.

3. Change into the 09-recursion directory.

Like all projects, you run zk 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

Like earlier tutorials, you can prepare your project by deleting the default files that come with the new project and creating a smart contract called Add.

Open src/index.ts in a text editor and import the Add smart contract, like:

import { Add } from './Add.js';
export { Add };

Write the ZkProgram

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

A final version of the smart contract is provided in the Add.ts example file.

Copy the example

Use the existing code in the Add.ts example file.

1. First, open the Add.ts example file.
2. Copy the file's entire contents into your project src/Add.ts file.

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.

info

import { Field, SelfProof, ZkProgram, verify } 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.
• SelfProof: The class in o1js that extends the Proof class and allows you to pass in a proof of a circuit in one of its own methods.
• 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.
• verify: Verifies the signature using a message and the corresponding PublicKey.

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,

  methods: {
    init: {
      privateInputs: [],

      async method(state: Field) {
        state.assertEquals(Field(0));
      },
    },
  },
});

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

   addNumber: {
     privateInputs: [SelfProof, Field],

     async method(
       newState: Field,
       earlierProof: SelfProof<Field, void>,
       numberToAdd: Field
     ) {
       earlierProof.verify();
       newState.assertEquals(earlierProof.publicInput.add(numberToAdd));
     },
   },

Use recursion to combine two proofs:

   add: {
     privateInputs: [SelfProof, SelfProof],

     async method(
       newState: Field,
       earlierProof1: SelfProof<Field, void>,
       earlierProof2: SelfProof<Field, void>
     ) {
       earlierProof1.verify();
       earlierProof2.verify();
       newState.assertEquals(
         earlierProof1.publicInput.add(earlierProof2.publicInput)
       );
     },
   },

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

async function main() {
  console.log('compiling...');

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

  console.log('making proof 0');

  const { proof: proof0 } = await Add.init(Field(0));

  console.log('making proof 1');

  const { proof: proof1 } = await Add.addNumber(Field(4), proof0, Field(4));

  console.log('making proof 2');

  const { proof: 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);
}

main();

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 async initStateRoot(stateRoot: Field) {
    this.state.set(stateRoot);
  }

  @method async update(rollupStateProof: RollupProof) {
    const currentState = this.state.get();
    this.state.requireEquals(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.