arkworks-rs / marlin

A Rust library for the Marlin preprocessing zkSNARK

Marlin

marlin is a Rust library that implements a

preprocessing zkSNARK for R1CS
with
universal and updatable SRS

This library was initially developed as part of the Marlin paper, and is released under the MIT License and the Apache v2 License (see License).

WARNING: This is an academic prototype, and in particular has not received careful code review. This implementation is NOT ready for production use.

Overview

A zkSNARK with preprocessing achieves succinct verification for arbitrary computations, as opposed to only for structured computations. Informally, in an offline phase, one can preprocess the desired computation to produce a short summary of it; subsequently, in an online phase, this summary can be used to check any number of arguments relative to this computation.

The preprocessing zkSNARKs in this library rely on a structured reference string (SRS), which contains system parameters required by the argument system to produce/validate arguments. The SRS in this library is universal, which means that it supports (deterministically) preprocessing any computation up to a given size bound. The SRS is also updatable, which means that anyone can contribute a fresh share of randomness to it, which facilitates deployments in the real world.

The construction in this library follows the methodology introduced in the Marlin paper, which obtains preprocessing zkSNARKs with universal and updatable SRS by combining two ingredients:

• an algebraic holographic proof
• a polynomial commitment scheme

The first ingredient is provided as part of this library, and is an efficient algebraic holographic proof for R1CS (a generalization of arithmetic circuit satisfiability supported by many argument systems). The second ingredient is imported from poly-commit. See below for evaluation details.

Build guide

The library compiles on the stable toolchain of the Rust compiler. To install the latest version of Rust, first install rustup by following the instructions here, or via your platform's package manager. Once rustup is installed, install the Rust toolchain by invoking:

rustup install stable

After that, use cargo (the standard Rust build tool) to build the library:

git clone https://github.com/arkworks-rs/marlin.git
cd marlin
cargo build --release

This library comes with some unit and integration tests. Run these tests with:

cargo test

Lastly, this library is instrumented with profiling infrastructure that prints detailed traces of execution time. To enable this, compile with cargo build --features print-trace.

Benchmarks

All benchmarks below are performed over the BLS12-381 curve implemented in the ark-bls12-381 library, with the asm feature activated. Benchmarks were run on a machine with an Intel Xeon 6136 CPU running at 3.0 GHz.

Running time compared to Groth16

The graphs below compare the running time, in single-thread execution, of Marlin's indexer, prover, and verifier algorithms with the corresponding algorithms of Groth16 (the state of the art in preprocessing zkSNARKs for R1CS with circuit-specific SRS) as implemented in groth16. We evaluate Marlin's algorithms when instantiated with the PC scheme from [CHMMVW20] (denoted "M-AHP w/ PC of [CHMMVW20]"), and the PC scheme from [MBKM19] (denoted "M-AHP w/ PC of [MBKM19]").

Multi-threaded performance

The following graphs compare the running time of Marlin's prover when instantiated with the PC scheme from [CHMMVW20] (left) and the PC scheme from [MBKM19] (right) when executed with a different number of threads.

Proof size

We compare the proof size of Marlin with that of Groth16. We instantiate the Marlin SNARK with the PC scheme from [CHMMVW20], and the PC scheme from [MBKM19].

Scheme	Proof size in bytes
Marlin AHP with PC of [CHMMVW20]	880
Marlin AHP with PC of [MBKM19]	784
[Groth16]	192

License

This library is licensed under either of the following licenses, at your discretion.

• Apache License Version 2.0
• MIT License

Unless you explicitly state otherwise, any contribution that you submit to this library shall be dual licensed as above (as defined in the Apache v2 License), without any additional terms or conditions.

Reference paper

Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS
Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Psi Vesely, Nicholas Ward
EUROCRYPT 2020

Acknowledgements

This work was supported by: an Engineering and Physical Sciences Research Council grant; a Google Faculty Award; the RISELab at UC Berkeley; and donations from the Ethereum Foundation and the Interchain Foundation.

marlin's Issues

Compile error "the trait `ff_fft::domain::EvaluationDomain` cannot be made into an object"

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 }

R1CS example not verifying in Marlin

I can't tell if this is an issue with Marlin or if I'm misunderstanding the Zexe R1CS API. Any help would be appreciated.

I'm trying to verify an R1CS with the following 3 constraints:

<a, 1> * <a, 1> = <d,1>
<b, 1> * <b, 1> = <e,1>
<f, 1> * <[d,e],[1,1]> = <c,1>

Where [a,b,c,f] are public input with values [3,4,25,0], respectively, and [d,e] are the witness with values [9,16], respectively.

An attempt at hand testing this circuit is attached. Just replace the src/test.rs file with test.rs.txt (renamed back to test.rs) and add num-traits = { version = "0.2", default-features = false } to the Cargo.toml file and you should be able to run Marlin on this circuit by simply calling cargo test.

Thanks!

Unable to build marlin

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.

Why test actually failed inside the `prove_and_verify_with_tall_matrix_big`?

I run the cmd

cargo test prove_and_verify_with_tall_matrix_big -- --nocapture

and get the print info as below:

running 1 test
Called index
Called prover
Called verifier

Should not verify (i.e. verifier messages should print below):
Inner sumcheck test failed
AHP decision predicate not satisfied
PC::Check failed
Called index
Called prover
Called verifier

Should not verify (i.e. verifier messages should print below):
Inner sumcheck test failed
AHP decision predicate not satisfied
PC::Check failed
Called index
Called prover
Called verifier 
...........

question on bn254

Can ark-bn254 be plugged in to replace ark-bls12-381? We'd like to do performance comparison with several other zkSnark tools based on bn254.
Thanks!

`to_matrices` is called before `inline_all_lcs`

The current master branch may fail to index a circuit because the index function would call:

let matrices = cs.to_matrices().unwrap();

in make_matrices_square_for_indexer, before calling inline_all_lcs.

As a result, a developer would see "no symbolic LCs".

---

This problem is indeed fixed in the constraints PR #39 by removing a check in make_matrices_square_for_indexer.

See https://github.com/arkworks-rs/marlin/pull/39/files#diff-4a24591214fb91bafc31f147e9f82b39471e7a773de92a5a36f0776f434c6158R54

But I think we are not going to merge that PR soon, it may be worthwhile to fix this one sooner. (I will work to finish the constraints PR of poly-commit soon.)

Notes on Implementing Marlin + Plookup

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

[Q] why not implement UniversalSetupSNARK for Marlin

May I ask why ark_snark::UniversalSetupSNARK trait is not implemented for struct Marlin when all of its functions (including those of a trait SNARK) are being implemented with the same func signature?

Fix and update dependencies to 0.3

∂

Summary of Bug

The branch constraints isn't building with latest dependencies.

Version

(903c741)

Steps to Reproduce

$ cargo build

Master build is broken

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

The culprit is plausibly this commit in zexe:
arkworks-rs/snark@ecc6057#diff-4cca21435ee820e184b16118ad656f07

Trouble compiling Marlin with IPA-PC

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

Move Marlin to the new polynomial framework

The new polynomial framework would require much change to Marlin's data structures. This is now done together with the constraints PR.

Add simple example of using the `timer` API

when running the following command for profiling

cargo build --features timer

The error appears:

Package `marlin v0.1.0 (/home/zy/Desktop/github/marlin)` does not have these features: `timer`

How to add this feature in the package? It seems that only modifying Cargo.toml is enough, but I am not familiar with rust.....

Allow public input of size not 2^k-1

The current implementation has a restriction that the public input (excluding the common "1") is 2^k-1.

The problem is that in ark-pcd, we want to provide a universal interface regardless of the implementation. But Marlin is special. The glue code would need special wrappers to allocate new input values in the circuits and modify the input to the verifier gadget accordingly.

Thus, how about changing Marlin into supporting many public input sizes? Basically, we modify the indexer, prover, and verifier to pad the formatted public input size to 2^k.

Replacing the `FiatShamirRng` with Merlin?

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.

A question in Marlin paper in section 5.3.2

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.

Add end-to-end diagram of Marlin

This already exists in the diagram branch; we should polish it and add it to master.

rand_core module OsRng not found

While running the tests cargo test I am running into the error

error[E0425]: cannot find value 'OsRng' in module 'rand_core'

for lines 160:35 (src/ahp/mod.rs) and 52:35 (src/test.rs)

Am I missing something here? Did someone else run into this issue?

Benchmarking Marlin

What’s the easiest way to benchmark Marlin at different R1CS instance sizes?

Underflow panic

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.

Commit-and-Prove Marlin

This issue is just to remark a useful variant of Marlin with the property of commit-and-prove. Basically, the verifier does not know the input but instead obtains a commitment of the input. Later, separately, the prover may open the commitment.

Based on the diagram, it seems the main change is as follows:

• The prover sends a polynomial commitment of x and the evaluation of x on challenge \beta.
• The prover changes the corresponding opening information of the outer sumcheck.
• The verifier changes the outer sumcheck and changes the PC check for this outer sumcheck.

This variant can be a fork or a configuration option. The constraints PR would add an option for recursive, which commits the vanishing polynomials. This could be a separate option.

More discussion on commit-and-prove SNARK can be found in https://eprint.iacr.org/2019/142.

Outer check may fail due to outlining

When I test a specific circuit, it seems that the PR to replace inlining with outlining (#50) has introduced potential errors that fail the outer check.

When it happens, the prover will panic.

thread 'main' panicked at 'assertion failed: evals.get_lc_eval(&outer_sumcheck, beta)?.is_zero()', 
/home/wkchen/.cargo/git/checkouts/marlin-cee5d75828d5b0f5/839478d/src/ahp/mod.rs:174:9

This problem is not caught by the tests. As another PR shows (#53), our current test might be too weak.

Thus, my plan is:

• First of all, let me add a PR to turn off outlining so that it does not affect other projects using Marlin.
• Debug the outlining.
• Add tests over more complicated circuits.

cc people in projects that may have a dependency on Marlin @ryanleh