Succinct state-restoration-sound IOP ⇒ STARK (BCS transform)

Fully-black-box reduction · random oracle model · via Fiat–Shamir · BCS16 · security loss: additive: ${\kappa }_{\mathrm{sr}}(t)$ plus $O(t^2{2}^{-\lambda })$ for a $t$-query prover and $\lambda$-bit oracle outputs, the probability of a collision among the oracle’s answers

Statement

Let $(P,V)$ be a public-coin $k$-round succinct interactive oracle proof with state-restoration knowledge soundness for the universal relation ${\mathcal{R}}_U=\{((M,x,T),w):M\text{ accepts }(x,w)\text{ within }T\text{ steps}\}$, with $q$ queries into prover oracles of length $\ell$ and state-restoration knowledge error ${\kappa }_{\mathrm{sr}}(t)$ against provers performing $t$ state restorations. The BCS transform — Merkle-commit each prover oracle with the random oracle $H$, derive the verifier’s randomness in each round by hashing that round’s root together with the statement in the first round and with the previous round’s randomness afterwards, and send the roots with the $q$ queried symbols and their authentication paths — is a transparent succinct non-interactive argument of knowledge for ${\mathcal{R}}_U$ in the random-oracle model, with no setup beyond the oracle. Its soundness is tightly characterized by the IOP’s state-restoration soundness: against provers making $t$ oracle queries, its knowledge error is ${\kappa }_{\mathrm{sr}}(t)$ plus the probability of a collision among the oracle’s answers — BCS16. The transform preserves the IOP’s honest-verifier zero knowledge, and applied to known IOPs it gives unconditional zero-knowledge proofs in the random-oracle model with quasilinear prover and polylogarithmic verifier — BCS16. BCS16 also prove tight upper and lower bounds on state-restoration soundness in terms of the IOP’s soundness and round complexity, and present the compiler as a generalization of Fiat–Shamir for public-coin interactive proofs and of Micali’s CS proofs for PCPs — BCS16.

Sketch

The prover Merkle-commits to each oracle ${\Pi }_i$ with $H$, sets ${\rho }_1:=H(M,x,T,{\mathrm{root}}_1)$ and ${\rho }_{i+1}:=H({\mathrm{root}}_{i+1},{\rho }_i)$, and outputs the roots, the queried symbols and their authentication paths; the verifier recomputes the ${\rho }_i$, checks the paths, and runs $V$ on the answers. A cheating prover’s oracle queries determine the oracles it committed to, and each query of $H$ on a fresh root is a state restoration of the IOP verifier — BCS16.

Notes

• The proof consists of $k$ Merkle roots and $q$ symbols with $q$ authentication paths of $\log \ell$ hashes each, $k\lambda +q(\log |\Sigma |+\lambda \log \ell )$ bits for $\lambda$-bit hashes and alphabet $\Sigma$; the prover runs the IOP prover and $O(\ell )$ hashes, and the verifier runs the IOP verifier and $O(q\log \ell )$ hashes — standard.
• The one-round case, a PCP, is Micali’s construction: ROM ⇒ SNARK (CS proofs) — Mic00.
• The transform of an IOP with round-by-round soundness is sound in the quantum random-oracle model — CMS19.
• For a $(2\mu +1)$-move public-coin protocol and $Q$ oracle queries, the generic soundness loss of Fiat–Shamir is approximately $Q^{\mu }$, which the $\mu$-fold sequential repetition of a $\Sigma$-protocol attains — AFK22.