In recent years, numerous new and more efficient constructions of zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) have been proposed, motivated by their growing practical applications. However, in most schemes, when the witness is changed, the prover has to recompute the proof from scratch even if the new witness is close to the old one. This is inefficient for applications where proofs are generated for dynamically changing witnesses with small changes. In this paper, we introduce Dynark, a dynamic zkSNARK scheme that can update the proof in sublinear time when the change of the witness is small. Dynark is built on top of the seminal zkSNARK protocol of Groth, 2016. In the semi-dynamic setting where new witnesses deviate from a single original witness, for an R1CS of size n, after a preprocessing of \(O(n\log n)\) group operations on the original witness, it only takes O(d) group operations and \(O(d\log ^2 d)\) field operations to update the proof for a new witness with distance d from the original witness, which is nearly optimal. In the fully-dynamic setting where witnesses are updated sequentially, the update time of Dynark is \(O(d\sqrt{n\log n})\) group operations and \(O(d\log ^2 d)\) field operations, where d is the distance between two consecutive witnesses. Both the proof size and the verifier time are O(1), which are exactly the same as Groth16. Compared to the scheme in a prior work by Wang et al. 2024, we reduce the proof size from \(O(\sqrt{n})\) to O(1) without relying on pairing product arguments or another zkSNARK, and the update time and the verifier time of Dynark are faster in practice. Experimental results show that for \(n=2^{20}\) , after a one-time preprocessing of 74.3 s, it merely takes 3 ms to update the proof in our semi-dynamic zkSNARK for \(d=1\) , and 60 ms to update the proof in our fully-dynamic zkSNARK. These are 1433 \(\times \) and 73 \(\times \) faster than Groth16, respectively. The proof size is 192 bytes and the verifier time is 4.4 ms. The system is fully compatible with any existing deployment of Groth16 without changing the trusted setup, the proof and the verification algorithm.

Dynark: Making Groth16 Dynamic

会议论文
发表日期：

2026年

查看全文

Tianyu Zhang,
Yupeng Ouyang,
Yupeng Zhang

摘要

In recent years, numerous new and more efficient constructions of zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) have been proposed, motivated by their growing practical applications. However, in most schemes, when the witness is changed, the prover has to recompute the proof from scratch even if the new witness is close to the old one. This is inefficient for applications where proofs are generated for dynamically changing witnesses with small changes. In this paper, we introduce Dynark, a dynamic zkSNARK scheme that can update the proof in sublinear time when the change of the witness is small. Dynark is built on top of the seminal zkSNARK protocol of Groth, 2016. In the semi-dynamic setting where new witnesses deviate from a single original witness, for an R1CS of size n, after a preprocessing of \(O(n\log n)\) group operations on the original witness, it only takes O(d) group operations and \(O(d\log ^2 d)\) field operations to update the proof for a new witness with distance d from the original witness, which is nearly optimal. In the fully-dynamic setting where witnesses are updated sequentially, the update time of Dynark is \(O(d\sqrt{n\log n})\) group operations and \(O(d\log ^2 d)\) field operations, where d is the distance between two consecutive witnesses. Both the proof size and the verifier time are O(1), which are exactly the same as Groth16. Compared to the scheme in a prior work by Wang et al. 2024, we reduce the proof size from \(O(\sqrt{n})\) to O(1) without relying on pairing product arguments or another zkSNARK, and the update time and the verifier time of Dynark are faster in practice. Experimental results show that for \(n=2^{20}\) , after a one-time preprocessing of 74.3 s, it merely takes 3 ms to update the proof in our semi-dynamic zkSNARK for \(d=1\) , and 60 ms to update the proof in our fully-dynamic zkSNARK. These are 1433 \(\times \) and 73 \(\times \) faster than Groth16, respectively. The proof size is 192 bytes and the verifier time is 4.4 ms. The system is fully compatible with any existing deployment of Groth16 without changing the trusted setup, the proof and the verification algorithm.