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, examples, documents, blogs, and papers(Lasso and Jolt). (The blogs contains a lot of insider information about the zk industry)

After running the examples, I tried integrating its verifier into the IC Canister.This thing is very meaningful and is actually an official todo list.

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:

expanded code

#![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)
}

This code can't be run, because it 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, 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, 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 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 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, 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 and 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 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