Verifying computations with state

By Benjamin Braun, Ariel J. Feldman, Zuocheng Ren, Srinath T. V. Setty, Andrew Justin Blumberg, Michael Walfish. 2013

209 citations recorded by the source corpus.

When a client outsources a job to a third party (e.g., the cloud), how can the client check the result, without re-executing 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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Program Analysis & Verification, Automated Theorem Proving & Formal Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Srinath T. V. Setty
  2. Dan Boneh
  3. Michael Walfish
  4. Eli Ben-Sasson
  5. Andrew Justin Blumberg
  6. Justin Thaler
  7. Eran Tromer
  8. Alessandro Chiesa

In Computer Networks and Communications

  1. Srinath T. V. Setty
  2. Michael Walfish
  3. Dan Boneh
  4. Andrew Justin Blumberg
  5. Eli Ben-Sasson
  6. Justin Thaler
  7. Eran Tromer
  8. Alessandro Chiesa

In Program Analysis & Verification

  1. Srinath T. V. Setty
  2. Michael Walfish
  3. Arjun Narayan
  4. Andrew Justin Blumberg
  5. Eli Ben-Sasson
  6. Justin Thaler
  7. Alessandro Chiesa
  8. Eran Tromer

In Automated Theorem Proving & Formal Methods

  1. Srinath T. V. Setty
  2. Michael Walfish
  3. Arjun Narayan
  4. Eran Tromer
  5. Eli Ben-Sasson
  6. Andrew Justin Blumberg
  7. Alessandro Chiesa
  8. Madars Virza

Citations in the corpus