Crate kimchi

Kimchi

Kimchi is based on PlonK, a zk-SNARK protocol.

Benchmarks

To bench kimchi, we have two types of benchmark engines.

Criterion is used to benchmark time. If you have installed cargo-criterion and gnuplot, you can run the benchmarks via

$ cargo criterion -p kimchi --bench proof_criterion

The result will appear in target/criterion/single\ proof/report/index.html and look like this:

Note that it only does 10 passes. To have more accurate statistics, remove the .sample_size(10) line from the bench.

The other benchmark uses iai to perform precise one-shot benchmarking. This is useful in CI, for example, where typical benchmarks are affected by the load of the host running CI.

$ cargo bench -p kimchi --bench proof_iai

It will look like this:

bench_proof_creation
Instructions: 22045968746
L1 Accesses: 27210681906
L2 Accesses: 32019515
RAM Accesses: 3034134
Estimated Cycles: 27476974171

Flamegraph

To obtain a flamegraph:

1. install required dependencies based on your OS
2. install cargo-flamegraph:

   $ cargo install flamegraph

3. run cargo flamegraph with sudo (or with the option --root on mac):

   $ # flamegraph of the proof creation:
   $ CARGO_PROFILE_RELEASE_DEBUG=true cargo flamegraph --bin flamegraph --notes "proof creation" -- prove
   $ # flamegraph of the proof verification:
   $ CARGO_PROFILE_RELEASE_DEBUG=true cargo flamegraph --bin flamegraph --notes "proof verification" -- verify

   the binary will run forever, so you have to C-c to exit and produce the flamegraph.svg file.

Note: lots of good advice on system performance in the flamegraph repo.

Re-exports

pub use groupmap;

pub use mina_curves;

pub use mina_poseidon;

pub use o1_utils;

pub use poly_commitment;

pub use turshi;

Modules

alphas

This module implements an abstraction to keep track of the powers of alphas. As a recap, alpha is a challenge sent by the verifier in PLONK, and is used to aggregate multiple constraints into a single polynomial. It is important that different constraints use different powers of alpha, as otherwise they can interact and potentially cancel one another. (The proof is in the use of the Schwartz-Zippel lemma.) As such, we want two properties from this:

bench

circuits

curve

This module contains a useful trait for recursion: KimchiCurve, which defines how a pair of curves interact.

error

This module implements the ProverError type.

lagrange_basis_evaluations

linearization

This module implements the linearization.

oracles

This type and logic only exists for the OCaml side. As we move more code to the Rust side, we hope to be able to remove this code in the future.

plonk_sponge

precomputed_srs

To prover and verify proofs you need a Structured Reference String (SRS). The generation of this SRS is quite expensive, so we provide a pre-generated SRS in this repo. Specifically, two of them, one for each pasta curve.

proof

This module implements the data structures of a proof.

prover

This module implements prover’s zk-proof primitive.

prover_index

This module implements the prover index as ProverIndex.

verifier

This module implements zk-proof batch verifier functionality.

verifier_index

This module implements the verifier index as VerifierIndex. You can derive this struct from the ProverIndex struct.

Macros

auto_clone

Auto clone macro - Helps make constraints more readable by eliminating requirement to .clone() all the time

auto_clone_array

grid

loc

Handy macro to return the filename and line number of a place in the code.

variable_map

Macro to simplify creation of layout map

variables

Macro to simplify mapping of layout variable