Recursion

Kimchi, the custom proof system that backs o1js, supports arbitrary infinite recursive proof construction of circuits through integration with the Pickles recursive system. Mina Protocol is the only blockchain that offers infinite recursion.

Recursion is an incredibly powerful primitive that has a wide-array of uses. For example:

1. Mina uses linear recursive proofs to compress the blockchain, an infinitely growing structure, down to a constant size.
2. Mina also uses "rollup-like" tree-based recursive proofs to, in parallel, compress transactions within blocks down to a constant size.
3. An app-specific rollup like a Mastermind game that uses linear recursive proofs to progress the state machine of the application without needing to sync back to the game.
4. App-specific rollups can use recursion to communicate to each other, like app chains using Inter-Blockchain Communication protocol (IBC) (Cosmos) or parachains using Cross-Chain Virtual Machine (XVM) to send messages.

More generally, you can use recursion to verify any zero knowledge program as part of your zkApp.

ZkProgram Overview

note

zkProgram is available as a top-level import. Experimental.ZkProgram is deprecated. If you are experiencing issues with zkProgram, be sure to update o1js to the latest version.

In o1js, you can use ZkProgram() to define the steps of a recursive program. Like SmartContract() methods, ZkProgram() methods execute off-chain.

After performing the desired recursive steps, you can settle the interaction on Mina's blockchain by embedding ZkProgram within a SmartContract method that verifies the underlying proof of execution and extracts the output that can be used elsewhere in the method (like storing the output in app-state, for example).

Similar to methods within the SmartContract class, inputs to ZkProgram are private by default and are never seen by the Mina network. Unlike SmartContract methods, as the zkApp developer you choose the shape of the public input to all methods within a ZkProgram.

Example: Recursively verify a simple program in a zkApp

This simple example has only one method that proves the public input it received is zero:

import { Field, ZkProgram } from 'o1js';

const SimpleProgram = ZkProgram({
  name: "simple-program-example",
  publicInput: Field,

  methods: {
   run: {
      privateInputs: [],

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

To compile this program:

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

Now, you can use it to create a proof:

const proof = await SimpleProgram.run(Field(0));

To verify this proof from within any method of your SmartContract class:

@method async foo(proof: SimpleProgram.Proof) {
  proof.verify().assertTrue();
  const output: Field = proof.value;
  // ...the rest of our method.
  // For example, storing the output of the execution of the program we've
  // proven as on-chain state, if desired.
}

In this example, foo is taking the SimpleProgram proof as a private argument to the method, verifying that the execution was valid, and then using the output.

Example: Recursively verify a linear recursive program in a zkApp

This example shows a recursive ZkProgram that you can use to create recursive zero knowledge proofs. In other proof systems, this is extremely difficult to construct (if it is even possible). In o1js, you can describe a recursive ZkProgram with a simple recursive function.

This program describes a recursive operation of adding one repeatedly to a number:

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

const AddOne = ZkProgram({
  name: "add-one-example",
  publicInput: Field,

  methods: {
    baseCase: {
      privateInputs: [],

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

    step: {
      privateInputs: [SelfProof],

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

Note that this example recursively depends on the older proof as a private argument to your method.

First, compile this program and make the base proof as before:

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

const proof = await AddOne.baseCase(Field(0));

This time, use this proof as input to recursively add one again:

const proof1 = await AddOne.step(Field(1), proof);

Repeat this as many times as you want:

const proof2 = await AddOne.step(Field(2), proof1);

Finally, verify the proof from within a SmartContract like the earlier example:

@method async foo(proof: Proof) {
  proof.verify().assertTrue();
  /* ... the rest of our method
   * For example using the total value as the fee for some other transaction. */
}

Example: Recursively verify a tree-based recursive program in a zkApp

Tree recursion is rarely seen in other proof systems and zk toolkits. Tree recursion is used internally within Mina as part of its decentralized prover and sequencing mechanism for rollups, so it's supported very robustly by Kimchi.

This example program describes a very simple rollup for adding numbers:

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

let RollupAdd = ZkProgram({
  name: "rollup-add-example",
  publicInput: Field,

  methods: {
    baseCase: {
      privateInputs: [],

      async method(publicInput: Field) { },
    },

    step: {
      privateInputs: [SelfProof, SelfProof],

      async method(
        publicInput: Field,
        left: SelfProof<Field, void>,
        right: SelfProof<Field, void>
      ) {
        left.verify();
        right.verify();
        // assert that the left and right equal this input
        left.publicInput.add(right.publicInput).assertEquals(publicInput);
      },
    },
  },
});

Bonus: Using ZkPrograms outside of zkApps

You can also use ZkProgram directly to prove and verify arbitrary zero knowledge programs (also known as circuits):

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

const proof = await MyProgram.base(Field(0));

Now you can directly verify a JSON-encoded version of the proof to get back a boolean value that tells you if the proof is valid:

import { verify } from 'o1js';

const ok = await verify(proof.toJSON(), verificationKey);