Verifying Computations with Streaming Interactive Proofs

By Graham Cormode, Justin Thaler, Ke Yi. 2011

90 citations recorded by the source corpus.

When computation is outsourced, the data owner would like to be assured that the desired computation has been performed correctly by the service provider. In theory, proof systems can give the necessary assurance, but prior work is not sufficiently scalable or practical. In this paper, we develop new proof protocols for verifying computations which are streaming in nature: the verifier (data owner) needs only logarithmic space and a single pass over the input, and after observing the input follows a simple protocol with a prover (service provider) that takes logarithmic communication spread over a logarithmic number of rounds. These ensure that the computation is performed correctly: that the service provider has not made any errors or missed out some data. The guarantee is very strong: even if the service provider deliberately tries to cheat, there is only vanishingly small probability of doing so undetected, while a correct computation is always accepted. We first observe that some theoretical results can be modified to work with streaming verifiers, showing that there are efficient protocols for problems in the complexity classes NP and NC. Our main results then seek to bridge the gap between theory and practice by developing usable protocols for a variety of problems of central importance in streaming and database processing. All these problems require linear space in the traditional streaming model, and therefore our protocols demonstrate that adding a prover can exponentially reduce the effort needed by the verifier. Our experimental results show that our protocols are practical and scalable.

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

Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, methodology): “The core idea behind Prio is reminiscent of techniques used in verifiable computation [16, 37, 62, 69, 97, 115, 116, 119], but in reverse—the client proves to a set of servers that it computed a function correctly.”
SafetyNets: Verifiable Execution of Deep Neural Networks on an Untrusted Cloud (2017, methodology): “As in prior works [5, 17, 18], we restrict our choice of p to Mersenne primes since they afford efﬁcient modular arithmetic implementations, and speciﬁcally to the primes p = 2 61 − 1 and p = 2 127 − 1 .”
Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract (2013, background): “Work in cryptography has focused, for instance, on the problems of computing on encrypted data [37, 39, 38, 19, 41, 40], computing on authenticated data [36], delegation of computation [46, 34, 25, 3, 21, 58], delegation of memory and streams [28, 24], non-interactive zeroknowledge proofs [52, 51, 1”
Scalable, transparent, and post-quantum secure computational integrity (2018, background): “[42] Graham Cormode, Justin Thaler, and Ke Yi.”
Practical verified computation with streaming interactive proofs (2011, background): “The existence of streaming verifiers relies on the fact that such low-degree extensions can be evaluated at any given location incrementally as the data is presented [17].”
Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, background): “[34, 70, 66, 15]): initial reports discussed only small word-size machines, restricted functionality and simple programs.”
Verifiable Computation with Massively Parallel Interactive Proofs (2012, background): “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.”