Code Monkey home page Code Monkey logo

jellyfish's Introduction

Jellyfish cryptographic library

example workflow Crates.io (version) GitHub

Disclaimer

DISCLAIMER: This software is provided "as is" and its security has not been externally audited. Use at your own risk.

Chatroom

For general discussions on Jellyfish PLONK, please join our Discord channel.

Development environment setup

We recommend the following tools:

Run direnv allow at the repo root. You should see dependencies (including Rust) being installed. Alternatively, enter the nix-shell manually via nix develop.

You can check you are in the correct development environment by running which cargo, which should print something like /nix/store/2gb31jhahrm59n3lhpv1lw0wfax9cf9v-rust-minimal-1.69.0/bin/cargo; and running echo $CARGO_HOME should print ~/.cargo-nix.

Build, run tests and examples

Build:

cargo build

Run an example:

cargo run --release --example proof-of-exp --features test-srs

This is a simple example to prove and verify knowledge of exponent. It shows how one may compose a circuit, and then build a proof for the circuit.

WASM target

Jellyfish is no_std compliant and compilable to WASM target environment, just run:

./scripts/build_wasm.sh

Backends

To choose different backends for arithmetics of curve25519-dalek, which is currently used by jf-primitives/aead, set the environment variable:

RUSTFLAGS='--cfg curve25519_dalek_backend="BACKEND"'

See the full list of backend options here.

You could further configure the word size for the backend by setting (see here):

RUSTFLAGS='--cfg curve25519_dalek_bits="SIZE"'

Tests

cargo test --release

Note that by default the release mode does not check integers overflow. In order to enforce this check run:

./scripts/run_tests.sh

Test coverage

We use grcov for test coverage

./scripts/test_coverage.sh

Generate and read the documentation

Standard

cargo doc --open

Code formatting

To format your code run

cargo fmt

Updating non-cargo dependencies

Run nix flake update if you would like to pin other version edit flake.nix beforehand. Commit the lock file when happy.

To update only a single input specify it as argument, for example

nix flake update github:oxalica/rust-overlay

Benchmarks

Primitives

Currently, a benchmark for verifying Merkle paths is implemented. The additional flags allow using assembly implementation of square_in_place and mul_assign within arkworks:

RUSTFLAGS='-Ctarget-cpu=native -Ctarget-feature=+bmi2,+adx' cargo bench --bench=merkle_path

PLONK proof generation/verification

For benchmark, run:

RAYON_NUM_THREADS=N cargo bench

where N is the number of threads you want to use (N = 1 for single-thread).

A sample benchmark result is available under bench.md.

Git Hooks

The pre-commit hooks are installed via the nix shell. To run them on all files use

pre-commit run --all-files

jellyfish's People

Contributors

akonring avatar alxiong avatar ancient123 avatar bfish713 avatar bulikos avatar chancharles92 avatar clu8 avatar dependabot[bot] avatar frierened avatar ggutoski avatar github-actions[bot] avatar huitseeker avatar jbearer avatar mike1729 avatar mrain avatar nomaxg avatar philippecamacho avatar sveitser avatar tbro avatar tessico avatar victorkoenders avatar xiaolou86 avatar zhenfeizhang avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

jellyfish's Issues

[Constraint] Introducing BoolVariable

we could introduce a struct BoolVariable which on initialization would enforce it's binary value. This would makes our API for gates like unpack() or logic_gate() clearer and less error-prone when it comes to deciding when to enforce/check {0,1} on the wire variable.

cc @zhenfeizhang

audit the useage of `RngCore + CryptoRng` vs `Rng` vs `CSPRNG`

this triggers me to think if we should replace some RngCore + CryptoRng trait bound in our API to just Rng?

  1. We are not implementing an PRNG ourselves, so we should probably always use Rng over RngCore, (since the latter is for backend implemented by the generator)
  2. What are some places where we have to use CSPRNG? probably not in schonrr or transcript?

Originally posted by @alxiong in #53 (comment)

Cargo clippy error

Compile error message

    Checking jf-rescue v0.1.2 (/Users/chengyu/espressosys/jellyfish/rescue)
error: you are deriving `PartialEq` and can implement `Eq`
  --> rescue/src/errors.rs:17:26
   |
17 | #[derive(Debug, Display, PartialEq)]
   |                          ^^^^^^^^^ help: consider deriving `Eq` as well: `PartialEq, Eq`
   |
note: the lint level is defined here
  --> rescue/src/lib.rs:22:9
   |
22 | #![deny(warnings)]
   |         ^^^^^^^^
   = note: `#[deny(clippy::derive_partial_eq_without_eq)]` implied by `#[deny(warnings)]`
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#derive_partial_eq_without_eq

error: you are deriving `PartialEq` and can implement `Eq`
  --> rescue/src/lib.rs:95:24
   |
95 | #[derive(Clone, Debug, PartialEq, Copy)]
   |                        ^^^^^^^^^ help: consider deriving `Eq` as well: `PartialEq, Eq`
   |
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#derive_partial_eq_without_eq

error: could not compile `jf-rescue` due to 2 previous errors

unsatisified no_std

Currently we thought we had proper no_std support since we use ark_std by default and only use std library with features(std).

I run into a bug today on cap-rollup branch that suggests otherwise.

How to reproduce

Check out to cap-rollup branch, run cargo check the code should compile successfully, but when running cargo check --features std, then you should see this error:

    Checking jf-plonk v0.1.2 (/Users/alex/work/jellyfish/plonk)
error[E0119]: conflicting implementations of trait `std::error::Error` for type `errors::PlonkError`
  --> plonk/src/errors.rs:50:1
   |
47 | impl ark_std::error::Error for PlonkError {}
   | ----------------------------------------- first implementation here
...
50 | impl std::error::Error for PlonkError {}
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `errors::PlonkError`

This is unexpected since ark_std::error::Error should be a different trait than std::error::Error.

Analysis

@zhenfeizhang and I spent some time digging around.

  • We first eliminate the possibility of leaky no_std from upsteam ark_std library by creating a minimal reproducible example.
  • We also double checked that our syntax #![cfg_attr(not(feature = "std"), no_std)] is a correct no_std declaration
  • we come to temporary conclusion that we could have accidentally imported a version of ark_std with features = ["std"], this could be through parallel features of ark-ff, ark-ec, ark-bls or any curve impl crates.
    • this suspicion gets confirmed by removing the parallel feature flag on ark-ff and ark-ec in our utilities crate, and we get the following error when only trying to compile jf-utils:
         --> utilities/src/serialize.rs:119:17
          |
      119 | #[derive(Debug, Snafu)]
          |                 ^^^^^ method cannot be called on `&SerializationError` due to unsatisfied trait bounds
          |
         ::: /Users/alex/.cargo/registry/src/github.com-1ecc6299db9ec823/ark-serialize-0.3.0/src/error.rs:5:1
          |
      5   | pub enum SerializationError {
          | ---------------------------
          | |
          | doesn't satisfy `SerializationError: AsErrorSource`
          | doesn't satisfy `SerializationError: StdError`
          |
          = note: the following trait bounds were not satisfied:
                  `SerializationError: StdError`
                  which is required by `SerializationError: AsErrorSource`
                  `&SerializationError: StdError`
                  which is required by `&SerializationError: AsErrorSource`
          = note: this error originates in the derive macro `Snafu` (in Nightly builds, run with -Z macro-backtrace for more info)
      

Root Cause

  • WIP: find out the real root cause
  • WIP: evaluate other repos for similar problem
  • Q: how to setup code to automatically detect accidental reliance on std in the future?

[API] Introduce SNARKConfig

Problem

Currently our trait UniversalSNARK<E: PairingEngine> whose prover API has bunch of generic type params:

fn prove<C, R, T>(
    rng: &mut R,
    circuit: &C,
    prove_key: &Self::ProvingKey,
    extra_transcript_init_msg: Option<Vec<u8>>,
) -> Result<Self::Proof, Self::Error>
where
    C: Arithmetization<E::Fr>,
    R: CryptoRng + RngCore,
    T: PlonkTranscript<E::Fq>;

Not to mention the complicated trait bounds such as:

impl<E, F, P> Verifier<E>
where
    E: PairingEngine<Fq = F, G1Affine = GroupAffine<P>>,
    F: RescueParameter + SWToTEConParam,
    P: SWModelParameters<BaseField = F> + Clone,

Proposal

(ideas stem from discussion with @chancharles92 and @zhenfeizhang)

In this task, we hope to introduce an encompassing trait SNARKConfig similar to:

trait SNARKConfig {
  type Transcript;
  type PCS: PolynomialCommit;
  type PairingEngine<Fr = Self::ScalarField, Fq = Self::BaseField>;
  type ScalarField: RescueParameter + SWToTEConParam;
  type BaseField;
}

trait SNARK: SNARKConfig {
  fn prove(...) {
    let transcript = Self::Transcript::new();
    // ...
    let cm = <Self::PCS as PolynomialCommitment>::commit();
  }
}

Preparing for open sourcing

Here are a list of todos; ESSENTIAL are the ones that need to be solved before we open up this repo:

  • logistics
    • [ESSENTIAL] choose a proper license: MIT
    • [ESSENTIAL] proper reading/writing permissions
    • create a channel for the community: telegram, discord, others? do it after open sourcing
    • create a PR template
  • documentation
    • [ESSENTIAL] update read me
    • update cargo doc
  • code
    • [ESSENTIAL] conduct one more code review and remove sensitive info
    • [ESSENTIAL] update other libraries to make sure nothing breaks
    • [ESSENTIAL] add Plonk benchmark
    • [ESSENTIAL] open source tagged-base64 repo
    • check testing coverage
    • update to latest dependencies #12
    • check benchmark scripts
    • expose test API via feature test #12
  • badges (low priority)
    • license
    • CI
    • crates.io (after code is published at crates.io)
    • test coverage <- require a dedicated CI service

PLONK for range proofs

I am looking at the Jellyfish library and want to measure the performance of the implemented PLONK for range proof circuits.
When I run the PLONK prover on the built-in range circuit, I get the error "SnarkError(WrongQuotientPolyDegree(127, 87))" showing the quotient polynomial has wrong degree. Any idea what's the issue? Maybe the culprit is the lack of field conversion (from ScalaField to BaseField) in the range_circuit function?
P.S., here is my code range.txt in the text format. I am testing the code by placing it in the /examples/ directory.

[Dependency] Remove dependency of jf-plonk from jf-primitives

As suggested by @alxiong

  • split out the constraint system definition into its own crate: jf-relation, which includes the PlonkCircuit (aka our constraint system) and our gates over
  • then, we keep the proof system (jf_plonk::proof module) as jf-plonk which depends on jf-relation
  • our jf-primitives would depend on jf-relation

Evaluate batch-affine MSM circuit complexity

We may be able to reduce constraint count for MSM a bit further.

https://hackmd.io/@tazAymRSQCGXTUKkbh1BAg/Sk27liTW9

https://github.com/Manta-Network/wasm-zkp-challenge/blob/optimized_pippenger/src/pippenger_msm.rs

arkworks-rs/algebra#380, https://github.com/AztecProtocol/barretenberg/blob/f45c27ecd70a3c5607cf30ad5e36bcb4b7385b6d/barretenberg/src/aztec/ecc/curves/bn254/scalar_multiplication/scalar_multiplication.cpp#L114

Let's consider native computation. When we add a projective point with an affine point, we use mixed-addition formula and require 11 field multiplications. In batch affine, we add two vectors of affine points and require only 6 field multiplications and 0 division amortized for each point addition. This saves a lot and motivates us to use batch affine in MSM.

The improvement are not likely to hold for circuits, but it would be interesting to find out.

submit the crate to crates.io

Tasks:

  • Decide on the name under which to publish
  • Replace all "git" dependencies with crates.io dependencies (can't publish if depending on "git", see the dependency guide)
    • espresso-systems-common
    • tagged-base64
    • arkworks deps (should be resolved after #45)

A reference / document / README on MerkleTree design or decisions?

I've been looking (not too deeply) at the jellyfish and seahorse libraries and wanted to ask for a pointer or a link to a good resource on the design & decisions around the MerkleTree and KV store.

1. Choice of Ternary tree

In src/merkle_tree.rs, it says:

At a high level the Merkle tree is a ternary tree

Q1: What was the reasoning behind a ternary tree specifically?

2. Sparse Tree Implementation

In seahorse/src/sparse_merkle_tree.rs, a SparseMerkleTree was implemented.

Q2: I did not dive to deep into the implementation and was wondering if it followed a standard design (e.g. JMT, PMT) or other?

3. Key-Value Storage Databse Engine

From the CAPE System Components page, I found the following:

Alternative implementations of CAPE relayers may maintain a lightweight state of the CAPE system, allowing the relayer to validate CAPE transactions locally before forwarding them to the CAPE contract on Ethereum

Similarly, from another section on the same page:

The records Merkle tree stores every record commitment produced in the system. The CAPE smart contract stores a small digest of this set called the Merkle root

Q3: What is the key-value store database engine backing this?

Ark-sponge compatibilty

Currently we have rescue-based sponge construction whereas ark-sponge repo supports Poseidon. But it may be beneficial to be compliant to their trait.

[API] Refactor Merkle tree and its gadget

Current API for MT and its gadgets need some refactoring, e.g. here's the code we use in ZPrice to generate a circuit of lots of Merkle Proof verification:

    // construct circuit constraining membership proof check
    let mut circuit = PlonkCircuit::new();
    // add root as a public input
    let root_var = circuit.create_public_variable(root)?;
    for (uid, proof) in merkle_proofs.iter().enumerate() {
        let leaf_var = circuit.create_variable(leaves[uid])?;
        let proof_var = AccMemberWitnessVar::new(&mut circuit, proof)?;
        let acc_elem_var = AccElemVars {
            uid: proof_var.uid,
            elem: leaf_var,
        };

        let claimed_root_var = circuit.compute_merkle_root(acc_elem_var, &proof_var.merkle_path)?;

        // enforce matching merkle root
        circuit.equal_gate(root_var, claimed_root_var)?;
    }

    // sanity check: the circuit must be satisfied.
    assert!(circuit.check_circuit_satisfiability(&[root]).is_ok());
  • mixed style of Struct::new() and field filling to instantiate structs
  • numerous MerklePath, MerkleNode etc are slightly confusing
  • gadget APIs are not intuitive at all

[API]: conform to standardized SNARK traits

Current SNARK APIs are slightly customized (many historical reasons), and this issue aims to conform to ark_snark's definition.

note: works will be performed on cap-rollup branch only, only merged into main on much distant horizon

range proof with various size

Currently range proof is only available for table of size 2^16.
We may want to use different tables (with proper domain separation #48) for customized sizes.

improve merkle tree's hash logic

currently merkle tree hash is implemented as

/// Hash function used to compute an internal node value
/// * `a` - first input value (e.g.: left child value)
/// * `b` - second input value (e.g.: middle child value)
/// * `c` - third input value (e.g.: right child value)
/// * `returns` - rescue_sponge_no_padding(a,b,c)
pub(crate) fn hash<F: RescueParameter>(
    a: &NodeValue<F>,
    b: &NodeValue<F>,
    c: &NodeValue<F>,
) -> NodeValue<F> {
    let perm = Permutation::default();
    let digest = perm.sponge_no_padding(&[a.0, b.0, c.0], 1).unwrap()[0];
    NodeValue(digest)
}

Every time a hash function is called, the same permutation initialization is called. This incurs a non-negligible cost.

hash/ed_on_bn254::init  time:   [28.953 us 28.962 us 28.971 us]
hash/ed_on_bn254::digest                        
                        time:   [346.65 us 346.80 us 346.96 us]

We should separate the initialization and the actual hash function so that it gets initialized for only once.
This will save around 29/(29 + 346) = 7.7%.

extract turbo plonk

Created a dedicated branch for turbo plonk. Let's work on this branch by submitting PRs against it (like what we did for plonk verifier).

  • #69
  • refactoring the code with better modularity
    • shall we allow for operators overloading? (future work)
  • gitbook
  • #71
  • Generate SRS, PK, VK for large enough circuit and version-control their sumcheck files in this repo while uploading the actual binary file to some AWS S3 bucket. (@zhenfeizhang)

[Bug] can't run test coverage

The error after running ./scripts/test_coverage.sh in nix-shell:

+ IGNORED_FILES='--ignore **/errors.rs               --ignore **/src/bin/*               --ignore transactions/src/parameters.rs               --ignore transactions/src/bench_utils/*              '
+ cargo +nightly install grcov
error: no such subcommand: `+nightly`
+ export CARGO_INCREMENTAL=0
+ CARGO_INCREMENTAL=0
+ export 'RUSTFLAGS=-Zprofile -Ccodegen-units=1 -Copt-level=3 -Clink-dead-code -Coverflow-checks=off -Zpanic_abort_tests -Cpanic=abort'
+ RUSTFLAGS='-Zprofile -Ccodegen-units=1 -Copt-level=3 -Clink-dead-code -Coverflow-checks=off -Zpanic_abort_tests -Cpanic=abort'
+ export RUSTDOCFLAGS=-Cpanic=abort
+ RUSTDOCFLAGS=-Cpanic=abort
+ rm -rf './target/**/*.gcda'
+ cargo +nightly build
error: no such subcommand: `+nightly`
+ cargo +nightly test --lib
error: no such subcommand: `+nightly`
+ grcov . -s . --binary-path ./target/debug/ -t html --branch --ignore-not-existing --ignore '**/errors.rs' --ignore '**/src/bin/*' --ignore transactions/src/parameters.rs --ignore 'transactions/src/bench_utils/*' -o ./target/debug/coverage/
./scripts/test_coverage.sh: line 15: grcov: command not found
+ echo 'Coverage report available at target/debug/coverage/index.html.'
Coverage report available at target/debug/coverage/index.html.

using rayon while keeping no_std support

Currently, I implemented a very simplistic to optionally turn on rayon and use its par_iter():

/// # Usage
/// let v = [1, 2, 3, 4, 5];
/// let sum = parallelizable_slice_iter(&v).sum();
///
/// // the above code is a shorthand for (thus equivalent to)
/// #[cfg(feature = "parallel")]
/// let sum = v.par_iter().sum();
/// #[cfg(not(feature = "parallel"))]
/// let sum = v.iter().sum();
#[cfg(feature = "parallel")]
pub fn parallelizable_slice_iter<T: Sync>(data: &[T]) -> rayon::slice::Iter<T> {
    use rayon::iter::IntoParallelIterator;
    data.into_par_iter()
}

#[cfg(not(feature = "parallel"))]
pub fn parallelizable_slice_iter<T>(data: &[T]) -> ark_std::slice::Iter<T> {
    data.iter()
}

but there's already an existing, better, more comprehensive solution by plonky2 team: maybe_rayon
given that they recently added MIT + Apache2 license, we should consider switching to that.

[Constraint] Introduce ConstraintSystemReference idea for friendly API

From @zhenfeizhang in #94 (comment)

In general I want to advocate my "circuit ref" idea. For example

struct BoolVar<'a> {
  index: Variable,
  cs: &'a ConstraintSystem
}

On top of overloading operators here are some additional thoughts:

  • to access the variable, we should use an API get_index(&self)->Variable -- i think it is a bit cleaner than into()
    • it makes more sense to me to implement Into/From for Vec<BoolVar> and Variable, in both directions, which are binary (de)composition
  • to create new variables we should use associated function BoolVar::new(cs: &ConstraintSystem, value: bool) rather than Circuit::create_bool_variable(...) and so on...
  • to check variable bound we can simply call bool_var.check_bound(), and we do not need to pass parameters
  • add CSRef for BoolVar
  • add CSRef for PointVar
  • add CSRef for Variable

implement BLS and BLS-VRF

  • define a generic signature trait and move Schnorr under that trait #53
  • implement BLS signature #55
  • define a generic VRF trait #55
  • implement BLS-VRF #55
  • (Bonus) implement EC-VRF

audit/improve KZG10 code

the main bottleneck of Jellyfish currently are:

  • FFT
  • KZG commitment

And KZG dominants.

It appears that arkwork's KZG implementation may not be optimized, for example:
arkworks-rs/poly-commit#98

The non-optimization in the example is not critical to us yet because it is for the verifier, and CAPE uses solidity verifier rather than rust verifier (cc @philippecamacho).

Consider using Snafu to define Error types

As a follow-up of #84 where we remove Snafu on jf-utils's TaggedBlobError temporarily.

We aim to try to use Snafu among all jf-* crates and enabled for all the error types we defined and we internally depend on (such as TBase64Error etc)

cc @jbearer

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.