Paper 2012/622

Resolving the conflict between generality and plausibility in verified computation

Srinath Setty, Benjamin Braun, Victor Vu, Andrew J. Blumberg, Bryan Parno, and Michael Walfish


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. A 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 most computations. Our protocol 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 \emph{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 GPU implementation. The result, as indicated by an experimental evaluation, is a system that is {\em almost} usable for real problems---without special-purpose tailoring.

Note: Update proofs, experimental results, and exposition.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. This is the full version of a paper at Eurosys 2013.
Contact author(s)
mwalfish @ cs utexas edu
2013-03-12: revised
2012-11-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Srinath Setty and Benjamin Braun and Victor Vu and Andrew J.  Blumberg and Bryan Parno and Michael Walfish},
      title = {Resolving the conflict between generality and plausibility in verified computation},
      howpublished = {Cryptology ePrint Archive, Paper 2012/622},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.