Paper 2013/356

Verifying Computations with State (Extended Version)

Benjamin Braun, Ariel J. Feldman, Zuocheng Ren, Srinath Setty, Andrew J. Blumberg, and Michael Walfish


When a client outsources a job to a third party (e.g., the cloud), how can the client check the result, without reexecuting the computation? Recent work in _proof-based verifiable computation_ has made significant progress on this problem by incorporating deep results from complexity theory and cryptography into built systems. However, these systems work within a stateless model: they exclude computations that interact with RAM or a disk, or for which the client does not have the full input. This paper describes Pantry, a built system that overcomes these limitations. Pantry composes proof-based verifiable computation with untrusted storage: the client expresses its computation in terms of digests that attest to state, and verifiably outsources _that_ computation. Using Pantry, we extend verifiability to MapReduce jobs, simple database queries, and interactions with private state. Thus, Pantry takes another step toward practical proof-based verifiable computation for realistic applications.

Note: Minor edits

Available format(s)
Publication info
Published elsewhere. Major revision. ACM Symposium on Operating Systems Principles (SOSP)
ryptographic protocolsimplementationapplications of PCPszero knowledgeverifiable computation with state
Contact author(s)
pepper @ cs utexas edu
2013-11-14: last of 3 revisions
2013-06-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benjamin Braun and Ariel J.  Feldman and Zuocheng Ren and Srinath Setty and Andrew J.  Blumberg and Michael Walfish},
      title = {Verifying Computations with State (Extended Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2013/356},
      year = {2013},
      doi = {10.1145/2517349.2522733},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.