Resolving the Conflict Between Generality and Plausibility in Verified Computation

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 server is immense: server work is 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 for all computations. We do so via theoretical refinements (of independent interest) to the core protocols, integrated with a built system that includes a compiler and a parallel GPU implementation. The result is a system that is almost usable for real problems—without special-purpose tailoring. We argue that this completes the transformation of the problem of verified computation into a problem in secure systems research.