Paper 2024/1566

Dynamic zk-SNARKs

Weijie Wang, Yale University
Charalampos Papamanthou, Yale University, Lagrange Labs
Shravan Srinivasan, Lagrange Labs
Dimitrios Papadopoulos, Hong Kong University of Science and Technology, Lagrange Labs
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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Zero knowledge proofs
Contact author(s)
weijie wang @ yale edu
charalampos papamanthou @ yale edu
shravan @ lagrange dev
dipapado @ cse ust hk
History
2025-06-03: last of 2 revisions
2024-10-04: received
See all versions
Short URL
https://ia.cr/2024/1566
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1566,
      author = {Weijie Wang and Charalampos Papamanthou and Shravan Srinivasan and Dimitrios Papadopoulos},
      title = {Dynamic zk-{SNARKs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1566},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1566}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.