Interactive oracle proof

An interactive oracle proof (IOP) is a public-coin interactive proof in which the verifier reads only a few symbols of each prover message — BCS16.

Definition

A $k$-round public-coin interactive oracle proof for a relation $\mathcal{R}$ is a protocol between a prover $P(x,w)$ and a verifier $V(x)$ in which, in each round $i\in [k]$, $P$ sends an oracle ${\Pi }_i\in {\Sigma }^{{\ell }_i}$ and $V$ answers with uniformly random ${\rho }_i$. After the last round $V$, from $x$ and ${\rho }_1,\dots ,{\rho }_k$, queries $q$ positions of ${\Pi }_1,\dots ,{\Pi }_k$ and accepts or rejects.

• Completeness: for every $(x,w)\in \mathcal{R}$, the honest prover makes $V$ accept with probability $1$.
• Soundness error $\epsilon$: for every $x\notin L(\mathcal{R})$ and every prover $\tilde{P}$, $V$ accepts with probability at most $\epsilon$.

A PCP is a one-round IOP, and an interactive proof is an IOP whose verifier reads every oracle — BCS16. RRR16 independently define the same notion as probabilistically checkable interactive proofs.

Succinct IOPs with state-restoration knowledge soundness

Let ${\mathcal{R}}_U=\{((M,x,T),w):M\text{ accepts }(x,w)\text{ within }T\text{ steps}\}$ be the universal relation. A public-coin IOP for ${\mathcal{R}}_U$, parameterized by $\lambda$, is succinct with state-restoration knowledge soundness if

• the honest prover, given $w$, runs in time $\mathrm{poly}(\lambda ,|M|,|x|,T)$;
• the verifier runs in time $\mathrm{poly}(\lambda ,|M|,|x|,\log T)$, which bounds the number of rounds, the number of queries and the size of each queried symbol;
• there is a polynomial-time extractor $\mathcal{E}$ such that for every polynomial $t$ and every prover $\tilde{P}$ that may, up to $t$ times, return the verifier to an earlier state before completing one transcript, the verifier then drawing fresh randomness for the next round: if $\tilde{P}$ makes $V$ accept $(M,x,T)$ with probability $\delta$, then ${\mathcal{E}}^{\tilde{P}}(M,x,T)$ outputs $w$ with $((M,x,T),w)\in {\mathcal{R}}_U$ with probability at least $\delta -{\kappa }_{\mathrm{sr}}(t)$, where ${\kappa }_{\mathrm{sr}}(t)$ is negligible in $\lambda$ — BCS16.

A state restoration rewinds the verifier, not the prover: $\tilde{P}$ chooses which partial transcript to continue from and which complete transcript to submit. Such a prover is what a cheating prover against the compiled non-interactive argument becomes, which is why this notion, rather than ordinary soundness, governs the BCS transform — BCS16.

Participates in

Builds on Interactive oracle proof

• Succinct state-restoration-sound IOP ⇒ STARK (BCS transform) (via Succinct IOPs with state-restoration knowledge soundness)