Git Product home page Git Product logo

proof-systems's Introduction

CI dependency status

Kimchi

This repository contains kimchi, a general-purpose zero-knowledge proof system for proving the correct execution of programs.

You can read more about this project on the Kimchi book.

See here for the rust documentation.

Example

We assume that you already have:

  • gates: a circuit, which can be expressed as a vector of CircuitGate
  • a way to produce a witness, which can be expressed as a [Vec<F>; COLUMNS] (for F some field of your chosing)
  • public_size: the size of the public input

Then, you can create an URS for your circuit in the following way:

use kimchi::{circuits::constraints, verifier::verify};
use mina_curves::pasta::{fp::Fp, vesta::{Affine, VestaParameters}, pallas::Affine as Other};
use oracle::{
    constants::PlonkSpongeConstantsKimchi,
    sponge::{DefaultFqSponge, DefaultFrSponge},
};
use commitment_dlog::commitment::{b_poly_coefficients, ceil_log2, CommitmentCurve};

type SpongeParams = PlonkSpongeConstantsKimchi;
type BaseSponge = DefaultFqSponge<VestaParameters, SpongeParams>;
type ScalarSponge = DefaultFrSponge<Fp, SpongeParams>;

// compile the circuit
let fp_sponge_params = oracle::pasta::fp_kimchi::params();
let cs = ConstraintSystem::<Fp>::create(gates, vec![], fp_sponge_params, public_size).unwrap();

// create an URS
let mut urs = SRS::<Affine>::create(cs.domain.d1.size as usize);
srs.add_lagrange_basis(cs.domain.d1);

// obtain a prover index
let prover_index = {
    let fq_sponge_params = oracle::pasta::fq_kimchi::params();
    let (endo_q, _endo_r) = endos::<Other>();
    Index::<Affine>::create(cs, fq_sponge_params, endo_q, srs)
};

// obtain a verifier index
let verifier_index = prover_index.verifier_index();

// create a proof
let group_map = <Affine as CommitmentCurve>::Map::setup();
let proof = {
    // for recursion
    let k = ceil_log2(index.srs.g.len());
    let chals: Vec<_> = (0..k).map(|_| Fp::rand(rng)).collect();
    let comm = {
        let coeffs = b_poly_coefficients(&chals);
        let b = DensePolynomial::from_coefficients_vec(coeffs);
        index.srs.commit_non_hiding(&b, None)
    };
    (chals, comm)
    ProverProof::create::<BaseSponge, ScalarSponge>(&group_map, witness, &prover_index, vec![prev])
};

// verify a proof
verify::<Affine, BaseSponge, ScalarSponge>(&group_map, verifier_index, proof).unwrap();

Note that kimchi is specifically designed for use in a recursion proof system, like pickles, but can also be used a stand alone for normal proofs.

Organization

The project is organized in the following way:

  • book/. The mina book, RFCs, and specifications.
  • cairo/. A Cairo runner written in rust.
  • curves/. The elliptic curves we use (for now just the pasta curves).
  • groupmap/. Used to convert elliptic curve elements to field elements.
  • hasher/. Interfaces for mina hashing.
  • kimchi/. Our proof system.
  • ocaml/. Ocaml bindings generator tool.
  • oracle/. Implementation of the poseidon hash function.
  • poly-commitment/. Polynomial commitment code.
  • signer/. Interfaces for mina signature schemes.
  • tools/. Various tooling to help us work on kimchi.
  • utils/. Collection of useful functions and traits.

Windows Development

Windows development can be done using Windows Subsystem for Linux (WSL).

  • Install and open WSL
  • Within WSL, install OCaml using your distro's package manager. For example: apt install opam
  • Within WSL, navigate to the project directory and run cargo test. If there are no failures then everything is set up correctly.

proof-systems's People

Contributors

aaronsens avatar cd-dr avatar chee-chyuan avatar creativcoder avatar frisitano avatar hanabi1224 avatar iammadab avatar imeckler avatar jspada avatar ltvvlz avatar mimoo avatar mitschabaude avatar mobileink avatar mrmr1993 avatar mssabr01 avatar querolita avatar rbkhmrcr avatar trivo25 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.