Paper 2024/1566

Dynamic zk-SNARKs (with applications to sparse zk-SNARKs and IVC)

Abstract

In this work, we introduce \emph{dynamic zk-SNARKs}. A dynamic zk-SNARK extends a standard zk-SNARK with an additional \emph{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 \emph{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 (\textsf{Dynaverse}), and another with $O(\log^3 n)$ update time and $O(\log^3 n)$ proof size (\textsf{Dynalog}). Both \textsf{Dynaverse} and \textsf{Dynalog} rest on \textsf{Dynamo}, a new zk-SNARK for permutation relations that we introduce. Crucially, \textsf{Dynamo} is \emph{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 \textsf{Dynaverse} (rather than using it as a black box), we construct \textsf{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 \emph{recursion-free} and \emph{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 \textsf{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.