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 following ZkProgram example code is provided in the main.ts example file.

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.

const Add = ZkProgram({
  name: 'add-example',
  publicInput: Field,

  methods: {
    init: {
      privateInputs: [],

      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 ],

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

Use recursion to combine two proofs:

  add: {
    privateInputs: [ SelfProof, SelfProof ],

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

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.