libSTARK: a C++ library for zk-STARK systems

Overview

The libSTARK library implements scalable and transparent argument of knowledge (STARK) systems. These systems can be executed with, or without, zero knowledge (ZK), and may be designed as either interactive or non-interactive protocols. The theoretical constructions which this library implements are described in detail in the zk-STARK paper. Briefly, the main properties of (zk)-STARK systems are:

• universality: the system can be applied to any computation specified by an algebraic intermediate representation (AIR) or by a permuted algebraic intermediate representation (PAIR) as defined in the zkSTARK paper. The former (AIR) is relevant to "memory efficient" computations and the latter (PAIR) for computations that require random access memory (RAM).
• transparency: all messages sent by the verifier, including queries to the proof oracles, are public random coins (i.e., the protocol is "Arthur-Merlin").
• scalability: as an asymptotic function of the number of cycles (T) required by the computation whose integrity is being proved, both of the following conditions hold:
  • prover scalability: prover running time scales quasi-linearly in T, i.e., like T poly log T.
  • verifier scalability: verifier running time scales poly-logarithmically in T, i.e., like poly log T.
• "post-quantum security": the cryptographic primitives that underlie the security of the system are either the existence of a family of collision resistant hash functions (for an interactive system) or common access to a random function (the "random oracle" model for a non-interactive setting); in particular, quantum computers are not known to break system security at time of writing.

Disclaimer

The code is academic grade, meant for academic peer review and evaluation. It very likely contains multiple serious security flaws, and should not be relied upon for any other purpose.

Dependencies

Hardware acceleration

• sse4 (https://en.wikipedia.org/wiki/SSE4)
  • CLMUL (https://en.wikipedia.org/wiki/CLMUL_instruction_set) for basic arithmetics in characteristic 2 fields.
  • SIMD (https://en.wikipedia.org/wiki/SIMD) instructions for FFT acceleration.
• aes (https://en.wikipedia.org/wiki/AES_instruction_set) to accelerate Merkle tree construction and verification.

Compiler

The code was tested with gcc version 7.3.0 (https://gcc.gnu.org), using c++11 standard. But should probably work with most common versions of gcc.

Compilation on macOS

In order to compile on macOS please use this thread: elibensasson#2

Libraries (all should be available in standard Linux distribution package managers)

• OpenMP (https://en.wikipedia.org/wiki/OpenMP) for parallelization.
• googletest (https://github.com/google/googletest) for unit-tests compilation only

How to run the code

Compilation:

git clone https://github.com/elibensasson/libSTARK.git
cd libSTARK
make -j8

STARK for DPM (DNA fingerprint blacklist)

Arguments format:

./stark-dpm <database file path> <fingerprint file path> [-s<security parameter>]

for example:

./stark-dpm examples-dpm/database.txt examples-dpm/fp_no_match.txt

The above execution results in execution of STARK simulation over the DPM blacklist program, with the database represented by examples-dpm/database.txt, the suspect's fingerprint in examples-dpm/fp_nomatch.txt, and soundness error at most 2^-120. The prover generates in this case a proof for the claim that the fingerprint does not perfectly match any entry in the database.

A single fingerprint is represented by a single line, each line contains 20 pairs delimited by spaces, each pair contains two 8 bit numbers in hexadecimal basis, separated by a single period. A database is a file where each line represents a fingerprint.

STARK for TinyRAM programs

Arguments format:

./stark-tinyram <TinyRAM assembly file path> -t<trace length log_2> [-s<security parameter]>

for example:

./stark-tinyram examples-tinyram/collatz.asm -t10 -s120

The above execution results in execution of STARK simulation over the collatz program, using at most 1023 (which is 2¹⁰-1) machine steps, and soundness error at most 2^-120.

Execution results

In the simulation the Prover and Verifier interact, the Prover generates a proof and the Verifier verifies it. During the executions the specifications of generated BAIR and APR, measurements, and Verifier's decision, are printed to the standard output.

Unit-tests

Compilation:

make -j8 tests

Execution:

./bin/algebralib-tests/algebralib_tests
./bin/libstark-tests/libstark-tests
./bin/stark-tinyram-tests/stark-tinyram-tests

Academic literature (partial list, reverse chronological order)

1. Scalable perfect zero knowledge IOP systems [BCGV, BCFGRS].
2. A STARK without ZK [SCI].
3. Survey of alternative (non-STARK) proof systems [WB].
4. Interactive Oracle Proofs [BCS, RRR].
5. PCPs with scalable (quasi-linear) proof size [BS, D].
6. ZK-PCPs [K, KPT, IMS].
7. Probabilistically checkable proofs (PCPs) [AS, ALMSS] and PCPs of Proximity (PCPPs) [BGHSV, DR].
8. Scalable (poly-logarithmic) verification of computations [BFLS, BGHSV].
9. Interactive and ZK proof systems [BM, GMR, BFL].