Welcome to the resource topic for 2024/1566
Title:
Dynamic zk-SNARKs
Authors: Weijie Wang, Charalampos Papamanthou, Shravan Srinivasan, Dimitrios Papadopoulos
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 \mathcal{L} along with a verifying proof \pi, and a valid target statement-witness pair (x',w')\in \mathcal{L}. 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 presenting the formal definition of dynamic zk-SNARKs, we provide two constructions. The first one is based on recursive SNARKs and has O(\log n) update time. However it suffers from heuristic security—it must encode the random oracle in the SNARK circuit. The second one and our central contribution, \mathsf{Dynaverse}, is based solely on KZG commitments and has O(\sqrt{n}\log n) update time. Our preliminary evaluation shows, that, while worse asymptotically, \mathsf{Dynaverse} outperforms the recursive-based approach by at least one order of magnitude.
ePrint: https://eprint.iacr.org/2024/1566
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .