Streaming Authenticated Data Structures

Abstract

In the setting of streaming verifiable computation, a verifier and a prover observe a stream of n elements x1; x2; : : : ; xn and later, the verifier can delegate a computation (e.g., a range search query) to the untrusted prover over the stream. The prover returns the result of the computation and a cryptographic proof for its correctness. To verify the prover's result efficiently, the verifier keeps small local (logarithmic) state, which he updates while observing the stream. The challenge is to enable the verifier to update his local state with no interaction with the prover, while ensuring the prover can compute proofs efficiently.