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.
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.
- 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.
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.
In order to compile on macOS please use this thread: elibensasson#2
- OpenMP (https://en.wikipedia.org/wiki/OpenMP) for parallelization.
- googletest (https://github.com/google/googletest) for unit-tests compilation only
git clone https://github.com/elibensasson/libSTARK.git
cd libSTARK
make -j8
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.
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 210-1) machine steps, and soundness error at most 2-120.
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.
Compilation:
make -j8 tests
Execution:
./bin/algebralib-tests/algebralib_tests
./bin/libstark-tests/libstark-tests
./bin/stark-tinyram-tests/stark-tinyram-tests
- Scalable perfect zero knowledge IOP systems [BCGV, BCFGRS].
- A STARK without ZK [SCI].
- Survey of alternative (non-STARK) proof systems [WB].
- Interactive Oracle Proofs [BCS, RRR].
- PCPs with scalable (quasi-linear) proof size [BS, D].
- ZK-PCPs [K, KPT, IMS].
- Probabilistically checkable proofs (PCPs) [AS, ALMSS] and PCPs of Proximity (PCPPs) [BGHSV, DR].
- Scalable (poly-logarithmic) verification of computations [BFLS, BGHSV].
- Interactive and ZK proof systems [BM, GMR, BFL].