Dynamic zk-SNARKs (with Applications to Sparse zk-SNARKs and IVC)

In this work, we introduce dynamic zk-SNARKs. A dynamic zk-SNARK extends a standard zk-SNARK with an additional update algorithm. This algorithm takes as input a valid source statement–witness pair $(x,w)\in R$ together with a verifying proof $\pi$, and a valid target statement–witness pair $(x',w')\in R$. It outputs a verifying proof $\pi'$ for $(x',w')$ in sublinear time (when $(x,w)$ and $(x',w')$ have small Hamming distance), potentially with the help of a data structure. To the best of our knowledge, no commonly used zk-SNARKs are dynamic: even a single update to $(x,w)$ currently requires recomputing the proof from scratch, which takes at least linear time. After formally defining dynamic zk-SNARKs, we present two constructions: one with $O(\sqrt{n\log n})$ update time and $O(1)$ proof size (Dynaverse), and another with $O(\log^3 n)$ update time and $O(\log^3 n)$ proof size (Dynalog). Both Dynaverse and Dynalog rest on Dynamo, a new zk-SNARK for permutation relations that we introduce. Crucially, Dynamo is sparse, meaning its prover complexity depends only on the number of non-zero entries in the input vector. Our constructions can also be made universal in the random oracle model. We highlight two central applications of dynamic zk-SNARKs. First, we show that they naturally give rise to sparse zk-SNARKs---SNARKs whose prover complexity can be sublinear when the witness vector contains many zeros. In addition, by slightly modifying Dynaverse (rather than using it as a black box), we construct Aero, which to the best of our knowledge is the first sparse zk-SNARK with $O(k\log^2 k)$ prover complexity, where $k$ is the Hamming weight of the witness. Second, we develop a compiler from any dynamic zk-SNARK to recursion-free and bounded incremental verifiable computation (BIVC). Interestingly, when instantiated with a dynamic zk-SNARK that uses a sublinear-size data structure (which we build and call Dynavold), this transformation yields the first BIVC scheme with sublinear state. We finally discuss further applications of dynamic zk-SNARKs, including dynamic state proofs and dynamic ML proofs for retraining.