A Rust library for the Marlin preprocessing zkSNARK

Overview

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

Indexer Prover

Verifier

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.

Multi-threaded scaling of Marlin AHP with the PC scheme from [CHMMVW20] Multi-threaded scaling of Marlin AHP with the PC scheme from [MBKM19]

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.

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.

Comments
  • Fix outlining

    Fix outlining

    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.

    opened by weikengchen 8
  • Add the benchmark

    Add the benchmark

    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.

    opened by weikengchen 8
  • Trouble compiling Marlin with IPA-PC

    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);
    }
    
    opened by drewstone 6
  • Master build is broken

    Master build is broken

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

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

    opened by matteocam 5
  • Compile error

    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 }
    
    opened by juchiast 5
  • Replacing the `FiatShamirRng` with Merlin?

    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.

    opened by hdevalence 5
  • Update diagram.tex

    Update diagram.tex

    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
    opened by jon-chuang 4
  • Unify the interface for Fiat-Shamir transform

    Unify the interface for Fiat-Shamir transform

    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
    opened by nirvantyagi 3
  • A question in Marlin paper in section 5.3.2

    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.

    opened by wang12d 3
  • Update digest requirement from 0.8 to 0.9

    Update digest requirement from 0.8 to 0.9

    Updates the requirements on digest to permit the latest version.

    Commits

    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.


    Dependabot commands and options

    You can trigger Dependabot actions by commenting on this PR:

    • @dependabot rebase will rebase this PR
    • @dependabot recreate will recreate this PR, overwriting any edits that have been made to it
    • @dependabot merge will merge this PR after your CI passes on it
    • @dependabot squash and merge will squash and merge this PR after your CI passes on it
    • @dependabot cancel merge will cancel a previously requested merge and block automerging
    • @dependabot reopen will reopen this PR if it is closed
    • @dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually
    • @dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)
    • @dependabot use these labels will set the current labels as the default for future PRs for this repo and language
    • @dependabot use these reviewers will set the current reviewers as the default for future PRs for this repo and language
    • @dependabot use these assignees will set the current assignees as the default for future PRs for this repo and language
    • @dependabot use this milestone will set the current milestone as the default for future PRs for this repo and language
    • @dependabot badge me will comment on this PR with code to add a "Dependabot enabled" badge to your readme

    Additionally, you can set the following in your Dependabot dashboard:

    • Update frequency (including time of day and day of week)
    • Pull request limits (per update run and/or open at any time)
    • Out-of-range updates (receive only lockfile updates, if desired)
    • Security updates (receive only security updates, if desired)
    dependencies 
    opened by dependabot-preview[bot] 3
  • Unable to build marlin

    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.

    opened by sanket1729 3
  • Add sponge module

    Add sponge module

    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
    opened by vlopes11 0
  •  Fix and update dependencies to 0.3

    Fix and update dependencies to 0.3

    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
    opened by vlopes11 2
  • Fix and update dependencies to 0.3

    Fix and update dependencies to 0.3

    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

    opened by vlopes11 0
  • Notes on Implementing Marlin + Plookup

    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
    opened by jon-chuang 0
  • Underflow panic

    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.

    T-bug D-easy P-medium 
    opened by Schaeff 3
  • Witness multiplication optimization

    Witness multiplication optimization

    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
    opened by ryanleh 0
Releases(v0.3.0)
Owner
arkworks
An ecosystem for developing and programming with zkSNARKs
arkworks
The Light Protocol program verifies zkSNARK proofs to enable anonymous transactions on Solana.

Light Protocol DISCLAIMER: THIS SOFTWARE IS NOT AUDITED. Do not use in production! Tests cd ./program && cargo test-bpf deposit_should_succeed cd ./pr

null 34 Nov 20, 2022
L2 validity rollup combined with blind signatures over elliptic curves inside zkSNARK, to provide offchain anonymous voting with onchain binding execution on Ethereum

blind-ovote Blind-OVOTE is a L2 voting solution which combines the validity rollup ideas with blind signatures over elliptic curves inside zkSNARK, to

Aragon ZK Research 3 Nov 18, 2022
A Rust library for working with Bitcoin SV

Rust-SV A library to build Bitcoin SV applications in Rust. Documentation Features P2P protocol messages (construction and serialization) Address enco

Brenton Gunning 51 Oct 13, 2022
A Rust library for generating cryptocurrency wallets

Table of Contents 1. Overview 2. Build Guide 2.1 Install Rust 2.2a Build from Homebrew 2.2b Build from Crates.io 2.2c Build from Source Code 3. Usage

Aleo 534 Nov 22, 2022
A modern TLS library in Rust

Rustls is a modern TLS library written in Rust. It's pronounced 'rustles'. It uses ring for cryptography and libwebpki for certificate verification. S

ctz 3.9k Nov 27, 2022
Sodium Oxide: Fast cryptographic library for Rust (bindings to libsodium)

sodiumoxide |Crate|Documentation|Gitter| |:---:|:-----------:|:--------:|:-----:|:------:|:----:| |||| NaCl (pronounced "salt") is a new easy-to-use h

sodiumoxide 642 Nov 12, 2022
rabe is an Attribute Based Encryption library, written in Rust

Rabe rabe is a rust library implementing several Attribute Based Encryption (ABE) schemes using a modified version of the bn library of zcash (type-3

Fraunhofer AISEC 51 Nov 1, 2022
A Rust library for lattice-based additive homomorphic encryption.

Cupcake Cupcake is an efficient Rust library for the (additive version of) Fan-Vercauteren homomorphic encryption scheme, offering capabilities to enc

Facebook Research 364 Dec 3, 2022
Mundane is a Rust cryptography library backed by BoringSSL that is difficult to misuse, ergonomic, and performant (in that order).

Mundane Mundane is a Rust cryptography library backed by BoringSSL that is difficult to misuse, ergonomic, and performant (in that order). Issues and

Google 1k Nov 10, 2022
The most advanced Merkle tree library for Rust

rs-merkle rs-merkle is the most advanced Merkle tree library for Rust. Basic features include building a Merkle tree, creation, and verification of Me

Anton Suprunchuk 80 Nov 23, 2022
A wallet library for Elements / Liquid written in Rust!

EDK Elements Dev Kit A modern, lightweight, descriptor-based wallet library for Elements / Liquid written in Rust! Inspired by BDK for Elements & Liqu

luca vaccaro 11 Dec 11, 2021
Pairing cryptography library in Rust

bn This is a pairing cryptography library written in pure Rust. It makes use of the Barreto-Naehrig (BN) curve construction from [BCTV2015] to provide

Electric Coin Company Prototypes and Experiments 137 Aug 27, 2022
Pairing cryptography library in Rust

bn This is a pairing cryptography library written in pure Rust. It makes use of the Barreto-Naehrig (BN) curve construction from [BCTV2015] to provide

Parity Technologies 23 Apr 22, 2022
Aya is an eBPF library for the Rust programming language, built with a focus on developer experience and operability.

Aya API docs | Chat | Aya-Related Projects Overview eBPF is a technology that allows running user-supplied programs inside the Linux kernel. For more

null 1.4k Nov 25, 2022
A Rust Library of China's Standards of Encryption Algorithms (SM2/3/4)

Libsm Libsm is an open source pure rust library of China Cryptographic Algorithm Standards. It is completed by a collaborative effort between the Cryp

CITAHub 146 Nov 7, 2022
A library to help you sew up your Ethereum project with Rust and just like develop in a common backend

SewUp Secondstate EWasm Utility Program, a library helps you sew up your Ethereum project with Rust and just like development in a common backend. The

Second State 47 Nov 25, 2022
Rust FFI bindings for StarkWare's crypto-cpp library

starkware-crypto-rs Rust FFI bindings for StarkWare's crypto-cpp library Note that currently target x86_64-pc-windows-msvc is not supported. If you're

Jonathan LEI 11 Aug 22, 2022
An implementation of the paper "Honey Badger of BFT Protocols" in Rust. This is a modular library of consensus.

Honey Badger Byzantine Fault Tolerant (BFT) consensus algorithm Welcome to a Rust library of the Honey Badger Byzantine Fault Tolerant (BFT) consensus

null 333 Nov 10, 2022
Enigma Core library. The domain: Trusted and Untrusted App in Rust.

Enigma Core library Service Master Develop CI Badge Pure Rust Enclave && Untrusted in Rust. Core is part of the Enigma node software stack. The Core c

SCRT Labs 89 Sep 14, 2022