Practical verified computation with streaming interactive proofs

By Graham Cormode, Michael M. Mitzenmacher, Justin Thaler. 2011

273 citations recorded by the source corpus.

When delegating computation to a service provider, as in the cloud computing paradigm, we seek some reassurance that the output is correct and complete. Yet recomputing the output as a check is inefficient and expensive, and it may not even be feasible to store all the data locally. We are therefore interested in what can be validated by a streaming (sublinear space) user, who cannot store the full input, or perform the full computation herself. Our aim in this work is to advance a recent line of work on "proof systems" in which the service provider proves the correctness of its output to a user. The goal is to minimize the time and space costs of both parties in generating and checking the proof. Only very recently have there been attempts to implement such proof systems, and thus far these have been quite limited in functionality. Here, our approach is two-fold. First, we describe a carefully chosen instantiation of one of the most efficient general-purpose constructions for arbitrary computations (streaming or otherwise), due to Goldwasser, Kalai, and Rothblum [19]. This requires several new insights and enhancements to move the methodology from a theoretical result to a practical possibility. Our main contribution is in achieving a prover that runs in time O(S(n) log S(n)), where S(n) is the size of an arithmetic circuit computing the function of interest; this compares favorably to the poly(S(n)) runtime for the prover promised in [19]. Our experimental results demonstrate that a practical general-purpose protocol for verifiable computation may be significantly closer to reality than previously realized. Second, we describe a set of techniques that achieve genuine scalability for protocols fine-tuned for specific important problems in streaming and database processing. Focusing in particular on non-interactive protocols for problems ranging from matrix-vector multiplication to bipartite perfect matching, we build on prior work [8, 5] to achieve a prover that runs in nearly linear-time, while obtaining optimal tradeoffs between communication cost and the user's working memory. Existing techniques required (substantially) superlinear time for the prover. Finally, we develop improved interactive protocols for specific problems based on a linearization technique originally due to Shen [33]. We argue that even if general-purpose methods improve, fine-tuned protocols will remain valuable in real-world settings for key problems, and hence special attention to specific problems is warranted.

Subfields: Artificial Intelligence, Computer Networks and Communications

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

In Computer Networks and Communications

Citations in the corpus

Geppetto: Versatile Verifiable Computation (2015, background): “Some previous verifiable computations systems do not include a compiler [22, 52], while those that do [10, 16, 46] have typically compiled small examples with less than 100 lines of C code.”
Pinocchio: Nearly Practical Verifiable Computation (2013, methodology): “We omit results from another recent effort [25, 26], since it only applies to highly-parallelizable computations.”
Verifying computations with state (2013, background): “Computing the second moment of a frequency vector of length m [12].”
Verifiable differential privacy (2015, methodology): “One set of projects [11, 45, 46], derived from Goldwasser et al.”
Efficient RAM and control flow in verifiable outsourced computation (2015, background): “Variants of this problem have been around for decades [10]; today, cloud computing is a particularly pertinent use case.”
Quadratic Span Programs and Succinct NIZKs without PCPs (2013, background): “We find that QAPs outperform QSPs, and that Pinocchio significantly outperforms state-of-the-art systems [16, 40] based on PCPs [2, 25, 30].”
A Survey of Verifiable Computation (2017, methodology): “However, there are still some drawbacks in the above schemes [10, 21, 67].”
Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs (2019, unknown): “We note that without the zero-knowledge requirement, several existing interactive proof systems from the literature, including the GKR protocol [53], the CMT protocol [37], and the RRR protocol [78] can be viewed as fully linear IOPs.”
Demystifying Incentives in the Consensus Computer (2015, methodology): “Verifiable computation methods on consensus computers differ from techniques that have been used on classical computers [8, 9, 10, 11, 12, 13, 14].”
The Efficient Server Audit Problem, Deduplicated Re-execution, and the Web (2017, background): “A possibility is probabilistic proofs [20, 23, 32, 65, 75, 89], but they cannot handle our workloads, so we would have to estimate, and the estimates would yield outlandish speedups for OROCHI (over 106×).”
Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture (2014, methodology): “A set of works [32, 68, 67] has optimized and implemented the protocol of [42].”
Verifiable Computation with Massively Parallel Interactive Proofs (2012, methodology): “We believe our results demonstrate the immediate practicality of using GPUs for verifiable computation, and more generally, that protocols for verifiable computation have become sufficiently mature to deploy in real cloud computing systems.”
Scalable Zero Knowledge with No Trusted Setup (2019, background): “This led to a line of realizations in code, early works lacked ZK [36, 35, 76, 78], but the state-of-the-art ones, like [82] and Hyrax [80], do have it.”
Full Accounting for Verifiable Outsourcing (2017, methodology): “…d ( y and ˜ V y are similar). b tot / 2 b tot / 2 dot products of length 2 b tot / 2 ; // this costs N · G multiplications In the baseline approach [36, 77, 81, 82] to computing H ( τ ) , P sends evaluations (meaning H ( 0 ) , . . . , H ( b G ) ), and V uses Lagrange (Lagrange interpolation…”
Verifying computations without reexecuting them (2015, methodology): “This approach relies on interactive proof protocols [3, 26, 32], most notably Muggles [25], which was reﬁned and implemented [18, 45–47].”
A Hybrid Architecture for Interactive Verifiable Computation (2013, background): “The following description of our problem statement and framework borrows heavily from our prior treatments [44, 47].”
Doubly-Efficient zkSNARKs Without Trusted Setup (2018, methodology): “bine an interactive proof [35, 49, 97] and a verifiable polynomial delegation scheme [61, 78] to construct a succinct, non-ZK interactive argument.”
Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, background): “IP-based: The proofs for muggles approach [44] scales down Interactive Proofs (IP) from PSPACE to P and leads to excellent solutions for a limited yet interesting class of programs: those with high parallelism and small memory consumption; prover time for IP-based systems was reduced to quasi-linear”