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 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)R along with a verifying proof π, and a valid target statement-witness pair (x,w)R. It outputs a verifying proof for in sublinear time (for and 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 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 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 update time and proofs of 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.

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-02-14: revised
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.