Applications based on outsourcing computation require guarantees to the data owner that the desired computation has been performed correctly by the service provider. Methods based on proof systems can give the data owner the necessary assurance, but previous work does not give a sufficiently scalable and practical solution, requiring a lot of time, space or computational power for both parties. In this paper, we develop new proof protocols for verifying computations which are streaming in nature: the verifier (data owner) needs only a single pass over the input storing a logarithmic amount of information, and follows a simple protocol with a prover (service provider) that takes a logarithmic number of rounds. A dishonest prover fools the verifier with only polynomially small probability, while an honest prover's answer is always accepted.

We first observe that some existing constructions for interactive proof systems
can be modified to work with streaming verifiers. The consequences are powerful:
these constructions imply that
all problems in the complexity class NP have
\emph{computationally sound} streaming protocols requiring a polylogarithmic communication and space, and that all problems in log-space uniform NC have \emph{statistically sound}
protocols with the same space and communication requirements.

We then seek to bridge the gap between theory and practice by developing improved and simplified protocols for a variety of problems of central importance in streaming and database processing. All of our protocols achieve statistical soundness and most require only logarithmic communication between prover and verifier. We also experimentally demonstrate their practicality and scalability. All these problems require linear space in the traditional streaming model, showing that adding a prover can exponentially reduce the effort needed by the verifier.