When Can We Incrementally Prove Computations of Arbitrary Depth?

본문 미리보기

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, ra