Skip to main content
info

Please note that zkApp programmability is not yet available on Mina Mainnet, but zkApps can now be deployed to Berkeley Testnet.

Tutorial 9: Recursion

Overview​

One of the most powerful features of zkApps is recursion.

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

Scaling Throughput - zkRollups & App Chains​

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

By leveraging recursive verification, it is possible to easily construct both zkRollups and app chains. We’ll give an example of a simple zkRollup near the end of this tutorial.

Recursive composition even gives us flexibility to handle live demand. Recursive composition gives you flexibility to choose between a high tree height (higher throughput, but logarithmically slower latency), and lower tree height (lower throughput, but faster latency). The depth of the tree can be modified live to handle whatever traffic actually 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 orderbook. Rolling up the transactions for the application with zero knowledge proofs can allow our app to handle the expensive computations of keeping buy and sell orders sorted, while still posting full verification to the chain.

At the end of this tutorial, we’ll review a simple zkRollup example that can be used for implementing a zkRollup or an app chain.

Scaling Proof Size​

Recursive ZKPs also give you the ability to construct very large transactions that wouldn’t otherwise be possible.

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

Off-chain, multi-party proof construction​

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

ZkProgram​

Recursive zkApps are built using ZkProgram. ZkProgram is similar to the zkApp smart contracts we’ve seen before, but aren’t tied to an on-chain account.

Proofs generated via ZkProgram can be passed into zkApp smart contracts (for them to verify recursively), and can even be passed recursively into their own functions for off-chain recursive composition.

To see an example of this, let’s build a simple ZkProgram that uses recursion. You can find the code for this example here.

This example will be in a single file, main.ts. We’ll create our ZkProgram as follows:

const Add = Experimental.ZkProgram({
  publicInput: Field,

    methods: {
      init: {
        privateInputs: [],
        method(state: Field) {
          state.assertEquals(Field(0));
      },
    }
  }
}

We start with one method, init. Note that for each method, we need to declare what inputs it will receive. The first argument of a ZkProgram method is always the state of the ZkProgram, named “publicInput” since it will be public.

Let’s add another method to this:

  addNumber: {
    privateInputs: [SelfProof, Field ],

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

Here, we take an existing proof, and add a new number to it, and produce a new proof.

We can also 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, we need to 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);

Note that 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.

For another example of off-chain multi-party proof construction, see the code here - showing how to do Private Off-Chain voting with Recursive ZKPs.

Using ZkProgram in SmartContracts​

Once we have a recursive ZKP, we may want or need to settle this to the Mina blockchain. We can accomplish this using a method on a SmartContract. To show how to use ZkProgram from a SmartContract, let’s build a zkRollup.

Our zkRollup will operate over a MerkleMap of “accounts”, which each store a number. Our update rule will be to increment 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 Merkle map of accounts on chain. We will allow this to be updated when authorized by a recursive zero knowledge proof generated by our ZkProgram.

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

Let’s discuss the code for the ZkProgram part of a rollup. You can find the full example here.

On one machine, the below code doesn’t offer a high throughput, but by switching the mapreduce used for a mapreduce that runs over tens or hundreds of machines, very high throughputs can be achieved. In fact, any level of throughput can be achieved as long as you’re willing to incur log(N) latency when constructing the proof of N transactions. You can find an implementation that distributes compute over AWS instances here.

To start, let’s set up our ZkProgram:

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

  static createMerged(state1: RollupState, state2: RollupState) {
      return new RollupState({
      initialRoot: state1.initialRoot,
      latestRoot: state2.latestRoot
    });
  }

  static assertEquals(state1: RollupState, state2: RollupState) {
    state1.initialRoot.assertEquals(state2.initialRoot);
    state1.latestRoot.assertEquals(state2.latestRoot);
  }
}

const Rollup = Experimental.ZkProgram({
  publicInput: RollupState,

  methods: {
    oneStep: {
        ...
    },

  merge: {
    privateInputs: [ SelfProof, SelfProof ],

    method(
        newState: RollupState,
        rollup1proof: SelfProof<RollupState>,
        rollup2proof: SelfProof<RollupState>,
    ) {
      rollup1proof.verify(); // A -> B
      rollup2proof.verify(); // B -> C

      rollup1proof.publicInput.initialRoot.assertEquals(newState.initialRoot);

      rollup1proof.publicInput.latestRoot.assertEquals(rollup2proof.publicInput.initialRoot);

      rollup2proof.publicInput.latestRoot.assertEquals(newState.latestRoot);
    }
}

A proof generated by our merge method will indicate there is a valid sequence of transactions (i.e. applications of “oneStep”) that get from an “initialRoot” (the root of a MerkleMap) to a “latestRoot” (root of the Merkle map after transactions are applied).

We will consume these in a SmartContract, which will use 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);
  }
}

Last, is just to fill in the methods above, particularly, oneStep(), and createOneStep(). This single “step” of the rollup will check the value at an “account” was incremented by a particular amount.

To check that the value at an account was incremented by a particular amount, our code computes an updated state - inside the recursive snark - by calling RollupState.createOneStep(). And 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 = Experimental.ZkProgram({
  publicInput: RollupState,

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

createOneStep() returns a proof, that acts as the “leaf” in a tree of recursive proofs. To use this rollup, we would first construct all of the leafs in parallel. Then, we would recursively merge these leafs, until we get a proof for the entire sequence. This parallel merging gives the high throughput properties we’re looking for in a rollup.

And with that last function, we have completed the code for a zkRollup!

Hopefully it’s clear how one could re-implement the above for more substantial functionality, just by changing createOneStep(). For example, to implement a DEX zkRollup that uses an orderbook we could change this to:

  • Updating buy/sell orders on an orderbook
  • Executing those buy/sell orders
  • Adding a “queue” of tokens to move to the app chain in the SmartContract
  • Adding a “queue” of tokens to move out of the app chain in the ZkProgram

Conclusion​

We have finished showing how to use recursion with zkApps, both on and off chain, and discussed their use cases to create high-throughput applications, use larger proof sizes, and create multi-party proof constructions We hope this helps show how recursive zero knowledge proofs can help you build powerful zkApps.

Check out our other tutorials and documentation to learn more about SnarkyJS and zkApps.