This PR turns on outlining and adds a test that triggers the outlining. Previous tests all would not trigger outlining and therefore did not discover this problem earlier.

This PR is expected to fail before https://github.com/arkworks-rs/snark/pull/331 is merged.

This closes #56.

A serious limitation of the benchmark is that it does not quantify the "weight" / "nonzero" / "density" yet. Any idea or suggestion?

This, if good enough, closes https://github.com/arkworks-rs/marlin/issues/31.

I'm trying to get a dummy test compiling with the IPA_PC scheme and Marlin / Pallas but my compiler says it doesn't implement the PolynomialCommitment trait which I can see it does (unless it just doesn't for this specific curve type)

Am I setting things up incorrectly or does it not work for Fp256?

error[E0277]: the trait bound `InnerProductArgPC<ark_ec::models::short_weierstrass_jacobian::GroupAffine<PallasParameters>, Blake2s, DensePolynomial<Fp256<FrParameters>>>: ark_poly_commit::PolynomialCommitment<Fp256<FrParameters>, DensePolynomial<Fp256<FrParameters>>>` is not satisfied
   --> src/tests.rs:79:19
    |
79  |           let srs = Marlin::<
    |  ___________________^
80  | |             $bench_field,
81  | |             InnerProductArgPC<$affine_curve, Blake2s, DensePolynomial<$bench_field>>,
82  | |             Blake2s,
83  | |         >::universal_setup(65536, 65536, 65536, rng)
    | |__________________________^ the trait `ark_poly_commit::PolynomialCommitment<Fp256<FrParameters>, DensePolynomial<Fp256<FrParameters>>>` is not implemented for `InnerProductArgPC<ark_ec::models::short_weierstrass_jacobian::GroupAffine<PallasParameters>, Blake2s, DensePolynomial<Fp256<FrParameters>>>`

I'm under the impression that this is the implementation that I thought should work: https://github.com/arkworks-rs/poly-commit/blob/constraints/src/ipa_pc/mod.rs#L304. Nonetheless, I'm evoking this with the following args:

fn bench_prove() {
    marlin_prove_bench!(pallas, ark_pallas::Fr, ark_pallas::Affine);
}

fn bench_verify() {
    marlin_verify_bench!(pallas, ark_pallas::Fr, ark_pallas::Affine);
}

As of subject. There seems to be an incompatibility with the latest zexe.

The culprit is plausibly this commit in zexe: https://github.com/scipr-lab/zexe/commit/ecc6057971c1bb1595ca5c5537afc5e0561a38d5#diff-4cca21435ee820e184b16118ad656f07

This look like a breaking change in ff_fft crate. I suggest including a working Cargo.lock into the code, or pinning to a specific commit when you use git dependencies.

ff-fft = { git = "https://github.com/scipr-lab/zexe/", default-features = false }

Currently Marlin includes its own FiatShamirRng which uses chacha20 and a generic Digest function (instantiated with I think blake2s).

Would you be interested in a PR that replaces it with Merlin?

In contrast to the existing implementation, this provides more secure prover randomness generation, allows binding Marlin proofs to arbitrary structured application data rather than just a single domain separator string, or to transcripts of other proof protocols, and potentially makes the implementation slightly cleaner (although the FiatShamirRng API is already pretty reasonable). It also simplifies the (cryptographic) dependencies, as rather than relying on the security of both chacha20 and blake2s (or some other hash function), the security relies only on keccak-f/1600.

I would be happy to create a PR for this change but only if it's one that you'd actually want.

Mistake in definition of b(X)

Description

closes: #XXXX

Before we can merge this PR, please make sure that all the following items have been checked off. If any of the checklist items are not applicable, please leave them but write a little note why.

• [ ] Targeted PR against correct branch (master)
• [ ] Linked to Github issue with discussion and accepted design OR have an explanation in the PR that describes this work.
• [ ] Wrote unit tests
• [ ] Updated relevant documentation in the code
• [ ] Added a relevant changelog entry to the Pending section in CHANGELOG.md
• [ ] Re-reviewed Files changed in the Github PR explorer

Description

This PR abstracts the functionality needed for creating Fiat-Shamir challenges in Marlin. It allows for choices of other primitives instead of the hard-coded ChaChaRng with hash seed currently used. This hard-coded choice makes it difficult to use Marlin for some applications, e.g., in a solidity verifier where keccak would be preferred over chacha (https://github.com/Zokrates/ZoKrates/pull/1103).

Other projects (https://github.com/AleoHQ/snarkVM/blob/testnet2/marlin/src/fiat_shamir/traits/fiat_shamir.rs#L28) have similarly abstracted out the Fiat-Shamir functionality for the purpose of using a SNARK-friendly hash.

This PR can serve as a quick fix to allow customizability of the Marlin proof system. If a more comprehensive solution that supports constraints is desired (following the above link), perhaps that can be added in the future.

This PR does the following:

• Adds a FiatShamirRng trait to abstract the functionality needed for creating Fiat-Shamir challenges
• Adds a SimpleHashFiatShamirRng struct that implements the functionality using the existing SeedableRng and Digest composition (the previous hard-coded functionality is obtained by instantiating with ChaChaRng)

Test strategy: cargo test succeeds for Marlin instantiated with SimpleHashFiatShamirRng with ChaChaRng and Blake2s.

Checklist

• [x] Targeted PR against correct branch (master)
• [x] Linked to Github issue with discussion and accepted design OR have an explanation in the PR that describes this work.
• [ ] Wrote unit tests (tests pass, no functionality change -- just a refactor)
• [x] Updated relevant documentation in the code
• [x] Added a relevant changelog entry to the Pending section in CHANGELOG.md (not sure what to add here)
• [x] Re-reviewed Files changed in the Github PR explorer

Hello arkworks-rs, thanks for your the greater work Marlin. While reading the paper I encountered a question.

In page 28, section 5.3.2, it says: However, in the same page equation (6) it says sums to on H. Therefor, according the univariate sumcheck for subgroups protocol introduced in section 5.1, should be written as: if is not zero. Is my understanding about wrong or something I have missed? Any help is appreciated, thanks.

Updates the requirements on digest to permit the latest version.

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Thanks for the awesome work.

I think poly-commit does have these features.

the package `marlin` depends on `poly-commit`, with features: `parallel, std` but `poly-commit` does not have these features.


failed to select a version for `poly-commit` which could resolve this conflict

If I remove these features, I am still facing other issues probably because of the latest update to zexe library. I think everything works for commit #4ae139c commit in the zexe library if that helps in any debugging.

Description

Introduce the ability to create a sponge from a rate argument.

This should later upstream to ark-sponge; for now, we are avoiding breaking changes in 0.3

Before we can merge this PR, please make sure that all the following items have been checked off. If any of the checklist items are not applicable, please leave them but write a little note why.

• [ ] Targeted PR against correct branch (master)
• [ ] Linked to Github issue with discussion and accepted design OR have an explanation in the PR that describes this work.
• [ ] Wrote unit tests
• [ ] Updated relevant documentation in the code
• [ ] Added a relevant changelog entry to the Pending section in CHANGELOG.md
• [ ] Re-reviewed Files changed in the Github PR explorer

Description

The branch constraints isn't building with latest dependencies.

Open questions

• [ ] We declare DensePolynomial<F> concretely in some places, and expect the generic PC::BatchProof in others
• [ ] fiat_shamir::AlgebraicSponge looks duplicate to ark_sponge::CryptographicSponge and should possibly be replaced

closes: #87

• [ ] Targeted PR against correct branch (master) - N/A, this aims to fix constraints so the latter can be merged to master
• [x] Linked to Github issue with discussion and accepted design OR have an explanation in the PR that describes this work.
• [ ] Wrote unit tests
• [ ] Updated relevant documentation in the code
• [ ] Added a relevant changelog entry to the Pending section in CHANGELOG.md
• [x] Re-reviewed Files changed in the Github PR explorer

Summary of Bug

The branch constraints isn't building with latest dependencies.

Version

(https://github.com/arkworks-rs/marlin/commit/903c741e038be240d1c80622a843c4b011965d75)

Steps to Reproduce

$ cargo build

Summary

My notes on how to implement Marlin + Plookup: https://hackmd.io/@gPH8I-Z5RcSMH2KTXLDeDg/BJcMTU9wO @Pratyush you may still recognize this. I don't think I'll have time to work on this; I'll let another enthusiastic cryptographer do so if they so desire.

Problem Definition

Proposal

For Admin Use

• [ ] Not duplicate issue
• [ ] Appropriate labels applied
• [ ] Appropriate contributors tagged
• [ ] Contributor assigned/self-assigned

Summary of Bug

While adding Marlin as a backend for ZoKrates, I'm hitting an underflow panic during the setup phase:

This works (1 public input: the return value):

def main(private field x) -> field:
   return x**2

This fails (1 public input: the return value):

def main(private field x) -> field:
   return x

attempt to subtract with overflow ark-marlin-0.2.0/src/ahp/mod.rs:108:28

It seems like k_size is expected to be bigger than 2, but in this case isn't.

Version

0.2.0

Steps to Reproduce

For these examples I used a universal setup degree of 5 for all parameters.

Description

Currently, the witness polynomial multiplication in the second round of the AHP requires performing an FFT with a domain of size 4 * |H|. This change distributes the multiplication so that it only requires an FFT with a domain of size 2 * |H| along with some cheap multiplications/additions.

Running marlin-benches on a fairly powerful machine from master:

per-constraint proving time for Bls12_381: 51662 ns/constraint
per-constraint proving time for MNT4_298: 45649 ns/constraint
per-constraint proving time for MNT6_298: 55951 ns/constraint
per-constraint proving time for MNT4_753: 321626 ns/constraint

Running marlin-benches on the same machine from this PR:

per-constraint proving time for Bls12_381: 50834 ns/constraint
per-constraint proving time for MNT4_298: 46081 ns/constraint
per-constraint proving time for MNT6_298: 54172 ns/constraint
per-constraint proving time for MNT4_753: 320387 ns/constraint

So it seems to give an overall slight latency improvement and reduces the memory overhead of proving. I would guess that performance gains would be more noticeable on weaker machines.

This PR depends on https://github.com/arkworks-rs/algebra/pull/258

Before we can merge this PR, please make sure that all the following items have been checked off. If any of the checklist items are not applicable, please leave them but write a little note why.

• [x] Targeted PR against correct branch (master)
• [x] Linked to Github issue with discussion and accepted design OR have an explanation in the PR that describes this work.
• [ ] Wrote unit tests
• [x] Updated relevant documentation in the code
• [ ] Added a relevant changelog entry to the Pending section in CHANGELOG.md
• [ ] Re-reviewed Files changed in the Github PR explorer