anoma/zkp-compiler-shootout

Evaluating & benchmarking ZKP compilation strategies.

ZKP (circuit) compiler shootout

Evaluating & benchmarking ZKP compilation strategies.

Currently we are testing the following Zero Knowledge machines

1. RISC0
2. Miden
3. Triton
4. Plonk
5. Halo2

If you would like your machine / framework / compilation strategy to be benchmarked against the standard suite, please submit a PR! You can find instructions below.

Results can be seen in the following files:

• BENCHMARKS-x86.md
  • The results rendered in a mark down table
• BENCHMARKS-arm64.md
  • The results rendered in a mark down table
• anoma.github.io/zkp-compiler-shootout/
  • The results with graphs and standard deviations, means, etc.

The results were collected on a AMD Ryzen 7 5700X 8-Core @ 16x 3.4GHz CPU.

To see very rough notes about the languages in the benchmark and potential improvement points please read my notes file.

Dependencies

For some benchmark backends some external dependencies are required

Risc0

1. risczero
2. cargo-risczero

which can be installed by the following command

cargo install cargo-risczero
cargo risczero install

Make table

1. cargo-criterion
2. criterion-table

these can both be installed with the following command.

cargo install cargo-criterion
cargo install criterion-table

How to get benchmark results

There are two commands for producing results

1. make table arg="desired_backend"
2. make bench arg="desired_backend

It is recommended to run make table. However it requires two external dependencies

see the dependencies section for instructions for installation.

Make sure cargo packages are on your path.

Either way, the results can be seen

1. run make table arg="desired_flags"
   • or make bench arg="desired_flags, if one does not wish to install the cargo packages
2. sit back and watch your CPU spin
3. The HTML results should be in ./shootout/target/criterion/reports/index.html
4. If make table was run, the updated benchmark results should be seen in ./BENCHMARKS.md

Benchmark Flags

In order to be effective for developers and users wishing to verify results, we do not enable all benchmarks by default.

The following class of flags are had

1. Compiler flags
2. Test flags
3. Step Flags

All Step flags and Test flags are enabled by default. ALl Step flags on may be too slow for your workflow.

Parent Flag	Flag	default status	Notes
all	all	off
all_compilers	miden	off
all_compilers	triton	off
all_compilers	halo2	off
all_compilers	plonk	off
all_compilers	risc	off	Fails to compile
all_compilers	vampir_p	off
all_compilers	vampir_halo2	off
all_tests	sudoku	on
all_tests	fib	on
all_tests	blake	on
all_steps	compile	on
all_steps	prove	on
all_steps	verify	on
all_steps	prove_and_verify	on

• Any compilers that have Fails to compile, have to be enabled by hand in arg, as they are excluded from their parent

So if one wants to run everything one can run

make table arg="all"

In fact if one is fine with the default on features then one just needs to run

make table arg="miden"
make bench arg="miden"

where you can replace miden with any compiler_flag, such as risc.

However if one wishes to turn off a feature like various steps or tests

then one has to run a command like

cd shootout

cargo bench --no-default-features --features "all_tests prove_and_verify miden"

Here, we turn off all the steps, running only the prove_and_verify part of the benchmark.

Contributing

This repository serves as a base for contributions and so contributions should hopefully be easy, and deficiencies on the implementations well known.

Hopefully the process is rather straight forward, however we give a guide below to more quickly get familiar with the structure of the project.

To get a quick TL;DR feeling of this you could alternatively read how the miden backend plugs in both in the miden.rs, main.rs, bench.rs, and the miden sub directory for project layout. That should hopefully be readable enough without having to read the full guide below.

Layout Structure: SRC

The project has two components of organization, the shootout directory has an src folder that hosts a file per backend. These files (miden.rs, risc.rs, etc.) are rather basic, just hosting an implementation of the given backend struct that was created.

.
├── Cargo.lock
├── Cargo.toml
├── src
│   ├── bench.rs
│   ├── halo.rs
│   ├── main.rs
│   ├── miden.rs
│   ├── plonk.rs
│   └── risc.rs

We can see other files as well such as bench.rs and main.rs

For creating a new backend to test, one will have to touch bench.rs to have their new backend be tested. Since the code added is just a way to get around Rust's lack of typing of existentials this should be an easy task.

One should also add a feature flag for one's compiler in Cargo.toml.

Finally, in main.rs we hook up our tests to a certain benchmark we care about.

pub fn bench_sudoku(c: &mut Criterion) {
    let to_bench = vec![
        #[cfg(feature = "miden")]
        ZKP::Miden(miden::sudoku()),
        #[cfg(feature = "plonk")]
        ZKP::Plonk(plonk::sudoku()),
        #[cfg(feature = "risc")]
        ZKP::Risc0(risc::sudoku()),
        #[cfg(feature = "halo2")]
        ZKP::Halo2(halo::sudoku()),
    ];
    bench_zkp(c, String::from("Sudoku"), to_bench)
}

As we can see it's just adding the backend's struct to a vector list and wrapped with the enum found in bench.rs.

This structure should also make it easy to add new benchmark programs, please feel free to add new kinds of programs we wish to test here with whatever backend you are interested in! Hopefully others, including myself, can contribute to other backends for your test!

Layout Structure: sub directories

The layout structures of the other directories are as follows:

.
├── Cargo.lock
├── Cargo.toml
├── miden
├── notes.org
├── risc
├── sudoku-halo2
├── sudoku-plonk
└── zero-knowledge
    ├── Cargo.toml
    └── src

The most important folder is zero-knowledge as this has the trait needed to implement to have the benchmarker work.

pub trait ZeroKnowledge {
    type C;
    type R;
    fn name(&self) -> String;
    fn compile(&self) -> Self::C;
    fn prove(&self, setup: &mut Self::C) -> Self::R;
    fn verify(&self, receipt: Self::R, program: &mut Self::C) -> ();
    fn prove_and_verify(&self) -> () {
        let circuit = self.compile();
        let receipt = self.prove(&circuit);
        self.verify(receipt, &circuit);
    }
}

Here for a custom backend one just needs to implement compile, prove, verify, and a name, and your new zero knowledge backend can be tested!

The other folders like miden and risc, represent stand alone backends. Adding a new program to benchmark or improve a current benchmark should be quite easy.

the sudoku-halo2 and sudoku-plonk are similar, but represent a single program/project style structure (In the future we will likely transform these to fit the mold of what risc and miden have).

Lastly, the notes.org file lays out notes about the backends and deficiencies in any particular implementation, hopefully over time all the programs will be optimal for their specific backend to have a more accurate and fair results.

Project Structure

For adding a new backend or adding new programs for backends like halo2 or plonk. One may have to create a new sub directory.

this can be done with cargo new, or if you already have working code, just copy and paste your code into the directory! each of the sub-directories are standalone independent projects with their own workspace. The only new dependency you'll have to add is:

[dependencies]
zero-knowledge = { path = "../zero-knowledge" }

and make sure the top level Cargo.toml excludes the project and brings it in as a dependency.

If you are importing existing code for a new backend, make sure you implement the ZeroKnowledge trait, and you're all set!

We will now talk about backend specific considerations, feel free to skip these if they aren't a backend you care about contributing to

Project Structure: Miden

The miden backend can be found in the miden sub directory. Really one does not have to alter this code at all, just add your program to src/miden.rs to mainly fill in the starting advice tape or the starting stack, along with the file path where the miden program is stored.

Ι personally keep my miden code in miden-assembler, as Ι generate out miden code from my Common lisp DSL in programs sub directory. All one needs to run this code is quick-lisp and just write

;; if you need to load the file by hand
;; I will assume the repl is in the miden-assembler directory
(load "miden-assembler.asd")
;; load the project
(ql:quickload :miden-assembler)
;; switch to the project
(in-package :miden)
;; dump the code changes
(dump)

However you may keep it wherever you feel, just make sure path is properly given in the miden.rs file.

the rest is just hooking up your new program to main.rs which should be straight forward.

Project Structure: Risc0

Risc0 can compile straight rust code, which is nice, however this means the structure is a bit different from miden or other ZKVMs.

.
├── Cargo.toml
├── methods
│   ├── build.rs
│   ├── Cargo.toml
│   ├── guest
│   └── src
├── README.md
├── src
│   ├── lib.rs
│   └── main.rs
├── sudoku-core
│   ├── Cargo.toml
│   └── src
└── target

the src directory contains lib.rs which you will only need to touch the imports from the methods directory. the Risc struct should be general enough to handle any program you wish to compile.

.
├── build.rs
├── Cargo.toml
├── guest
│   ├── build.rs
│   ├── Cargo.lock
│   ├── Cargo.toml
│   ├── src
│   │   └── bin
│   │       ├── fib_fifty.rs
│   │       ├── fib_ninty_two.rs
│   │       ├── fib.rs
│   │       └── sudoku.rs
└── src
    └── lib.rs

inside methods, you should place your code in the bin of guest. As you can see the names of the current programs, these correspond to the imports in lib.rs

pub use methods_fib::{FIB_ID,           FIB_PATH,
                      FIB_FIFTY_ID,     FIB_FIFTY_PATH,
                      FIB_NINTY_TWO_ID, FIB_NINTY_TWO_PATH,
                      SUDOKU_ID,        SUDOKU_PATH};

Note that any dependency you want to be compiled with these should be placed in the Cargo.toml in the guest directory. This includes shared code like we have for sudoku-core, which is linked both to the guest and to the native rust code in src.

Much like miden, all that is now required is to make the Risc struct in shootout/src/risc.rs for your new program and tell main.rs to benchmark it!

Project Structure: Stand alone.

Hopefully miden shows a good way to create standalone projects. So if one has existing halo2 or plonk code, one could just copy and paste it into a directory and implement the ZeroKnowledge trait. for their program.

Alucard/VAMP-IR

Please see the official Alucard repository.

Geb

See the Geb repository.

zkp-compiler-shootout's Issues

Make Merkle Proof Benchmarks.

Merkle Proofs are a common use case for ZKP languages. It would be great to have benchmarks comparing the speed with a Merkle inclusion proof

We can do this on a per backend basis, so we can slowly add one backend at a time.

Re-enable RISC0

Currently due to compiler tool chain versions, risc0 is now disabled.

I'd ideally get this working again.

Triton: Preserving Expected Block Order

as seen in #16, there is no easy way to jump to a label without affecting the call stack. This demands that abstractions like loop or if after their termination, will have to have their exit code labels be placed after the label they were called from.

(def nonsense-example
  (tagbody 
   :nonesense-entry-point
     (dup 0)
     (if (begin (push 2) add)
         (begin (push 3) add))
   ;; In real code, this is generated by if, not written in code explicitly
   :after-if 
     (push 4)
     (loop swap (push 3) add swap)
   ;; In real code, this is generated by loop, not written in code explicitly
   :after-loop
     (dup 0)
     (push 100)
     lt skiz recurse return))

This should generate code to look something like

nonsense-entry-point:
  dup0
  skiz
  call if-wraper
after-if:
  push 4
  call loop
after-loop:
  dup0
  push 100
  lt skiz recurse return

if-wraper: ...
loop: ....

where loop and if-wrapper: are filled in with their proper code. However note where after-if: and after-loop: come. Their ordering was set to be after whatever the current block at the time was!

This behavior is not trivial to implement, as we can not rely on all gotos's to get the ordering naturally like a SSA style control flow graph.

In fact, due to how ordering works, we have to make sure we move down the any labels that were created before the continues-at point to the end, as the if/loop return label may have labels that already implicitly follow it!

We therefore have to carefully remember this ordering ourselves. Thankfully I propose the following solutions:

Solution 1: Flip the Chessboard, Anything that Branches, is now an adhoc procedure!

This solution is simpler than the second solution and is more elegant, however it needs some build up.

When we say something like (loop swap (push 3) add swap), how we think of the control graph, is that it calls into some loop boiler plate with the user logic inside, then it returns back to the caller.

Thus instead of thinking of concepts like loop and if as primitives or like a normal instruction, we can think of it like a higher order procedure!

Namely, an invocation of loop or if creates a brand new procedure, with the code the user specified being inside the generated procedure.

Since these blocks always call and return they are safe to move anywhere. This completely removes any need for reordering logic.

All that needs to happen from the code standpoint is:

1. Extend labels with a notion of created procedures that we accumulate.
2. When making an abstraction which takes user code and has any branches, remember to mark it as a procedure!
   • This puts a burden upon the abstraction writer, however hopefully it should be obvious when this happens
     • Maybe if I have enough examples I can nicely abstract it away from the author...

Solution 2: Extending Tlabels with Ordering and Hashtables

We change tlabels from being just a a list of blocks, to being a record containing the following fields.

1. A current ordering
2. A hashtable mapping the keyword label of a block to the block itself.
3. A current block that we are adding instructions onto.
4. A list of the current explicit follows.
5. An enum of :front, :end, or nil. For current blocks without labels, telling them where they go in the ordering

What the 4. point does, is when we finalize the block, we will move all nodes between the current node and what follows to the end.

Thus if we have

:a :b :c :d :e

and we say :d follows :a, then the ordering list will now look like

:a :d :e :b :c

This method is slow and is O(n^2) in the number of explicit follows. However if this is found to slow down the speed of compilation, then I can implement a O(n) method by some sort of numbering.

A note about merging tlabels

An important means of combination for tlables is appending an instruction or a set of instructions to the front.

This will serve as the modified version of my existing triton:cons-instructions-to-labels

• Consing an opcode (push, call, etc.):
  1. if there is a label for the current block:
     1. Finish the block, updating/adding it to the hashtable at its label
     2. Create a new block, with the enum field set to :front
  2. If there is no label for the current block
     1. Just cons onto the current block!
• Consing a label:
  1. If there is a label for the current block
     • Finish the block, updating/adding it to the hashtable at its label
     • Create a new block, and place it's ordering to the front of the list, and set the enum to nil
  2. If there is no label for the current block
     - Add the label to the current block
     - Add the new label to the ordering, at the front or end depening on what the value of the enum is.
• Consing a block:
  1. If there is no current block
     • Then set the current block to the given block
  2. If there is no label for the current block
     • Merge the two blocks. Note if the block we are consing has a label, then simply call the logic for consing a label
  3. If there is a label for the current block
     1. Finish the block, updating/adding it to the hashtable at its label
     2. Add block, and call logic for consing a label
• Consing a tlabels:
  1. Merge the hashtables.
  2. If there is no name for the current block and the consed tlabels is not empty:
     • gensym an unique label for the current block.
  3. Finalize the current block
  4. Take the tlabels's current block as our own, along with its enum value

Consider Benchmarking Libraries

Currently we are using criterion to test rust programs. This programs seems quite nice for benchmarking programs, however I should conduct a study of available benchmarking tools.

Another important consideration is how do we benchmark programs not written in rust? It would be cool if we can get a csv file out of the times, and import it into some system, which does the statistical projection for us. This way all our statistics look and feel consistent.

Triton Generation

Currently my code generator for Triton is quite primitive. I would like the following to be made

1. Add a notion of blocks
   • blocks are a label + code inside
   • nested blocks are not allowed!
2. Add a notion of collected labels
   • These are all the labels in a function
   • This also serves as an abstraction mechanism
     • Since functions like if create new labels to continue at, it is important to be able to compose this with code that comes next
     • Meaning that if we end off with a continuation address, and some code after it in it's own block, we should unify the jump points and give the block two names or unify the names
     • This means that we can effectively compose any abstractions, even those which create branches
3. #17
4. Add a notion of functions
   • Functions will collect all labels, and compose an entry point
5. Make Program encompass this
   • This means that a program will now be some some code that also keeps the relevant functions in mind and generates out the proper calls.
   • Further this would be the entry point to the circuit

Add Cairo to the shootout

Cairo is a rather neat project, we should add it to the benchmark.

However, Cairo has a few ways of operating so we should test the following provers

1. https://github.com/maxgillett/giza
2. https://github.com/starkware-libs/stone-prover

For the compiler I recommend using

1. https://github.com/lambdaclass/cairo-vm

cargo bench doesn't report data for Halo2

Also there are two versions of Halo2, via IPA and KZG. Is it possible to plugin both backends?

Reorganize Rust Structure

The current structure of having Sudoku folder with the risc0 code was fine before, however I wish to scale up the repo, and have multiple similar folders per idea. Thus I propose the following folder structure

• Program Name [Sudoku]
  • Approach Name with relevant code [Risc0, Halo2, Alucard, etc]
    • Code with an explicitly exported module
• Benchmark (This contains all benchmarks which can be run. A Test property will be had so each benchmark can be run standalone)

Add More Hashing Benchmarks

Currently I've added a Blake2 benchmark for risc0, but it would be nice to get a good basis of hash functions bench marked:

Known hashing functions to benchmark and compare

• Blake 3: Miden
• Sha 256: Miden
  • https://github.com/maticnetwork/miden/blob/main/assembly/benches/program_compilation.rs
• Blake3: Risc0

It would be great to get contributions for all ZKVM machines. Ideally we can get all the machines to have the same algorithm, so we can compare speeds more easily.

I should also verify the answer somehow.

For the Blake 3: Miden example I take it on faith value that I'm feeding the inputs correct and getting the correct output

Lower Benchmark timing

It seems like running the benchmarker takes 15 minutes on my machine. I need to reduce the number of repeat tests from 100 to 20.