a library for zero knowledge (ZK) scalable transparent argument of knowledge (STAR
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
ledgerwatch 76d5423928
Osx build (#1)
4 years ago
algebra Osx build (#1) 4 years ago
examples-dpm database now ok 5 years ago
examples-tinyram libstark - first version 5 years ago
libstark Osx build (#1) 4 years ago
libstark-tests coefficients for constraints decided at Ali phase 5 years ago
prevstarkdpm confidential-input program of starkdpm 5 years ago
starkdpm Osx build (#1) 4 years ago
tinyram Osx build (#1) 4 years ago
AUTHORS.md wip 5 years ago
LICENSE.md Update LICENSE.md 5 years ago
Makefile added unit-tests, flags.mk for common settings, and reduced compilation requirment from avx to sse4 5 years ago
README.md Cleanup in OS references 5 years ago
collectSubsetsumResults.sh multiple FRI execution for better soundness. 5 years ago
customCode.sln added win vs17 proj 5 years ago
flags.mk Osx build (#1) 4 years ago
runSubsetsumTests.sh multiple FRI execution for better soundness. 5 years ago


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


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.


Hardware acceleration


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: https://github.com/elibensasson/libSTARK/issues/2

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

How to run the code


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 210-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.



make -j8 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].