Scholarlink

In this work, we introduce dynamic zk-SNARKs. A dynamic zk-SNARK extends a standard zk-SNARK with an additional update algorithm. This algorithm takes as input a valid source statement-witness pair \((\mathbb {x},\mathbb {w})\in \mathcal {R}\) together with a verifying proof \(\pi \) , and a valid target statement-witness pair \((\mathbb {x}',\mathbb {w}')\in \mathcal {R}\) . It outputs a verifying proof \(\pi '\) for \((\mathbb {x}',\mathbb {w}')\) in sublinear time (when \((\mathbb {x},\mathbb {w})\) and \((\mathbb {x}',\mathbb {w}')\) have small Hamming distance), potentially with the help of a data structure. To the best of our knowledge, no commonly used zk-SNARKs are dynamic: even a single update to \((\mathbb {x},\mathbb {w})\) currently requires recomputing the proof from scratch, which takes at least linear time. After formally defining dynamic zk-SNARKs, we present two constructions: one with \(O(\sqrt{n\log n})\) update time and O(1) proof size (Dynaverse), and another with \(O(\log ^3 n)\) update time and \(O(\log ^3 n)\) proof size (Dynalog). Both Dynaverse and Dynalog rest on Dynamo, a new zk-SNARK for permutation relations that we introduce. Crucially, Dynamo is sparse, meaning its prover complexity depends only on the number of non-zero entries in the input vector. Our constructions can also be made universal in the random oracle model. We highlight two central applications of dynamic zk-SNARKs. First, we show that they naturally give rise to sparse zk-SNARKs—SNARKs whose prover complexity can be sublinear when the witness vector contains many zeros. In addition, by slightly modifying Dynaverse (rather than using it as a black box), we construct Aero, which to the best of our knowledge is the first sparse zk-SNARK with \(O(k\log ^2 k)\) prover complexity, where k is the Hamming weight of the witness. Second, we develop a compiler from any dynamic zk-SNARK to recursion-free and bounded incremental verifiable computation (BIVC). Interestingly, when instantiated with a dynamic zk-SNARK that uses a sublinear-size data structure (which we build and call Dynavold), this transformation yields the first BIVC scheme with sublinear state. We finally discuss further applications of dynamic zk-SNARKs, including dynamic state proofs and dynamic ML proofs for retraining.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Dynamic zk-SNARKs (with Applications to Sparse zk-SNARKs and IVC)

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Weijie Wang,
  • Charalampos Papamanthou,
  • Shravan Srinivasan,
  • Dimitrios Papadopoulos

摘要

In this work, we introduce dynamic zk-SNARKs. A dynamic zk-SNARK extends a standard zk-SNARK with an additional update algorithm. This algorithm takes as input a valid source statement-witness pair \((\mathbb {x},\mathbb {w})\in \mathcal {R}\) together with a verifying proof \(\pi \) , and a valid target statement-witness pair \((\mathbb {x}',\mathbb {w}')\in \mathcal {R}\) . It outputs a verifying proof \(\pi '\) for \((\mathbb {x}',\mathbb {w}')\) in sublinear time (when \((\mathbb {x},\mathbb {w})\) and \((\mathbb {x}',\mathbb {w}')\) have small Hamming distance), potentially with the help of a data structure. To the best of our knowledge, no commonly used zk-SNARKs are dynamic: even a single update to \((\mathbb {x},\mathbb {w})\) currently requires recomputing the proof from scratch, which takes at least linear time. After formally defining dynamic zk-SNARKs, we present two constructions: one with \(O(\sqrt{n\log n})\) update time and O(1) proof size (Dynaverse), and another with \(O(\log ^3 n)\) update time and \(O(\log ^3 n)\) proof size (Dynalog). Both Dynaverse and Dynalog rest on Dynamo, a new zk-SNARK for permutation relations that we introduce. Crucially, Dynamo is sparse, meaning its prover complexity depends only on the number of non-zero entries in the input vector. Our constructions can also be made universal in the random oracle model. We highlight two central applications of dynamic zk-SNARKs. First, we show that they naturally give rise to sparse zk-SNARKs—SNARKs whose prover complexity can be sublinear when the witness vector contains many zeros. In addition, by slightly modifying Dynaverse (rather than using it as a black box), we construct Aero, which to the best of our knowledge is the first sparse zk-SNARK with \(O(k\log ^2 k)\) prover complexity, where k is the Hamming weight of the witness. Second, we develop a compiler from any dynamic zk-SNARK to recursion-free and bounded incremental verifiable computation (BIVC). Interestingly, when instantiated with a dynamic zk-SNARK that uses a sublinear-size data structure (which we build and call Dynavold), this transformation yields the first BIVC scheme with sublinear state. We finally discuss further applications of dynamic zk-SNARKs, including dynamic state proofs and dynamic ML proofs for retraining.