Paper 2025/251

Verifiable Streaming Computation and Step-by-Step Zero-Knowledge

Abstract

We propose a new incrementally computable proof system, called Incrementally Verifiable $\mathit{\text{Streaming}}$ Computation (IVsC). IVsC enables computing incremental proofs of correct execution for any RAM program $\mathcal{M}$ on a $\mathit{\text{streaming}}$ input $x$. Input $x$ is called a $\mathit{\text{streaming}}$ input if it is only available on-the-fly as part of an ongoing data generation/streaming process, and not available at once. We also propose a new notion of zero-knowledge features for IVsC that guarantees the proof can be incrementally verified w.r.t.~an encrypted digest, where the proof and digest hide the full data stream. We design zero-knowledge IVsC from a wide variety of standard falsifiable assumptions (such as decision-linear/sub-exponential DDH/LWE). We also introduce a new notion of non-interactive zero-knowledge proofs, that we call $$ zero-knowledge protocols. Such protocols have strong zero-knowledge guarantees, wherein the prover's entire internal memory is simulatable at any point during proof generation. That is, unlike standard zero-knowledge proofs, where only the final proof is simulatable, we can also simulate prover's state at every step of the computation. Such proof systems will be useful in settings where an adversary could corrupt an honest prover even before it generates the full proof. We show that a zero-knowledge IVsC system can be used (almost) as a black-box to design step-by-step zero-knowledge proof systems, therefore secure under standard assumptions.