Verifying computations with state

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 proofbased
verifiable computation for realistic applications.