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

A subtask of issue #1

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)

should we add more example code? both for downstream user, and for potential contributor to this library?

Originally posted by @alxiong in #13 (comment)

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

We have not encountered a case where hash to group is necessary. So this is a low priority for now.

We may consider implement

• rejection sampling based, or
• Hash to Elliptic Curve implementation of https://datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve/

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?

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();
  }
}

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

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.

This issue aims to implement Non-membership proof gadget based on IMT.

Blocked by #98

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

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.

Refer to https://github.com/SpectrumXYZ/zk-rollup/issues/3

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)

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?

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

A subtask of #1

Update dependencies and remove sensitive info.

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

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

the test coverage of primitives/src/aead.rs is relatively low (73.6%).

something similar to https://github.com/zcash/halo2/tree/main/book would be really helpful

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.

• auto enable direnv via .envrc, so that community can easily enter our nix-shell when cd into the directory with all dep installed and ready to run (add instruction to run direnv allow inside "Getting Started")
• remove cargo husky and use nix's pre-commit hooks

@sveitser Can you help us submit a PR for ☝️ ?

Originally posted by @alxiong in #1 (comment)

Use the technique in Section 4.1 of Plookup (https://eprint.iacr.org/2020/315.pdf) to support multiple lookup tables.

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%.

Pointproof code base

• We can save the FFT for the PCS in a plonk. But a Plonk still requires FFT to compute quotient poly.
• we should get a 10% ~ 15% improvement.

Add lt, gt gates to the constraint system.

Reference: r1cs-std's cmp.rs

Maybe: change all current is_xxx() (such as here) to check_xxx() and those that enforce and will return error if not SAT, we keep using xxx_gate() (like this)?
as long as we are consistent, I'm fine.

Originally posted by @alxiong in #53 (comment)

This issue aims to implement IMT and add unit tests.

Blocked by specification work from https://github.com/EspressoSystems/cap-rollup/issues/19
Related to refactoring of current MT (since there are some trait definition and code that could be shared): #88

This issue aims to implement gadget for batch insertion for our current ternary forgettable MT.

Blocked by #88

Need to implement public APIs for comparing to constants. E.g. is_lt_const, enforce_gt_const

subtask of issue #1

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)

This issue implements member insertion into IMT.

Blocked by #98

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.

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.

A subtask of issue #1

Evaluate the cost and benefits of switching to arkworks' MarlinKZG10 instead. (as a follow-up of #80)

Current BLS and VRF uses a very naive H2G function. We may consider using BLST for BLS and VRF.

serde_cbor is unmaintained

The serde_cbor crate is unmaintained. The author has archived the github repository.

Alternatives proposed by the author:

• ciborium
• minicbor

See advisory page for additional details.

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

• 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

range-gate-lookup() should always enforce a linear combination gate after decomposing the witness (even if the witness is supposed to be less than range_size()):
https://github.com/EspressoSystems/jellyfish/blob/main/plonk/src/circuit/customized/ultraplonk/range.rs#L51

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).

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