Paper 2013/356
Verifying Computations with State (Extended Version)
Benjamin Braun, Ariel J. Feldman, Zuocheng Ren, Srinath Setty, Andrew J. Blumberg, and Michael Walfish
Abstract
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
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Major revision. ACM Symposium on Operating Systems Principles (SOSP)
- DOI
- 10.1145/2517349.2522733
- Keywords
- ryptographic protocolsimplementationapplications of PCPszero knowledgeverifiable computation with state
- Contact author(s)
- pepper @ cs utexas edu
- History
- 2013-11-14: last of 3 revisions
- 2013-06-10: received
- See all versions
- Short URL
- https://ia.cr/2013/356
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2013/356,
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},
url = {https://eprint.iacr.org/2013/356}
}
