Spartan: High-speed zkSNARKs without trusted setup
Spartan is a high-speed zero-knowledge proof system, a cryptographic primitive that enables a prover to prove a mathematical statement to a verifier without revealing anything besides the validity of the statement. This repository provides libspartan, a Rust library that implements a zero-knowledge succinct non-interactive argument of knowledge (zkSNARK), which is a type of zero-knowledge proof system with short proofs and fast verification times. The details of the Spartan proof system are described in our paper published at CRYPTO 2020. The security of the Spartan variant implemented in this library is based on the discrete logarithm problem in the random oracle model.
A simple example application is proving the knowledge of a secret s such that H(s) == d for a public d, where H is a cryptographic hash function (e.g., SHA-256, Keccak). A more complex application is a database-backed cloud service that produces proofs of correct state machine transitions for auditability. See this paper for an overview and this paper for details.
Note that this library has not received a security review or audit.
We now highlight Spartan's distinctive features.
No "toxic" waste: Spartan is a transparent zkSNARK and does not require a trusted setup. So, it does not involve any trapdoors that must be kept secret or require a multi-party ceremony to produce public parameters.
General-purpose: Spartan produces proofs for arbitrary NP statements. libspartan supports NP statements expressed as rank-1 constraint satisfiability (R1CS) instances, a popular language for which there exists efficient transformations and compiler toolchains from high-level programs of interest.
Sub-linear verification costs: Spartan is the first transparent proof system with sub-linear verification costs for arbitrary NP statements (e.g., R1CS).
Standardized security: Spartan's security relies on the hardness of computing discrete logarithms (a standard cryptographic assumption) in the random oracle model. libspartan uses ristretto255, a prime-order group abstraction atop curve25519 (a high-speed elliptic curve). We use curve25519-dalek for arithmetic over ristretto255.
State-of-the-art performance: Among transparent SNARKs, Spartan offers the fastest prover with speedups of 36–152× depending on the baseline, produces proofs that are shorter by 1.2–416×, and incurs the lowest verification times with speedups of 3.6–1326×. The only exception is proof sizes under Bulletproofs, but Bulletproofs incurs slower verification both asymptotically and concretely. When compared to the state-of-the-art zkSNARK with trusted setup, Spartan’s prover is 2× faster for arbitrary R1CS instances and 16× faster for data-parallel workloads.
libspartan uses merlin to automate the Fiat-Shamir transform. We also introduce a new type called RandomTape that extends a Transcript in merlin to allow the prover's internal methods to produce private randomness using its private transcript without having to create OsRng objects throughout the code. An object of type RandomTape is initialized with a new random seed from OsRng for each proof produced by the library.
To import libspartan into your Rust project, add the following dependency to Cargo.toml:
spartan = "0.8.0"The following example shows how to use libspartan to create and verify a SNARK proof.
Some of our public APIs' style is inspired by the underlying crates we use.
…Here is another example to use the NIZK variant of the Spartan proof system:
…Finally, we provide an example that specifies a custom R1CS instance instead of using a synthetic instance
…For more examples, see examples/ directory in this repo.
libspartanInstall rustup
Switch to nightly Rust using rustup:
rustup default nightlyClone the repository:
git clone https://github.com/Microsoft/Spartan
cd SpartanTo build docs for public APIs of libspartan:
cargo docTo run tests:
RUSTFLAGS='-C target_cpu=native --cfg curve25519_dalek_backend="BACKEND"' cargo testTo build libspartan:
RUSTFLAGS='-C target_cpu=native --cfg curve25519_dalek_backend="BACKEND"' cargo build --releaseNOTE: We enable SIMD instructions in
curve25519-dalekby default, so if it fails to build remove the argument passed to curve25519_dalek in the above command.
std: enables std features (enabled by default)profile: enables fine-grained profiling information (see below for its use)libspartan depends upon rand::OsRng (internally uses getrandom crate), it has out of box support for wasm32-wasi.
For the target wasm32-unknown-unknown disable default features for spartan
and add direct dependency on getrandom with wasm-bindgen feature enabled.
[dependencies]
spartan = { version = "0.7", default-features = false }
# since spartan uses getrandom(rand's OsRng), we need to enable 'wasm-bindgen'
# feature to make it feed rand seed from js/nodejs env
# https://docs.rs/getrandom/0.1.16/getrandom/index.html#support-for-webassembly-and-asmjs
getrandom = { version = "0.1", features = ["wasm-bindgen"] }libspartan includes two benches: benches/nizk.rs and benches/snark.rs. If you report the performance of Spartan in a research paper, we recommend using these benches for higher accuracy instead of fine-grained profiling (listed below).
To run end-to-end benchmarks:
RUSTFLAGS='-C target_cpu=native --cfg curve25519_dalek_backend="BACKEND"' cargo benchBuild libspartan with profile feature enabled. It creates two profilers: ./target/release/snark and ./target/release/nizk.
These profilers report performance as depicted below (for varying R1CS instance sizes). The reported performance is from running the profilers on a Microsoft Surface Laptop 3 on a single CPU core of Intel Core i7-1065G7 running Ubuntu 20.04 (atop WSL2 on Windows 10). See Section 9 in our paper to see how this compares with other zkSNARKs in the literature.
……See LICENSE
See CONTRIBUTING
No open issues yet, or sync has not completed.