Paper 2024/1566

Dynamic zk-SNARKs

Abstract

In this work, we introduce the notion of dynamic zk-SNARKs. A dynamic zk-SNARK is a zk-SNARK that has an additional update algorithm. The update algorithm takes as input a valid source statement-witness pair $(x,w)\in R$ along 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 (for $(x,w)$ and $(x',w')$ with small Hamming distance) potentially with the help of a data structure. To the best of our knowledge, none of the commonly-used zk-SNARKs are dynamic---a single update in $(x,w)$ can be handled only by recomputing the proof, which requires at least linear time. After formally defining dynamic zk-SNARKs, we present three constructions. The first one, Dynarec, is based on recursive zk-SNARKs, has $O(\log n)$ update time and is folklore, in the sense that it shares similarities (and limitations such as small number of compositions and heuristic security) with existing tree-based Incremental Verifiable Computation (IVC) schemes. Our second contribution is Dynaverse, a dynamic zk-SNARK based on a new dynamic permutation argument that we propose---Dynamo. Dynaverse has $O(\sqrt{n}\log n)$ update time and proofs of $O(1)$ size. The security of Dynaverse rests upon the $q$-DLOG assumption in the Algebraic Group Model (AGM)---the same assumption used to prove security of the celebrated Groth16 zk-SNARK. Our final construction, Dynalog, further advances Dynaverse via a data structure of exponentially-increasing levels and maintainable vector commitments to finally achieve polylogarithmic update time and proofs of $O(\log n)$ size, again under $q$-DLOG in the AGM (With a single level of SNARK composition, therefore not affecting security, Dynalog's proofs can be further compressed down to $O(1)$.) As a central application of dynamic zk-SNARKs, we build a compiler from any dynamic zk-SNARK to bounded-step and recursion-free IVC, a model introduced by Tyagi et al. in 2022. Interestingly, when this transformation is instantiated with a slight modification of Dynaverse, we derive the first bounded-step and recursion-free IVC with sublinear space, removing the need for maintaining a linear-time server for retrieving proofs. We also detail additional applications of dynamic zk-SNARKs such as dynamic state proofs and keyless authentication. Our preliminary evaluation shows that Dynaverse outperforms baseline PLONK proof recomputation by up to approximately 500x as well as heuristically-secure and asymptotically-superior Dynarec by up to one order of magnitude.