Paper 2025/1413

When Can We Incrementally Prove Computations of Arbitrary Depth?

Abstract

Incrementally Verifiable Computation (IVC) allows one to prove the correctness of a computation of potentially unbounded length (or, depth) in an incremental way, while a computationally weak client can efficiently check its correctness in time sublinear in the computation's length. IVC are of practical relevance; yet, most existing IVC schemes are only provably secure for constant-depth computations. Arguing their security for computations of polynomial depth relies on heuristic assumptions, raising both theoretical and practical concerns. More generally, it remains unclear whether these schemes are genuinely insecure at superconstant depths or whether our current proof techniques are simply insufficient. In this work, we delve into the security foundations of incremental proof systems, while at the same time looking for new approaches to prove security at superconstant depths. To this end, we study the relation between the depth of the target computation and IVC security as a question in its own right. Specifically, we ask: - **Can we prove an IVC secure at depth $d =\omega(1)$ if it satisfies a "weak" security property at some "larger" depth $D$?** We uncover a surprising connection between infinitely-often soundness (guaranteed to hold only for some infinite set of parameters) and standard soundness in IVC: a scheme that is infinitely-often sound at $D$ depth achieves \textit{standard} soundness at some smaller depth $d=o(D)$. - **How does a proof system's security degrade with depth?** More precisely, if a scheme loses negligible soundness beyond (e.g.) $O(1)$ depth---the current provable frontier of most practical schemes---can we at least achieve \textit{noticeable} (but arbitrarily low) soundness for \textit{some} superconstant depth? We show the answer is negative. - **Depth boosting: If there exists an IVC scheme secure at depth $d$, does there exist one secure at a greater depth?** We show a simple and \emph{black-box} boosting technique: given an IVC secure at depth $d$, we can construct one secure at depth $D = d^\rho$ for any function $\rho$ such that $d^\rho$ is polynomially bounded ($\rho$ can even be superconstant). This allows us to systematically amplify security from modest depths to much greater ones (e.g., constant to polynomial depth, with only a logarithmic overhead). Our results uncover a nuanced landscape of depth, efficiency, and security in IVC, and new strategies to prove security beyond $O(1)$ depth. They also apply to non-deterministic computations and other soundness notions, including \textbf{incremental functional commitments} (IFC), a streaming variant of functional commitments that we introduce.