Home > Resources > papers > BBHR18-STARK

Scalable, Transparent, and Post-Quantum Secure Computational Integrity (Ben-Sasson, Bentov, Horesh, Riabzev 2018)

Last modified: 2026-10-27

URL: https://eprint.iacr.org/2018/046

Summary

Introduces zk-STARKs: transparent (no trusted setup), scalable proofs of computational integrity whose prover runs in quasi-linear time and verifier in poly-logarithmic time, relying only on collision-resistant hashing and therefore plausibly post-quantum. Computations are expressed as an Algebraic Intermediate Representation (AIR) and low-degree tested with FRI. Basis of StarkWare's systems and of the wider hash-based proof family considered for long-lived, quantum-resistant credentials.

Used by

• zk-STARKs

Related resources

• Aurora: Transparent Succinct Arguments for R1CS (Ben-Sasson et al. 2019) (paper, 2019)
• Circle STARKs (Haböck, Levit, Papini 2024) (paper, 2024)
• Fast Reed-Solomon Interactive Oracle Proofs of Proximity (FRI) (paper, 2018)
• Poseidon: A New Hash Function for Zero-Knowledge Proof Systems (Grassi, Khovratovich, Rechberger, Roy, Schofnegger 2021) (paper, 2021)