CRHF ⇒ STARK

Random oracle model · BBHR18a · security loss: additive: the IOP’s state-restoration soundness error for $t$ oracle queries plus $O(t^2{2}^{-\lambda })$ for $\lambda$-bit oracle outputs

Statement

A collision-resistant hash function, used for Merkle commitments and modeled as a random oracle for non-interactivity, yields STARKs: transparent (no trusted setup) succinct non-interactive arguments of knowledge with quasilinear prover time and $O({\log }^{2}T)$ proof size for a $T$-step computation — BBHR18a.

Sketch

The computation is expressed as an AIR; the prover Merkle-commits to Reed–Solomon codewords of the execution-trace polynomials, and the AIR constraints reduce to a low-degree proximity claim about a derived codeword, which FRI certifies in logarithmically many degree-halving rounds. The BCS transform compiles the resulting IOP, given its state-restoration soundness, into a non-interactive argument of knowledge in the random-oracle model — BCS16.

Notes

• Only the interactive variant, before the BCS transform, reduces to collision resistance in the standard model — BBHR18a; instantiating the random oracle with a concrete hash function is heuristic — standard.
• Post-quantum soundness of the non-interactive argument needs a quantum-random-oracle analysis: the BCS transform of a round-by-round sound IOP is sound in the quantum random-oracle model — CMS19.
• The verifier runs in time $\mathrm{polylog}(T)$ for a fixed program — BBHR18a.