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
- Srinath T. V. Setty
- Dan Boneh
- Michael Walfish
- Eli Ben-Sasson
- Andrew Justin Blumberg
- Justin Thaler
- Eran Tromer
- Alessandro Chiesa
In Computer Networks and Communications
- Srinath T. V. Setty
- Michael Walfish
- Dan Boneh
- Andrew Justin Blumberg
- Eli Ben-Sasson
- Justin Thaler
- Eran Tromer
- Alessandro Chiesa
In Program Analysis & Verification
- Srinath T. V. Setty
- Michael Walfish
- Arjun Narayan
- Andrew Justin Blumberg
- Eli Ben-Sasson
- Justin Thaler
- Alessandro Chiesa
- Eran Tromer
In Automated Theorem Proving & Formal Methods
- Srinath T. V. Setty
- Michael Walfish
- Arjun Narayan
- Eran Tromer
- Eli Ben-Sasson
- Andrew Justin Blumberg
- Alessandro Chiesa
- Madars Virza
Citations in the corpus
- Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, background): “An interesting challenge would be to try to reduce the client’s bandwidth usage without resorting to relatively expensive public-key cryptographic techniques [17, 18, 26, 41, 97].”
- Geppetto: Versatile Verifiable Computation (2015, methodology): “We compare the use of MultiQAPs for shared state with the use of hashing in prior work such as Pantry [16].”
- Pinocchio: Nearly Practical Verifiable Computation (2013, methodology): “We compare against (1) a naïve version of a PCP-based scheme(22); (2) GGP,9 an early scheme that defined VC, but which relies on FHE; (3) Pepper,22 an optimized refinement of (1); (4) Ginger,23 a further refinement of Pepper; (5) Ginger with a batch of one million simultaneous”
- VC3: Trustworthy Data Analytics in the Cloud Using SGX (2015, background): “In some cases, one of the parties may have access to the data in the clear, while the others only have to verify the result, using zero-knowledge proofs (see e. g., Pinocchio [48], Pantry [13], and ZQL [21]).”
- Practical verified computation with streaming interactive proofs (2011, background): “also exploits the ability of these argument systems to support circuits that take advice [20].”
- Doubly-Efficient zkSNARKs Without Trusted Setup (2018, methodology): “proof (PCP)3 and ZK transform that form the basis of many recent zkSNARK implementations [4, 5, 12, 13, 15, 16, 29, 34, 36, 39, 42–44, 64, 76, 79, 105], including systems deployed in applications like ZCash [12, 107].”
- Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture (2014, methodology): “An efficiency comparison with other non-universal circuit generators [66, 64, 56, 27] is not well-defined.”
- Efficient RAM and control flow in verifiable outsourced computation (2015, background): “• Zero-knowledge: The protocol provides no information to the verifier—beyond what the verifier can deduce itself— about the values in z.”
- The Bouncer Problem: Challenges to Remote Explainability (2019, background): “In proof-based ver-ifiable computation [7], the provider returns the results of a queried computation, along with a proof for that computation.”
- Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, methodology): “We are motivated to design such succinct zero-knowledge arguments because there is significant interest in employing them in many applications including delegation of computation [40, 76, 80–84, 86] and stateful services [33, 39, 41, 47, 79, 94], distributed ledgers and blockchains [15, 31, 36, 67],”
- Distributed Differential Privacy and Applications (2015, methodology): “VerDP uses the Pantry (Braun et al., 2013) system for verifiable computation, configured with the Pinocchio (Parno et al.”
- Full Accounting for Verifiable Outsourcing (2017, methodology): “…an arithmetic circuit (AC). domain is a finite field F , usually F p (the integers mod a prime p ); The front-end transforms Ψ from its original expression to an AC, denoted C ; this step often uses a compiler [19, 22, 31, 32, assertion “ y = C( x ) ”; this step incorporates tools from complexity”
- Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation (2019, background): “[26] introduced quadratic arithmetic programs (QAPs), which forms the basis of most recent implementations [11,14,19,23,25,40,46] including libSNARK [13].”
- Verifying computations without reexecuting them (2015, background): “(For evaluations that take additional resources into account, see Braun et al. [14].)”
- ALITHEIA: Towards Practical Verifiable Graph Processing (2014, methodology): “A VC protocol for graph algorithms can be derived in theory via black-box use of existing general-purpose VC schemes [18, 14, 24, 9, 10, 19, 11], or one of the systems that have been built to apply these techniques [33, 32, 30, 7, 12, 36].”
- Scalable Zero Knowledge Via Cycles of Elliptic Curves (2014, methodology): “[22] uses memory checking to verify accesses to an untrusted storage.”
- Demystifying Incentives in the Consensus Computer (2015, background): “One popular line of work uses classical computers for verification that involves prior trust establishment to guarantee that G does not deviate after knowing the solution [8, 9, 10, 11, 12, 13, 14].”