Paper 2024/1566

Dynamic zk-SNARKs

Abstract

In this work, we put forth 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 two 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 and central contribution is Dynaverse, a dynamic zk-SNARK based on a new dynamic permutation argument that we propose and whose security rests solely KZG commitments. Dynaverse has $O(\sqrt{n}\log n)$ update time and proofs of $O(\log N)$ size. As a central application of dynamic zk-SNARKs, we build a compiler from any dynamic zk-SNARK to a non-trivial (i.e., sublinear) scheme for recursion-free IVC, allowing us for the first time to base non-trivial IVC security solely on KZG commitments, therefore removing any bound on the number of allowed iterations as well any reliance on heuristic security. 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.