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 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 NP is only known to exist in non-standard idealized models, or based on knowledge assumptions. No constructions are known from standard assumptions, or \emph{even in the random oracle model}. Furthermore, as observed in prior works, since IVC for NP implies adaptive succinct non-interactive arguments for NP, the work of Gentry-Wichs [STOC'11] seemingly poses barriers to constructing IVC for 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 iO and LWE (or bilinear maps), we construct IVC for all NP with proof size poly(|x_i|, log T).

* Assuming subexponential iO and injective PRGs, we construct IVC for trapdoor IVC languages where the proof-size is 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.