Crate kimchi

source ·
Expand description

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:

criterion kimchi

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;
  • pub use snarky::prelude::*;

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.
  • folding
  • 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.
  • snarky
    Snarky is the front end to kimchi, allowing users to write their own programs and convert them to kimchi circuits.
  • 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