Starks

STARKs, or Scalable Transparent ARguments of Knowledge, are a class of zero-knowledge proofs designed for scalable, transparent verification of computations. They provide short proofs that a computation was performed correctly without exposing inputs and without a trusted setup. STARKs are post-quantum secure, relying on hash-based commitments and algebraic techniques rather than discrete-log or factoring assumptions. The transparency aspect means there is no parameter-generation ceremony required.

A STARK proof encodes a computation as a set of algebraic constraints over polynomials. The execution trace is extended to a low-degree polynomial, forming a low-degree extension. The prover commits to these polynomials and uses proximity tests, such as the Fast Reed-Solomon Proximity Proofs (FRI), to convince the verifier that the polynomials are low-degree without revealing the witness. Non-interactive proofs are obtained via the Fiat-Shamir transform, yielding a publicly verifiable, succinct proof. Verification runs in time that is polylogarithmic in the size of the computation, and the proof size grows modestly with complexity.

Applications include publicly verifiable computations in blockchains and other protocols. STARKs are used in scalable rollups and related systems as an alternative to SNARKs, offering transparency and quantum resistance at the cost of larger proof sizes relative to some SNARKs. Ongoing research aims to improve efficiency and reduce proof sizes further while maintaining transparency and post-quantum security.

See also SNARKs, zero-knowledge proofs, and zk-STARKs.