Home

Awesome

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]

<!--- NOTE: the file you are reading is in Markdown format, which is is fairly readable directly, but can be converted into an HTML file with much nicer formatting. To do so, run "make doc" (this requires the python-markdown package) and view the resulting file README.html. Alternatively, view the latest HTML version at https://github.com/scipr-lab/libsnark . -->

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:

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.

These properties are summarized by the zkSNARK acronym, which stands for Zero-Knowledge Succinct Non-interactive ARgument of Knowledge (though zkSNARKs are also knows 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].)

    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-knowldge 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:

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:


Build instructions

Dependencies

The libsnark library relies on the following:

So far we have tested these only on Linux, though we have been able to make the libsnark work, with some features disabled (such as memory profiling or GTest tests), on Windows via Cygwin and on Mac OS X. See also the notes on portability below. (If you port libsnark to additional platforms, please let us know!)

Concretely, here are the requisite packages in some Linux distributions:

Building

Fetch dependencies from their GitHub repos:

$ git submodule init && git submodule update

Create the Makefile:

$ mkdir build && cd build && cmake ..

Then, to compile the library, tests, and profiling harness, run this within the build directory:

$ make

To create the HTML documentation, run

$ make doc

and then view the resulting README.html (which contains the very text you are reading now).

To compile and run the tests for this library, run:

$ make check

Using libsnark as a library

To develop an application that uses libsnark, it's recommended to use your own build system that incorporates libsnark and dependencies. If you're using CMake, add libsnark as a git submodule, and then add it as a subdirectory. Then, add snark as a library dependency to the appropriate rules.

To build and install the libsnark library:

$ DESTDIR=/install/path make install

This will install libsnark.a into /install/path/lib; so your application should be linked using -L/install/path/lib -lsnark. It also installs the requisite headers into /install/path/include; so your application should be compiled using -I/install/path/include.

In addition, unless you use WITH_SUPERCOP=OFF, libsnark_adsnark.a will be installed and should be linked in using -lsnark_adsnark.

When you use compile your application against libsnark, you must have the same conditional defines (#define FOO or g++ -DFOO) as when you compiled libsnark, due to the use of templates. One way to figure out the correct conditional defines is to look at build/libsnark/CMakeFiles/snark.dir/flags.make after running cmake. (Issue #21)

Building on Windows using Cygwin

Install Cygwin using the graphical installer, including the g++, libgmp, cmake, and git packages. Then disable the dependencies not easily supported under CygWin, using:

$ cmake -DWITH_PROCPS=OFF ..

Building on Mac OS X

On Mac OS X, install GMP from MacPorts (port install gmp). Then disable the dependencies not easily supported under OS X, using:

$ cmake -DWITH_PROCPS=OFF ..

MacPorts does not write its libraries into standard system folders, so you might need to explicitly provide the paths to the header files and libraries by appending CXXFLAGS=-I/opt/local/include LDFLAGS=-L/opt/local/lib to the line above.


Build options

The following flags change the behavior of the compiled code. Use

 $ cmake -Dname1=ON -Dname2=OFF ...

to control these (you can see the default at the top of CMakeLists.txt).

Use architecture-specific assembly routines for F[p] arithmetic and heap in
multi-exponentiation. (If disabled, use GMP's `mpn_*` routines instead.)

Not all combinations are tested together or supported by every part of the codebase.


Docker

You can run libsnark on Docker:

$ docker build -t libsnark .
$ docker run -ti libsnark /bin/bash

Tutorials

libsnark includes a tutorial, and some usage examples, for the high-level API.


Executing profiling example

The command

 $ libsnark/zk_proof_systems/ppzksnark/r1cs_ppzksnark/profiling/profile_r1cs_ppzksnark 1000 10 Fr

exercises the ppzkSNARK (first generator, then prover, then verifier) on an R1CS instance with 1000 equations and an input consisting of 10 field elements.

(If you get the error zmInit ERR:can't protect, see the discussion above.)

The command

 $ libsnark/zk_proof_systems/ppzksnark/r1cs_ppzksnark/profiling/profile_r1cs_ppzksnark 1000 10 bytes

does the same but now the input consists of 10 bytes.


Portability

libsnark is written in fairly standard C++11.

However, having been developed on Linux on x86-64 CPUs, libsnark has some limitations with respect to portability. Specifically:

  1. libsnark's algebraic data structures assume little-endian byte order.

  2. Profiling routines use clock_gettime and readproc calls, which are Linux-specific.

  3. Random-number generation is done by reading from /dev/urandom, which is specific to Unix-like systems.

  4. libsnark binary serialization routines (see BINARY_OUTPUT above) assume a fixed machine word size (i.e. sizeof(mp_limb_t) for GMP's limb data type). Objects serialized in binary on a 64-bit system cannot be de-serialized on a 32-bit system, and vice versa. (The decimal serialization routines have no such limitation.)

  5. libsnark requires a C++ compiler with good C++11 support. It has been tested with g++ 4.7 and newer, and clang 3.4 and newer.

  6. On x86-64, we by default use highly optimized assembly implementations for some operations (see USE_ASM above). On other architectures we fall back to a portable C++ implementation, which is slower.

  7. The ate-pairing library, require by the BN128 curve, can be compiled only on i686 and x86-64. (On other platforms, use other -DCURVE=... choices.)

  8. The SUPERCOP library, required by ADSNARK, can be compiled only on i686 and x86-64. (On other platforms, use -DWITH_SUPERCOP=OFF.)

Tested configurations include:


Directory structure

The directory structure of the libsnark library is as follows:

Some of these module directories have the following subdirectories:

In particular, the top-level API examples are at libsnark/r1cs_ppzksnark/examples/ and libsnark/gadgetlib2/examples/.


Further considerations

Multiexponentiation window size

The ppzkSNARK's generator has to solve a fixed-base multi-exponentiation problem. We use a window-based method in which the optimal window size depends on the size of the multiexponentiation instance and the platform.

On our benchmarking platform (a 3.40 GHz Intel Core i7-4770 CPU), we have computed for each curve optimal windows, provided as fixed_base_exp_window_table initialization sequences, for each curve; see X_init.cpp for X=edwards,bn128,alt_bn128.

Performance on other platforms may not be optimal (but probably not be far off). Future releases of the libsnark library will include a tool that generates optimal window sizes.


References

[BBFR15] ADSNARK: nearly practical and privacy-preserving proofs on authenticated data , Michael Backes, Manuel Barbosa, Dario Fiore, Raphael M. Reischuk, IEEE Symposium on Security and Privacy (Oakland) 2015

[BCCT12] From extractable collision resistance to succinct non-Interactive arguments of knowledge, and back again , Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer, Innovations in Computer Science (ITCS) 2012

[BCCT13] Recursive composition and bootstrapping for SNARKs and proof-carrying data Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer, Symposium on Theory of Computing (STOC) 13

[BCGTV13] SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge , Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, Madars Virza, CRYPTO 2013

[BCIOP13] Succinct non-interactive arguments via linear interactive Proofs , Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, Omer Paneth, Theory of Cryptography Conference 2013

[BCTV14a] Succinct non-interactive zero knowledge for a von Neumann architecture , Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza, USENIX Security 2014

[BCTV14b] Scalable succinct non-interactive arguments via cycles of elliptic curves , Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza, CRYPTO 2014

[CTV15] Cluster computing in zero knowledge , Alessandro Chiesa, Eran Tromer, Madars Virza, Eurocrypt 2015

[DFGK14] Square span programs with applications to succinct NIZK arguments , George Danezis, Cedric Fournet, Jens Groth, Markulf Kohlweiss, ASIACCS 2014

[GM17] Snarky Signatures: Minimal Signatures of Knowledge from Simulation-Extractable SNARKs , Jens Groth and Mary Maller, IACR-CRYPTO-2017

[GGPR13] Quadratic span programs and succinct NIZKs without PCPs , Rosario Gennaro, Craig Gentry, Bryan Parno, Mariana Raykova, EUROCRYPT 2013

[ate-pairing] High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves , MITSUNARI Shigeo, TERUYA Tadanori

[PGHR13] Pinocchio: Nearly Practical Verifiable Computation , Bryan Parno, Craig Gentry, Jon Howell, Mariana Raykova, IEEE Symposium on Security and Privacy (Oakland) 2013