# Tutorial 9: Recursion > Use recursion on-chain and off-chain with zkApps. Learn about use cases to create high-throughput applications, use larger proof sizes and create multi-party zero knowledge proof constructions. Canonical URL: https://docs.minaprotocol.com/zkapps/tutorials/recursion One of the most powerful features of zkApps is [recursion](https://docs.o1labs.org/o1js/advanced-concepts/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](https://docs.o1labs.org/o1js/api-reference/functions/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 [Add.ts](https://github.com/MinaProtocol/docs2/blob/main/examples/zkapps/09-recursion/src/Add.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](/zkapps/tutorials#prerequisites) for zkApp Developer Tutorials. This tutorial uses o1js 3.0.0. o1js 3.0.0 needs Node.js 22.19.5 or later (`engines.node` in the o1js package). In particular, make sure you have the zkApp CLI installed: ```sh $ 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. 1. Now, create a project using the `zk project` command: ```sh $ 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. 1. 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: ```ts title="src/index.ts" 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](https://github.com/MinaProtocol/docs2/blob/main/examples/zkapps/09-recursion/src/Add.ts) example file. ### Copy the example Use the existing code in the [Add.ts](https://github.com/MinaProtocol/docs2/blob/main/examples/zkapps/09-recursion/src/Add.ts) example file. 1. First, open the [Add.ts](https://github.com/MinaProtocol/docs2/blob/main/examples/zkapps/09-recursion/src/Add.ts) example file. 1. 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. ::: ```ts title="src/Add.ts" 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. - `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. The `src/main.ts` file that runs the ZkProgram also imports `verify`. The `verify()` function verifies a proof against the verification key that `compile()` returns. ### 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. This block is the start of the program: the `init()` method in the `methods` object. Add the next two methods after `init`, in the same `methods` object. The example file then closes the `methods` object and the `ZkProgram()` call. ```ts title="src/Add.ts" 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: ```ts title="src/Add.ts" addNumber: { privateInputs: [SelfProof, Field], async method( newState: Field, earlierProof: SelfProof, numberToAdd: Field ) { earlierProof.verify(); newState.assertEquals(earlierProof.publicInput.add(numberToAdd)); }, }, ``` Use recursion to combine two proofs: ```ts title="src/Add.ts" add: { privateInputs: [SelfProof, SelfProof], async method( newState: Field, earlierProof1: SelfProof, earlierProof2: SelfProof ) { earlierProof1.verify(); earlierProof2.verify(); newState.assertEquals( earlierProof1.publicInput.add(earlierProof2.publicInput) ); }, }, ``` To use ZkProgram, compile it and then call methods on it: ```ts title="src/main.ts" import { Field, verify } from 'o1js'; import { Add } from './Add.js'; 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](https://github.com/MinaProtocol/docs2/blob/main/examples/zkapps/09-recursion/src/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](https://github.com/MinaProtocol/docs2/blob/main/examples/zkapps/09-recursion/src/rollup.ts) example file. A community-contributed implementation distributes compute over AWS instances in this [proof_aggregator](https://github.com/Trivo25/proof_aggregator) example. ### Set up ZkProgram The public input of the rollup ZkProgram is a `RollupState`. A `RollupState` holds two Merkle roots: the root before the transactions (`initialRoot`) and the root after them (`latestRoot`). ```ts title="src/rollup.ts" export 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, }); } 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); } } ``` The `Rollup` ZkProgram has two methods, `oneStep()` and `merge()`: ```ts title="src/rollup.ts" export const Rollup = ZkProgram({ name: 'rollup', publicInput: RollupState, methods: { oneStep: { privateInputs: [Field, Field, Field, Field, Field, MerkleMapWitness], async 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); }, }, merge: { privateInputs: [SelfProof, SelfProof], async method( newState: RollupState, rollup1proof: SelfProof, rollup2proof: SelfProof ) { rollup1proof.verify(); rollup2proof.verify(); rollup2proof.publicInput.initialRoot.assertEquals( rollup1proof.publicInput.latestRoot ); rollup1proof.publicInput.initialRoot.assertEquals(newState.initialRoot); rollup2proof.publicInput.latestRoot.assertEquals(newState.latestRoot); }, }, }, }); export let RollupProof_ = ZkProgram.Proof(Rollup); export class RollupProof extends RollupProof_ {} ``` 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 `merge()` verifies the two proofs. It asserts that the second proof starts at the root where the first proof ends, that the new state starts at the `initialRoot` of the first proof, and that the new state ends at the `latestRoot` of the second proof. ### Consume the proofs To consume these proofs in a smart contract (`SmartContract`) that uses the recursive proof to update its internal state: ```ts title="src/rollup.ts" export class RollupContract extends SmartContract { @state(Field) state = State(); async deploy(args: DeployArgs) { await super.deploy(args); this.account.permissions.set({ ...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 Look again at `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. ```ts title="src/rollup.ts" 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, }); } ``` ```ts title="src/rollup.ts" oneStep: { privateInputs: [Field, Field, Field, Field, Field, MerkleMapWitness], async 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 `oneStep()` method returns a proof that acts as the leaf in a tree of recursive proofs. (`createOneStep()` returns the `RollupState` that the proof is about.) 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 ## Test it Build the project, then run `main.ts`: ```sh npm run build node build/src/main.js ``` It prints: ``` compiling... making proof 0 making proof 1 making proof 2 verifying proof 2 proof 2 data 4 ok true ``` The voting example and the rollup example run the same way. They make real proofs, so each run takes several minutes. ```sh node build/src/vote.js ``` ``` compiling... making proof 0 making proof 1 making proof 2 verifying proof 2 1 1 ok true ``` `1 1` is one vote for and one vote against. ```sh node build/src/rollup.js ``` ``` compiling... generating transition information making first set of proofs merging proofs verifying rollup 16681890329296260524727674720599141567461542680012070463181990759791426893085 ok true ``` The long number is the `latestRoot` of the merged proof: the root of the MerkleMap after the four transitions in `main()`. The example project in this repository carries a test suite for the code on this page: ```sh cd examples/zkapps/09-recursion npm install npm test ``` It asserts what this page claims: - `Add` makes real proofs. Proof 0 is for `0`, proof 1 adds `4` to proof 0, and proof 2 combines proof 1 and proof 0 into `4`. Proof 2 verifies with `verify()`, so `main()` prints `ok true`. - A proof of `4` that claims `5` does **not** verify, and neither does a dummy proof. - `init` **rejects** a state that is not `0`. `addNumber` and `add` **reject** a new state that is not the sum. After a rejection, the earlier proofs still verify. - `Rollup` merges one proof per transition into one proof that goes from the root of the empty map to the latest root. It **rejects** a step with a wrong increment or a wrong key, two proofs in the wrong order, and a merge that claims a different latest root. - `RollupContract` moves its state to the latest root of a rollup proof. It **rejects** a proof that does not start at the stored root, and the same proof a second time. The state does not change. - `Vote` counts one vote for and one vote against. It **rejects** a second vote from the same voter, a voter who is not in the voters tree, and a new state that counts a vote twice. A ZkProgram with proofs off makes dummy proofs, and `earlierProof.verify()` checks nothing, so the `Add` tests make real proofs. They compile the ZkProgram once and make the three proofs once, which takes several minutes. The `Rollup` and `Vote` tests turn proofs off: every assertion still runs, and each of these test files takes about one minute. ## 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](/zkapps/tutorials/account-updates) to learn about account updates, the underlying structure of zkApps, and how they enable permissions, preconditions, and composability.