Cryptology ePrint Archive: Report 2013/356

Verifying Computations with State (Extended Version)

Benjamin Braun and Ariel J. Feldman and Zuocheng Ren and Srinath Setty and 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.

Category / Keywords: ryptographic protocols / implementation, applications of PCPs, zero knowledge, verifiable computation with state

Original Publication (with major differences): ACM Symposium on Operating Systems Principles (SOSP)
DOI: 10.1145/2517349.2522733

Date: received 7 Jun 2013, last revised 14 Nov 2013

Contact author: pepper at cs utexas edu

Available format(s): PDF | BibTeX Citation

Note: Minor edits

Version: 20131114:135428 (All versions of this report)

Short URL: ia.cr/2013/356

Discussion forum: Show discussion | Start new discussion