DOCSEARCHbyAlgolia
Submit Docs

libsnark Documentation

repository·master·Indexed 24 days ago

https://github.com/scipr-lab/libsnark

A high-performance C++ library for implementing zkSNARK (Zero-Knowledge Succinct Non-interactive ARgument of Knowledge) proof systems. It allows developers to express NP statements as constraints and generate efficient proofs using systems such as Groth16, PGHR13/BCTV14a, and GM17. The library supports various constraint systems including R1CS, BACS, USCS, TBCS, and ADSNARK, and provides tools for TinyRAM assembly program preprocessing and execution.

Tokens
3.2K
Snippets
0
Records
15
Agent score
83%

What's inside libsnark

  1. Overview of libsnark zkSNARK implementations

    master

    libsnark is a C++ library for implementing zkSNARK (Zero-Knowledge Succinct Non-interactive ARgument of Knowledge) schemes. It allows a prover to attest to the truth of an NP statement (like the satisfiability of a circuit or the execution of a program) without revealing the underlying witness.

    Key proof systems provided include:

    • R1CS (Rank-1 Constraint Systems): A general-purpose preprocessing zkSNARK for NP-complete statements. It includes implementations following [BCTV14a] and the faster, shorter [Groth16] system.
    • BACS (Bilinear Arithmetic Circuit Satisfiability): A preprocessing SNARK for arithmetic circuits that reduces to R1CS.
    • USCS (Unitary-Square Constraint Systems): An abstraction of the core contribution of [DFGK14].
    • TBCS (Two-input Boolean Circuit Satisfiability): A preprocessing SNARK for Boolean circuits that reduces to USCS.
    • Simulation-extractable R1CS: A construction using the approach from [GM17].
    • ADSNARK: A preprocessing SNARK for proving statements on authenticated data.
    • Proof-Carrying Data (PCD): Uses recursive composition of SNARKs.

  2. Compare gadgetlib1 and gadgetlib2

    master

    libsnark provides two libraries for constructing R1CS instances from reusable "gadgets":

    • gadgetlib1: A low-level, template-based library. It is highly efficient and supports working on multiple elliptic curves simultaneously. It is used for most internal constraint-building and in many examples.
    • gadgetlib2: A higher-level library that is easier to use and better documented. It does not use templates, making the interface simpler, but it provides fewer available gadgets than gadgetlib1.

  3. Understand libsnark's modular dependency structure

    master

    Core algebraic components have been factored out of the monolithic libsnark into two separate libraries, which are managed as Git submodules in the depends directory (formerly third-party):

    • libff: Handles finite fields and elliptic curves.
    • libfqfft: Handles fast polynomial evaluation and interpolation in various finite domains.

    Submodule Management: To prevent library duplication or versioning conflicts, libsnark fetches only top-level submodules and does not perform recursive submodule fetching. This ensures that CMake compiles dependencies as native code to libsnark and prevents hidden shared-library dependency issues. If you are modifying submodules, be aware that CMake scripts include optional flags to pass state from the parent to the dependency to prevent unnecessary recompilation.

  4. Understand asymptotic complexity of libsnark zkSNARKs

    master

    To predict how a proof system will scale with larger circuits, use the following asymptotic notation where:

    • $M$ = number of constraints in R1CS instance
    • $N$ = number of variables in R1CS instance
    • $n$ = number of inputs in R1CS instance

    Asymptotic Complexity Table

    Proof systemFFTs (count)FFTs (domain size)Exponentiations (Gen/Prover)PK (#G1 / #G2)VK (#G1 / #G2)
    PGHR13/BCTV14a7$M+n+1$$6N+M+n$ / $N$$6N+M+n$ / $N$$n$ / $O(1)$
    Groth167$M+n+1$$3N+M$ / $N$$3N+M$ / $N$$n$ / $O(1)$
    GM175$2M+2n+1$$3N+5M+4n$ / $(N+M+n)$$3N+5M+4n$ / $(N+M+n)$$n$ / $O(1)$

  5. Choose an elliptic curve for ppzkSNARK

    master

    The choice of elliptic curve affects security and performance. The libff library provides three main options:

    • edwards: Based on an Edwards curve, providing 80 bits of security. Architecture-independent.
    • bn128: Based on a Barreto-Naehrig curve, providing 128 bits of security. Requires an x86-64 CPU. This implementation uses dynamic machine code generation, which may be blocked by some systems (e.g., Fedora with strict security settings). If blocked, use alt_bn128 or run sudo setsebool -P allow_execheap 1 on Fedora.
    • alt_bn128: An alternative to bn128 that avoids dynamic code generation. It is slightly slower but more portable.

    To set the curve during build, use: -DCURVE=ALT_BN128 (or other choices).

  6. Compare knapsack vs knapsack-indirect assembly programs

    master

    The TinyRAM examples include two versions of the 0/1 knapsack problem, which demonstrate how different memory access patterns affect SNARK circuit size.

    knapsack.s (Uniform Access)

    • Auxiliary Input: A bit vector of size k (where k is the number of integers in the knapsack instance). Each bit b_i indicates if integer a_i is included.
    • Complexity: Runs in time O(k).
    • Use Case: Best when the solution is not sparse.

    knapsack-indirect.s (Indirect Access)

    • Auxiliary Input: An array of indices idx_1, ..., idx_l representing the elements to include.
    • Complexity: Runs in time O(l).
    • Performance: Uses a routing-network-based capability to perform arbitrary memory accesses. This results in a O(l log l)-size circuit for the underlying SNARK, whereas a linear-sweep approach would require O(k * l).
    • Use Case: Highly efficient for sparse solutions (where l is much smaller than k).

  7. Install and build libsnark from source

    master

    To build libsnark on Linux, follow these steps:

    1. Install Dependencies: For Debian/Ubuntu (18.04/20.04):

      sudo apt install build-essential cmake git libgmp3-dev libprocps-dev python3-markdown libboost-program-options-dev libssl-dev python3 pkg-config

    2. Fetch Submodules:

      git submodule init && git submodule update

    3. Build:

      mkdir build && cd build
cmake ..
make

    4. Run Tests:

      make check

    Note for Windows (Cygwin): Install g++, libgmp, cmake, and git via the Cygwin installer, and use cmake -DWITH_PROCPS=OFF .. to disable unsupported dependencies.

  8. Prepare TinyRAM assembly programs with process_assembly

    master

    Before running TinyRAM demonstrations, you must preprocess your assembly files using the process_assembly Python script. This script resolves labels and parses the header line to generate the necessary files for the libsnark C++ backend.

    Input: A .s assembly file.

    Outputs:

    • program-processed_assembly.txt: An internal representation of the TinyRAM assembly used by libsnark.
    • program-architecture_params.txt: A text file containing two space-separated integers: w (word size) and k (register count), which defines the TinyRAM machine configuration.

  9. Build libsnark using CMake

    master

    The build process for libsnark has transitioned from shell scripts and Makefiles to CMake. To build the project, use cmake to configure the build directory and then run make.

    Note that the new build system uses different flag notation compared to the legacy Makefile-based system. For example, instead of passing variables directly to make, you must pass them as definitions to cmake using the -D prefix.

  10. How to use libsnark in a C++ application

    master

    Using libsnark involves a four-step high-level workflow:

    1. Express the statement: Write C++ code to construct an R1CS (or another supported language like arithmetic/Boolean circuits) and link it with libsnark.
    2. Generate public parameters: Use libsnark's generator algorithm to create a proving key and a verification key (done once per circuit).
    3. Generate proofs: Use the prover algorithm to create proofs for true statements.
    4. Verify proofs: Use the verifier algorithm to check the validity of the proofs.

    When developing your own application, it is recommended to use your own build system (e.g., CMake) and include libsnark as a git submodule. If using CMake, add libsnark as a subdirectory and link against the snark library.

  11. Run TinyRAM demonstrations

    master

    You can execute TinyRAM demonstrations using three different scripts. All scripts assume libsnark executables are located in ../build by default.

    1. Debugging execution traces

    Use ./run_demo_arithmetization <program> to run the "TinyRAM universal circuit reduction" component. This does not run SNARK cryptography. It is fast and outputs a full disassembly of execution traces, making it ideal for debugging assembly logic.

    2. End-to-end Proving and Verifying

    Use ./run_demo_ram_ppzksnark <program> to run the circuit reduction and the SNARK cryptography within a single process. This establishes the full workflow of generating proofs and verifying the correctness of TinyRAM computations.

    3. Testing Serialization

    Use ./run_ram_ppzksnark_gpv <program> to run the generator, prover, and verifier as separate processes. They communicate via files containing serialized proving/verification keys and proofs. This is useful for testing serialization, though it is slower due to serialization overhead.

  12. Configure libsnark build options via CMake

    master

    You can customize the libsnark build using CMake flags (-Dname=VALUE). Common flags include:

    FlagDescription
    -DCURVE=choiceSet default curve: ALT_BN128, BN128, EDWARDS, MNT4, MNT6
    -DLOWMEM=ONLimit multi-exponentiation table size for low-memory platforms
    -DWITH_PROCPS=OFFDisable libprocps (disables memory profiling)
    -DWITH_SUPERCOP=OFFDisable SUPERCOP (disables ADSNARK)
    -DMULTICORE=ONEnable parallelized execution using OpenMP
    -DUSE_ASM=ONUse architecture-specific assembly (default)
    -DBINARY_OUTPUT=ONOutput raw binary data instead of decimal (default)
    -DMONTGOMERY_OUTPUT=ONSerialize Fp elements as Montgomery representations (default)

    To override the maximum number of OpenMP threads at runtime, set the OMP_NUM_THREADS environment variable.