libsnark

libsnark: a C++ library for zkSNARK proofs

---

Authors and contacts

The libsnark library is developed by the [SCIPR Lab] project and contributors and is released under the MIT License (see the [LICENSE] file).

Copyright (c) 2012-2017 SCIPR Lab and contributors (see [AUTHORS] file).

For announcements and discussions, see the libsnark mailing list.

---

[TOC]

---

Overview

This library implements zkSNARK schemes, which are a cryptographic method for proving/verifying, in zero knowledge, the integrity of computations.

A computation can be expressed as an NP statement, in forms such as the following:

• "The C program foo, when executed, returns exit code 0 if given the input bar and some additional input qux."
• "The Boolean circuit foo is satisfiable by some input qux."
• "The arithmetic circuit foo accepts the partial assignment bar, when extended into some full assignment qux."
• "The set of constraints foo is satisfiable by the partial assignment bar, when extended into some full assignment qux."

A prover who knows the witness for the NP statement (i.e., a satisfying input/assignment) can produce a short proof attesting to the truth of the NP statement. This proof can be verified by anyone, and offers the following properties.

• Zero knowledge: the verifier learns nothing from the proof beside the truth of the statement (i.e., the value qux, in the above examples, remains secret).
• Succinctness: the proof is short and easy to verify.
• Non-interactivity: the proof is a string (i.e. it does not require back-and-forth interaction between the prover and the verifier).
• Soundness: the proof is computationally sound (i.e., it is infeasible to fake a proof of a false NP statement). Such a proof system is also called an argument.
• Proof of knowledge: the proof attests not just that the NP statement is true, but also that the prover knows why (e.g., knows a valid qux).

These properties are summarized by the zkSNARK acronym, which stands for Zero-Knowledge Succinct Non-interactive ARgument of Knowledge (though zkSNARKs are also known as succinct non-interactive computationally-sound zero-knowledge proofs of knowledge). For formal definitions and theoretical discussions about these, see [BCCT12], [BCIOP13], and the references therein.

The libsnark library currently provides a C++ implementation of:

1. General-purpose proof systems:

   1. A preprocessing zkSNARK for the NP-complete language "R1CS" (Rank-1 Constraint Systems), which is a language that is similar to arithmetic circuit satisfiability.

      This zkSNARK construction follows, extends, and optimizes the approach described in [BCTV14a], itself an extension of [BCGTV13], following the approach of [GGPR13] and [BCIOP13]. (An alternative implementation of this approach is the Pinocchio system of [PGHR13].)

      The library also implements a zk-SNARK for R1CS secure in the generic group model [Groth16]. Compared to [BCTV14a] the [Groth16] proof system is faster and achieves shorter proofs, at expense of making stronger security assumptions.

      We provide detailed empirical and asymptotic comparison between these choices.

   2. A preprocessing SNARK for a language of arithmetic circuits, "BACS" (Bilinear Arithmetic Circuit Satisfiability). This simplifies the writing of NP statements when the additional flexibility of R1CS is not needed. Internally, it reduces to R1CS.

   3. A preprocessing SNARK for the language "USCS" (Unitary-Square Constraint Systems). This abstracts and implements the core contribution of [DFGK14]

   4. A preprocessing SNARK for a language of Boolean circuits, "TBCS" (Two-input Boolean Circuit Satisfiability). Internally, it reduces to USCS. This is much more efficient than going through R1CS.

   5. A simulation-extractable preprocessing SNARK for R1CS. This construction uses the approach described in [GM17]. For arithmetic circuits, it is slower than the [BCTV14a] approach, but produces shorter proofs.

   6. ADSNARK, a preprocessing SNARKs for proving statements on authenticated data, as described in [BBFR15].

   7. Proof-Carrying Data (PCD). This uses recursive composition of SNARKs, as explained in [BCCT13] and optimized in [BCTV14b].

2. Gadget libraries (gadgetlib1 and gadgetlib2) for constructing R1CS instances out of modular "gadget" classes.
3. Examples of applications that use the above proof systems to prove statements about:
   1. Several toy examples.
   2. Execution of TinyRAM machine code, as explained in [BCTV14a] and [BCGTV13]. (Such machine code can be obtained, e.g., by compiling from C.) This is easily adapted to any other Random Access Machine that satisfies a simple load-store interface.
   3. A scalable for TinyRAM using Proof-Carrying Data, as explained in [BCTV14b]
   4. Zero-knowledge cluster MapReduce, as explained in [CTV15].

See the above references for discussions of efficiency aspects that arise in practical use of such constructions, as well as security and trust considerations.

This scheme is a preprocessing zkSNARK (ppzkSNARK): before proofs can be created and verified, one needs to first decide on a size/circuit/system representing the NP statements to be proved, and run a generator algorithm to create corresponding public parameters (a long proving key and a short verification key).

Using the library involves the following high-level steps:

1. Express the statements to be proved as an R1CS (or any of the other languages above, such as arithmetic circuits, Boolean circuits, or TinyRAM). This is done by writing C++ code that constructs an R1CS, and linking this code together with libsnark
2. Use libsnark's generator algorithm to create the public parameters for this statement (once and for all).
3. Use libsnark's prover algorithm to create proofs of true statements about the satisfiability of the R1CS.
4. Use libsnark's verifier algorithm to check proofs for alleged statements.

---

The NP-complete language R1CS

The ppzkSNARK supports proving/verifying membership in a specific NP-complete language: R1CS (rank-1 constraint systems). An instance of the language is specified by a set of equations over a prime field F, and each equation looks like: < A, (1,X) > * < B , (1,X) > = < C, (1,X) > where A,B,C are vectors over F, and X is a vector of variables.

In particular, arithmetic (as well as boolean) circuits are easily reducible to this language by converting each gate into a rank-1 constraint. See [BCGTV13] Appendix E (and "System of Rank 1 Quadratic Equations") for more details about this.

---

Elliptic curve choices

The ppzkSNARK can be instantiated with different parameter choices, depending on which elliptic curve is used. The libff library currently provides three options:

• "edwards": an instantiation based on an Edwards curve, providing 80 bits of security.

• "bn128": an instantiation based on a Barreto-Naehrig curve, providing 128 bits of security. The underlying curve implementation is [ate-pairing], which has incorporated our patch that changes the BN curve to one suitable for SNARK applications.

  • This implementation uses dynamically-generated machine code for the curve arithmetic. Some modern systems disallow execution of code on the heap, and will thus block this implementation.

    For example, on Fedora 20 at its default settings, you will get the error zmInit ERR:can't protect when running this code. To solve this, run sudo setsebool -P allow_execheap 1 to allow execution, or use cmake -DCURVE=ALT_BN128 instead.

• "alt_bn128": an alternative to "bn128", somewhat slower but avoids dynamic code generation.

Note that bn128 requires an x86-64 CPU while the other curve choices should be architecture-independent; see portability.

---

Gadget libraries

The libsnark library currently provides two libraries for conveniently constructing R1CS instances out of reusable "gadgets". Both libraries provide a way to construct gadgets on other gadgets as well as additional explicit equations. In this way, complex R1CS instances can be built bottom up.

gadgetlib1

This is a low-level library which expose all features of the preprocessing zkSNARK for R1CS. Its design is based on templates (as does the ppzkSNARK code) to efficiently support working on multiple elliptic curves simultaneously. This library is used for most of the constraint-building in libsnark, both internal (reductions and Proof-Carrying Data) and examples applications.

gadgetlib2

This is an alternative library for constructing systems of polynomial equations and, in particular, also R1CS instances. It is better documented and easier to use than gadgetlib1, and its interface does not use templates. However, fewer useful gadgets are provided.

---

Security

The theoretical security of the underlying mathematical constructions, and the requisite assumptions, are analyzed in detailed in the aforementioned research papers.

** This code is a research-quality proof of concept, and has not yet undergone extensive review or testing. It is thus not suitable, as is, for use in critical or production systems. **

Known issues include the following:

• The ppzkSNARK's generator and prover exhibit data-dependent running times and memory usage. These form timing and cache-contention side channels, which may be an issue in some applications.

• Randomness is retrieved from /dev/urandom, but this should be changed to a carefully considered (depending on system and threat model) external, high-quality randomness source when creating long-term proving/verification keys.

---

Build instructions

Dependencies

The libsnark library relies on the following:

• C++ build environment
• CMake build infrastructure
• GMP for certain bit-integer arithmetic
• libprocps for reporting memory usage
• Fetched and compiled via Git submodules:
  • libff for finite fields and elliptic curves
  • libfqfft for fast polynomial evaluation and interpolation in various finite domains
  • Google Test (G