Paper 2013/356

Verifying computations with state

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

Abstract

When outsourcing computations to the cloud or other third-parties, a key issue for clients is the ability to verify the results. Recent work in proof-based verifiable computation, building on deep results in complexity theory and cryptography, has made significant progress on this problem. However, all existing systems require computational models that do not incorporate state. This limits these systems to simplistic programming idioms and rules out computations where the client cannot materialize all of the input (e.g., very large MapReduce instances or database queries). This paper describes Pantry, the first built system that incorporates state. Pantry composes the machinery of proof-based verifiable computation with ideas from untrusted storage: the client expresses its computation in terms of digests that attests to state, and verifiably outsources that computation. Besides the boon to expressiveness, the client can gain from outsourcing even when the computation is sublinear in the input size. We describe a verifiable MapReduce application and a queriable database, among other simple applications. Although the resulting applications result in server overhead that is higher than we would like, Pantry is the first system to provide verifiability for realistic applications in a realistic programming model.