The area of proof-based verified computation (outsourced computation
built atop probabilistically checkable proofs and cryptographic
machinery) has lately seen renewed interest. Although recent work has
made great strides in reducing the overhead of naive applications of the
theory, these schemes still cannot be considered practical. The core
issue is that the work for the prover is immense, in general; it
is near-practical only for hand-compiled computations that can
be expressed in special forms.
This paper addresses that problem. Provided one is willing to batch
verification, we develop a protocol that
achieves the efficiency of the
best manually constructed protocols in the literature yet applies to all
is built on the observation that the
recently-proposed QAPs of Gennaro et al. (ePrint 2012/215) yield a
linear PCP that works with the efficient argument protocol of Setty et
al. (ePrint 2012/598, Security 2012, NDSS 2012), itself based on the
proposal of Ishai et al. (CCC 2007).
The consequence is a prover whose total work is not much more than
_linear_ in the running time of the computation.
We implement the protocol in the
context of a built system that includes a compiler and a parallel GPU
implementation. The result, as indicated by an experimental evaluation,
is a system that is _almost_ usable for real problems -- without