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.

Highlights

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.

Implementation details

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.

Examples

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.

extern crate libspartan;
extern crate merlin;
use libspartan::{Instance, SNARKGens, SNARK};
use merlin::Transcript;
fn main() {
    // specify the size of an R1CS instance
    let num_vars = 1024;
    let num_cons = 1024;
    let num_inputs = 10;
    let num_non_zero_entries = 1024;

    // produce public parameters
    let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_non_zero_entries);

    // ask the library to produce a synthentic R1CS instance
    let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);

    // create a commitment to the R1CS instance
    let (comm, decomm) = SNARK::encode(&inst, &gens);

    // produce a proof of satisfiability
    let mut prover_transcript = Transcript::new(b"snark_example");
    let proof = SNARK::prove(&inst, &comm, &decomm, vars, &inputs, &gens, &mut prover_transcript);

    // verify the proof of satisfiability
    let mut verifier_transcript = Transcript::new(b"snark_example");
    assert!(proof
      .verify(&comm, &inputs, &mut verifier_transcript, &gens)
      .is_ok());
    println!("proof verification successful!");
}

Here is another example to use the NIZK variant of the Spartan proof system:

extern crate libspartan;
extern crate merlin;
use libspartan::{Instance, NIZKGens, NIZK};
use merlin::Transcript;
fn main() {
    // specify the size of an R1CS instance
    let num_vars = 1024;
    let num_cons = 1024;
    let num_inputs = 10;

    // produce public parameters
    let gens = NIZKGens::new(num_cons, num_vars, num_inputs);

    // ask the library to produce a synthentic R1CS instance
    let (inst, vars, inputs) = Instance::produce_synthetic_r1cs(num_cons, num_vars, num_inputs);

    // produce a proof of satisfiability
    let mut prover_transcript = Transcript::new(b"nizk_example");
    let proof = NIZK::prove(&inst, vars, &inputs, &gens, &mut prover_transcript);

    // verify the proof of satisfiability
    let mut verifier_transcript = Transcript::new(b"nizk_example");
    assert!(proof
      .verify(&inst, &inputs, &mut verifier_transcript, &gens)
      .is_ok());
    println!("proof verification successful!");
}

Finally, we provide an example that specifies a custom R1CS instance instead of using a synthetic instance

#![allow(non_snake_case)]
extern crate curve25519_dalek;
extern crate libspartan;
extern crate merlin;
use curve25519_dalek::scalar::Scalar;
use libspartan::{InputsAssignment, Instance, SNARKGens, VarsAssignment, SNARK};
use merlin::Transcript;
use rand::rngs::OsRng;

fn main() {
  // produce a tiny instance
  let (
    num_cons,
    num_vars,
    num_inputs,
    num_non_zero_entries,
    inst,
    assignment_vars,
    assignment_inputs,
  ) = produce_tiny_r1cs();

  // produce public parameters
  let gens = SNARKGens::new(num_cons, num_vars, num_inputs, num_non_zero_entries);

  // create a commitment to the R1CS instance
  let (comm, decomm) = SNARK::encode(&inst, &gens);

  // produce a proof of satisfiability
  let mut prover_transcript = Transcript::new(b"snark_example");
  let proof = SNARK::prove(
    &inst,
    &comm,
    &decomm,
    assignment_vars,
    &assignment_inputs,
    &gens,
    &mut prover_transcript,
  );

  // verify the proof of satisfiability
  let mut verifier_transcript = Transcript::new(b"snark_example");
  assert!(proof
    .verify(&comm, &assignment_inputs, &mut verifier_transcript, &gens)
    .is_ok());
  println!("proof verification successful!");
}

fn produce_tiny_r1cs() -> (
 usize,
 usize,
 usize,
 usize,
 Instance,
 VarsAssignment,
 InputsAssignment,
) {
  // We will use the following example, but one could construct any R1CS instance.
  // Our R1CS instance is three constraints over five variables and two public inputs
  // (Z0 + Z1) * I0 - Z2 = 0
  // (Z0 + I1) * Z2 - Z3 = 0
  // Z4 * 1 - 0 = 0

  // parameters of the R1CS instance rounded to the nearest power of two
  let num_cons = 4;
  let num_vars = 5;
  let num_inputs = 2;
  let num_non_zero_entries = 5;

  // We will encode the above constraints into three matrices, where
  // the coefficients in the matrix are in the little-endian byte order
  let mut A: Vec<(usize, usize, [u8; 32])> = Vec::new();
  let mut B: Vec<(usize, usize, [u8; 32])> = Vec::new();
  let mut C: Vec<(usize, usize, [u8; 32])> = Vec::new();

  // The constraint system is defined over a finite field, which in our case is
  // the scalar field of ristreeto255/curve25519 i.e., p =  2^{252}+27742317777372353535851937790883648493
  // To construct these matrices, we will use `curve25519-dalek` but one can use any other method.

  // a variable that holds a byte representation of 1
  let one = Scalar::ONE.to_bytes();

  // R1CS is a set of three sparse matrices A B C, where is a row for every
  // constraint and a column for every entry in z = (vars, 1, inputs)
  // An R1CS instance is satisfiable iff:
  // Az \circ Bz = Cz, where z = (vars, 1, inputs)

  // constraint 0 entries in (A,B,C)
  // constraint 0 is (Z0 + Z1) * I0 - Z2 = 0.
  // We set 1 in matrix A for columns that correspond to Z0 and Z1
  // We set 1 in matrix B for column that corresponds to I0
  // We set 1 in matrix C for column that corresponds to Z2
  A.push((0, 0, one));
  A.push((0, 1, one));
  B.push((0, num_vars + 1, one));
  C.push((0, 2, one));

  // constraint 1 entries in (A,B,C)
  A.push((1, 0, one));
  A.push((1, num_vars + 2, one));
  B.push((1, 2, one));
  C.push((1, 3, one));

  // constraint 3 entries in (A,B,C)
  A.push((2, 4, one));
  B.push((2, num_vars, one));

  let inst = Instance::new(num_cons, num_vars, num_inputs, &A, &B, &C).unwrap();

  // compute a satisfying assignment
  let mut csprng: OsRng = OsRng;
  let i0 = Scalar::random(&mut csprng);
  let i1 = Scalar::random(&mut csprng);
  let z0 = Scalar::random(&mut csprng);
  let z1 = Scalar::random(&mut csprng);
  let z2 = (z0 + z1) * i0; // constraint 0
  let z3 = (z0 + i1) * z2; // constraint 1
  let z4 = Scalar::ZERO; //cons