  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.
