# Run Jolt zkVM Verifier on-chain(IC)

The canister is already running on the chain
https://p6xvw-7iaaa-aaaap-aaana-cai.raw.ic0.app/

On April 9th, the A16z crypto team released the fastest zkVM for prover: Jolt, including [code](https://github.com/a16z/jolt), [examples](https://github.com/a16z/jolt/tree/main/examples), [documents](https://jolt.a16zcrypto.com/), [blogs](https://a16zcrypto.com/posts/tags/lasso-jolt), and papers([Lasso](https://eprint.iacr.org/2023/1216.pdf) and [Jolt](https://eprint.iacr.org/2023/1217.pdf)). ~~(The blogs contains a lot of insider information about the zk industry)~~

After running the examples, I tried integrating its verifier into the [IC](https://internetcomputer.org/) Canister.This thing is very meaningful and is actually an official [todo list](https://github.com/a16z/jolt/issues/209).

IC is a high-performance blockchain Layer 1 that can use Rust to write smart contracts and compile them into WASM, and then deploy them to IC. Therefore, choosing IC has a high probability of success.

## Find verifier
I went to look at the fibonacci example and found its verify function:

    let (prove_fib, verify_fib) = guest::build_fib();

Very good, I can get the `verify_fib` in the guest.

When I go to `guest` to view, where is `build_fib`?🧐

#![cfg_attr(feature = "guest", no_std)]
#![no_main]

#[jolt::provable]
fn fib(n: u32) -> u128 {
    let mut a: u128 = 0;
    let mut b: u128 = 1;
    let mut sum: u128;
    for _ in 1..n {
        sum = a + b;
        a = b;
        b = sum;
    }

    b
}

Well, Jolt uses macros to encapsulation and makes the Jolt develop-experience more ergonomic. To figure out the details, I need to expand the macro by `cargo expand -p fibonacci-guest --lib`, the whole code is [here](https://github.com/flyq/jolt_expand):

<details>
<summary><b>expanded code</b></summary>

#![cfg_attr(feature = "guest", no_std)]
#![no_main]

extern crate alloc;

use alloc::rc::Rc;
use alloc::vec::Vec;

use jolt_core::{
    host::Program,
    jolt::vm::{rv32i_vm::RV32IJoltVM, Jolt, JoltPreprocessing},
};
use jolt_sdk::{postcard, Proof, F, G, RV32IM};

pub fn build_fib() -> (impl Fn(u32) -> (u128, Proof), impl Fn(Proof) -> bool) {
    let (program, preprocessing) = preprocess_fib();
    let program = Rc::new(program);
    let preprocessing = Rc::new(preprocessing);
    let program_cp = program.clone();
    let preprocessing_cp = preprocessing.clone();
    let prove_closure = move |n: u32| {
        let program = (*program).clone();
        let preprocessing = (*preprocessing).clone();
        prove_fib(program, preprocessing, n)
    };
    let verify_closure = move |proof: Proof| {
        let _program = (*program_cp).clone();
        let preprocessing = (*preprocessing_cp).clone();
        RV32IJoltVM::verify(preprocessing, proof.proof, proof.commitments).is_ok()
    };
    (prove_closure, verify_closure)
}

pub fn fib(n: u32) -> u128 {
    {
        let mut a: u128 = 0;
        let mut b: u128 = 1;
        let mut sum: u128;
        for _ in 1..n {
            sum = a + b;
            a = b;
            b = sum;
        }
        b
    }
}

pub fn analyze_fib(n: u32) -> (usize, Vec<(RV32IM, usize)>) {
    let mut program = Program::new("guest");
    program.set_input(&n);
    program.trace_analyze()
}

pub fn preprocess_fib() -> (Program, JoltPreprocessing<F, G>) {
    let mut program = Program::new("guest");
    program.set_func("fib");
    let (bytecode, memory_init) = program.decode();
    let preprocessing: JoltPreprocessing<F, G> =
        RV32IJoltVM::preprocess(bytecode, memory_init, 1 << 10, 1 << 10, 1 << 14);
    (program, preprocessing)
}

pub fn prove_fib(
    mut program: Program,
    preprocessing: JoltPreprocessing<F, G>,
    n: u32,
) -> (u128, Proof) {
    program.set_input(&n);
    let (io_device, bytecode_trace, instruction_trace, memory_trace, circuit_flags) =
        program.trace();
    let output_bytes = io_device.outputs.clone();
    let (jolt_proof, jolt_commitments) = RV32IJoltVM::prove(
        io_device,
        bytecode_trace,
        memory_trace,
        instruction_trace,
        circuit_flags,
        preprocessing,
    );
    let ret_val = postcard::from_bytes::<u128>(&output_bytes).unwrap();
    let proof = Proof {
        proof: jolt_proof,
        commitments: jolt_commitments,
    };
    (ret_val, proof)
}

</details>

This code can't be run, because it [attempts to compile standard library](https://jolt.a16zcrypto.com/usage/troubleshooting.html#guest-attempts-to-compile-standard-library). But it provides `preprocessing`, `proof` and `verify` details.

#[derive(CanonicalSerialize, CanonicalDeserialize)]
pub struct Proof {
    pub proof: RV32IJoltProof<F, G>,
    pub commitments: JoltCommitments<G>,
}

let preprocessing: JoltPreprocessing<F, G> =
    RV32IJoltVM::preprocess(bytecode, memory_init, 1 << 20, 1 << 20, 1 << 24);

RV32IJoltVM::verify(preprocessing, proof.proof, proof.commitments).is_ok()

Therefore, the next work is simple. I only need to transfer the `JoltPreprocessing` and `Proof` data to IC Canister, and then call `RV32IJoltVM::verify` to complete the verification.

## Build smart contracts

I implement a canister(smart contract), the project is here:
https://github.com/flyq/jolt_verifier_canister/tree/master/src

The main logic is that the smart contract accepts the serialized bytes of `proof` and `preprocess`, and then deserializes the data internally in the smart contract, and then performs verify.

use ark_bn254::{Fr, G1Projective};
use ark_serialize::CanonicalDeserialize;
use jolt_core::jolt::vm::{rv32i_vm::RV32IJoltVM, Jolt, JoltPreprocessing};
use jolt_sdk::Proof;

pub fn deserialize_proof(proof: &[u8]) -> Proof {
    Proof::deserialize_compressed(proof).unwrap()
}

pub fn deserialize_preprocessing(preprocessing: &[u8]) -> JoltPreprocessing<Fr, G1Projective> {
    JoltPreprocessing::deserialize_compressed(preprocessing).unwrap()
}

pub fn verify(preprocessing: JoltPreprocessing<Fr, G1Projective>, proof: Proof) -> bool {
    RV32IJoltVM::verify(preprocessing, proof.proof, proof.commitments).is_ok()
}

In order to allow jolt to run in the WASM environment, I need to modify some contents of jolt.
- [Delete criterion](https://github.com/flyq/jolt/commit/74b93dfe5f1fa9ad81a9196912a616bcddd1bb46), criterion is a library used for benchmarking in Rust, delete it has no side effects, and it cannot be compiled into Wasm.

  Rayon cannot be used when targeting wasi32. Try disabling default features.
    --> /Users/flyq/.cargo/registry/src/index.crates.io-6f17d22bba15001f/criterion-0.5.1/src/lib.rs:31:1
     |
  31 | compile_error!("Rayon cannot be used when targeting wasi32. Try disabling default features....
     | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

- [Save the proof data to file](https://github.com/flyq/jolt/commit/d66e8c5acc9ec6505e9e787da7182badd94c6884), so that I can use it later.

    let (output, proof) = prove_fib(50);
    proof.save_to_file("./proof.bin").unwrap();
    let is_valid = verify_fib(proof);

## First Try

git clone https://github.com/flyq/jolt.git

cd jolt
    
cargo run --release -p fibonacci

It will run the fibonacci example, and compile the fibonacci program to executable file on the target platform(riscv32), and generate the proof and write the proof to `proof.bin` file, and verify the proof.

compile result will store in here:

/tmp/jolt-guest-linkers:
fibonacci-guest.ld

/tmp/jolt-guest-target-fibonacci-guest-fib:
CACHEDIR.TAG              release                   riscv32i-unknown-none-elf

In order to easily obtain Preprocess from the compilation results and call canister, I constructed a [helper](https://github.com/flyq/jolt_verifier_canister/blob/master/helper/src/main.rs) program.

If you set `Program.elf`, it will read the compilation results according to the `elf path`, otherwise it will try to recompile to riscv.

    let mut program = Program::new("guest");
    program.set_func("fib");
    program.elf = Some(
        PathBuf::from_str(
            "/tmp/jolt-guest-target-fibonacci-guest-fib/riscv32i-unknown-none-elf/release/guest",
        )
        .unwrap(),
    );
    let (bytecode, memory_init) = program.decode();

In short, I easily obtained `bytecode` and `memory_init`, and their sizes are relatively small (less than 2MB), which can meet the size requirements of IC smart contract calls (cannot be larger than 2MB).

So, I put the `JoltPreprocessing` construct on the IC. As a result, the instructions required by this construct exceeded the [instruction limit](https://forum.dfinity.org/t/instruction-limit-is-crushing-me/22070/10?u=flyq) of a single call of the IC, and failed:

let preprocessing: JoltPreprocessing<Fr, G1Projective> =
    RV32IJoltVM::preprocess(bytecode, memory_init, 1 << 20, 1 << 20, 1 << 24);

## Second Try

This time, I tried constructing the `JoltPreprocessing` off-chain, serializing it, and uploading it to the IC.

So, I need to [modify JoltPreprocessing](https://github.com/flyq/jolt/commit/b2449cf6fc80017493b220f2fd4e651873530bbb), in which adding `Default` and `De/Serialize` to `JoltPreprocessing`, and then I save the serialized JoltPreprocessing to file:

    let preprocessing: JoltPreprocessing<Fr, G1Projective> =
        RV32IJoltVM::preprocess(bytecode, memory_init, 1 << 20, 1 << 20, 1 << 24);

    let file = File::create("preprocess.bin").unwrap();
    preprocessing.serialize_compressed(file).unwrap();

but It is too large(~48MB) to upload to IC canister:

ls -al preprocess.bin 
-rw-r--r--  1 flyq  staff  48386392 Apr 15 10:36 preprocess.bin

Then I tried to modify the size of the problem in the example, from solving `fib(50)` to `fib(3)`. The size is still about 48MB, much larger than 2MB.

Then I tried to modify parameters such as the maximum memory from $2^{20}$ to $2^{10}$, but the size was still 48 MB:

    let preprocessing: JoltPreprocessing<Fr, G1Projective> =
        RV32IJoltVM::preprocess(bytecode, memory_init, 1 << 10, 1 << 10, 1 << 14);

## Third Try

Thanks to [Dominic Wörner](https://twitter.com/domiwoe) and [Wyatt Benno](https://twitter.com/wyatt_benno) for the tips.

This time I did the following work, trying to split the `Preprocess` into multiple data blocks, and then assemble them in advance in the canister. But when the `Proof` is uploaded and verified, the error of exceed instruction limit is still coming out.

Therefore, I also need to upload the `Proof` bytes in advance, save the deserialized Proof, and then in a new update call, get the prepared Preprocess and Proof, directly call `verify`, and finally there is no instruction limit error and success, obtained a true verification result

During this process, Canister requires `Proof` to implement the Clone trait, so I [added the Clone trait](https://github.com/flyq/jolt/commit/98d1645e8cb8faa9e4dce713d90edf8efd789d3d) to Proof in Jolt lib, and stirred up a hornet's nest. Finally, I added Clone to all 55 data structures that make up Proof and successfully passed the compilation. The advantage is that I completely know what components Proof and Commitment are composed of.

## Next Plan

Waiting the optimizing Rust verifier: https://github.com/a16z/jolt/issues/216