OlaVM

OlaVM is a STARK-based ZK-friendly ZKVM, it is built on a small finite field called Goldilocks field. As the most important component of the Ola system, OlaVM is mainly used to execute a program and generate a valid proof for the programmable scalable case and the programmable private case.

Warning: This repository shouldn't be used for production case, as it is still in development phase and has not been audited, so it might contain many bugs and security holes..

Overview

OlaVM is a Turing complete VM, which means that it can execute any computation on it and at the same time it could generate a valid proof for it. For getting a smaller proof time, we have many powerful designs that are relevant with ZK-friendly.

if you want to know more about ZK-friendly and VM designs, check out the doc/olavm;
if you want to know more about the circuit design, check out circuit crate;
if you want to know more about the performance of OlaVM, check out Performance section;
if you want to know more about STARKS, check out References section;

Key Features

There are a lot of tricks to get a very ZK-friendly ZKVM in OlaVM. We would like to highlight some of them:

Algebraic RISC. The property of the instruction set of OlaVM is Algebraic RISC: "Algebraic" refers to the supported operations are field operation, "RISC" refers to the minimality of the instruction set. We can achieve a concise transition constraint based on this, see circuit/cpu to learn more;
Small finite field. The word defined in OlaVM is a finite field, Goldilocks. The prime of Goldilocks is p = 2^64 - 2^32 + 1, which is less than 64 bits. The computation based on these field elements could be expected to be much faster than other large finite fields;
Builtins. Since the cyclic group size is limited, it would be better if the trace table could contain as many transactions as possible. This means that if there are some computation cost a large trace lines in transaction logic, we should remove them from the main trace table and add a special sub-trace table to store them, this is the reason that introduce builtins, like hash, bitwise operation and so on, check the doc/olavm for more details;
Prophets. It is designed for non-deterministic computation, which means "implementation is expensive, verification is cheap". So to some extent Prophets is more like an external helper. It helps you compute the results of some non-deterministic computation, and then you verify the results using the instruction sets, should note that this verification is done by the VM, not by constraints which is different with builtins, see the doc/olavm for more details;

Status

Features	Status
Algebraic RISC	$\color{Green}{Done}$
Small finite field	$\color{Green}{Done}$
Builtins - bitwise	$\color{Green}{Done}$
Builtins - rangecheck	$\color{Green}{Done}$
Builtins - cmp	$\color{Green}{Done}$
Builtins - poseidon	$\color{Yellow}{Doing}$
Builtins - ecdsa	$\color{Yellow}{Doing}$
Prover optimization	$\color{Green}{Done}$
Prophets lib	$\color{Red}{Todo}$
u32/u64/u256 lib	$\color{Red}{Todo}$
Support privacy	$\color{Red}{Todo}$

Project structure

This project consists of several crates:

Crate	Description
core	Define instruction structure and instruction sets
circuits	1. Constraints for instruction sets, builtins, memory; 2. Generate proof
executor	Execute the programme and generate the execution trace for the Ola-prover
client	Some commands can be used by developers
plonky2	A SNARK implementation based on techniques from PLONK and FRI techniques
infrastructure	Write the execution trace to an Excel file

Performance

Many optimizations have not yet been applied, and we expect to see some speed improvements as we devote more time to performance optimization. The benchmarks below should only be used as a rough guide to expected future performance.

In the benchmarks below, the VM executes the same Fibonacci calculator program for 2^20 cycles at 100-bit target security level on a high-end 64-core CPU:

VM cycles	Execution time	Proving time	RAM consumed	Proof size
2^18	81.115 ms	2.932 s	5.6 GB	175 KB
2^19	159.80 ms	6.143 s	11.1 GB	181 KB
2^20	318.08 ms	12.688 s	23.2 GB	187 KB
2^21	627.38 ms	29.923 s	45.3 GB	195 KB
2^22	1240.4 ms	61.834 s	86.6 GB	208 KB
2^23	2453.8 ms	128.62 s	176 GB	216 KB

Run cd circuits && cargo bench -- fibo_loop_prover to see the benchmark data.

Overall, we don't expect the benchmarks to change significantly, but there will definitely be some deviation from the numbers below in the future.

A few general notes on performance:

Software:

Support the fastest hash algorithm, Blake3 Hash $\color{Green}{Done}$
Support parallel FFT $\color{Green}{Done}$
Support parallel polynomial evaluation $\color{Green}{Done}$
Support parallel proof

Hardware:

Integrate GPU accelerated FFT
Integrate GPU accelerated polynomial evaluation
Integrate FPGA accelerated FFT
Integrate FPGA accelerated polynomial evaluation

Here is an example program which calculates a fibonacci(8) cyclically and generates a main trace of 2^20 rows, then proves the execution is correct by generating a proof and verifying the proof:

    // mov r0 8
    // mov r1 1
    // mov r2 1
    // mov r3 0
    // EQ r0 r3
    // cjmp 19
    // add r4 r1 r2
    // mov r1 r2
    // mov r2 r4
    // mov r4 1
    // add r3 r3 r4
    // jmp 8
    // end
    let program_src = "0x4000000840000000
        0x17200
        0x4000001040000000
        0x1
        0x4000002040000000
        0x1
        0x4000004040000000
        0x0
        0x0020810100000000
        0x4400000010000000
        0x13
        0x0040408400000000
        0x0000401040000000
        0x0001002040000000
        0x4000008040000000
        0x1
        0x0101004400000000
        0x4000000020000000
        0x8
        0x0000000000800000"

    let instructions = program_src.split('\n');
    let mut program: Program = Program {
        instructions: Vec::new(),
        trace: Default::default(),
    };

    // prepare the fibonacci program
    for inst in instructions.into_iter() {
        program.instructions.push(inst.clone().parse().unwrap());
    }

    // execute the fibonacci program
    let mut process = Process::new();
    process.execute(&mut program);
    

    // generate the proof with traces from the execution of the fibonacci program
    let mut ola_stark = OlaStark::default();
    let (traces, public_values) = generate_traces(&program, &mut ola_stark);
    let config = StarkConfig::standard_fast_config();
    let proof = prove_with_traces::<F, C, D>(
        &ola_stark,
        &config,
        traces,
        public_values,
        &mut TimingTree::default(),
    )?;

    // verify the proof is correct
    let ola_stark = OlaStark::default();
    verify_proof(ola_stark, proof, &config)

References

OlaVM runs based on the Goldilocks field and uses STARK to generate proofs for the inner layer and more will use Plonky2 to generate recursive proofs for inner proofs. There are some resources to learn more about it.

Goldilocks field & plonky2

STARK

Vitalik Buterin's blog series on zk-STARKs:

Part-1: Proofs with Polynomials
Part-2: Thank Goodness It's FRI-day
Part-3: Into the Weeds

Alan Szepieniec's STARK tutorials:

Part-0: Introduction
Part-1: STARK Overview
Part-2: Basic Tools
Part-3: FRI
Part-4: The STARK Polynomial IOP
Part-5: A Rescue-Prime STARK
Part-6: Speeding Things Up

Sin7Y's STARK explanation:

Privacy:

License

This project is under MIT licensed.

matthiasgoergens/olavm