Incrementally Verifiable Computation for NP from Standard Assumptions

Incrementally verifiable computation (IVC) [Valiant, TCC'08] allows one to iteratively prove that a configuration $x_0$ reaches another configuration $x_T$ after repeated applications of a (possibly non-deterministic) transition function $\mathcal{M}$. The key requirement is that the size of the proof and the time to update the proof is sublinear in the number of steps $T$. IVC has numerous applications, notably including proving correctness of virtual machine executions in blockchains.

Currently, IVC for $\mathsf{NP}$ is only known to exist in non-standard idealized models, or based on knowledge assumptions. No constructions are known from standard assumptions, or even in the random oracle model. Furthermore, as observed in prior works, since IVC for $\mathsf{NP}$ implies adaptive succinct non-interactive arguments for $\mathsf{NP}$, the work of Gentry-Wichs [STOC'11] seemingly poses barriers to constructing IVC for $\mathsf{NP}$ from falsifiable assumptions.

In this work, we observe that the Gentry-Wichs barrier can be overcome for IVC for NP. We show the following two results:

• Assuming subexponential $i\mathcal{O}$ and LWE (or bilinear maps), we construct IVC for all $\mathsf{NP}$ with proof size $\mathsf{poly}(|x_i|,\log T)$.

• Assuming subexponential $i\mathcal{O}$ and injective PRGs, we construct IVC for trapdoor IVC languages where the proof-size is $\mathsf{poly}(\log T)$. Informally, an IVC language has a trapdoor if there exists a (not necessarily easy to find) polynomial-sized circuit that determines if a configuration $x_i$ is reachable from $x_0$ in $i$ steps.