Paper 2021/710
VCProof: Constructing Shorter and Faster-to-Verify zkSNARKs with Vector Oracles
Yuncong Zhang and Ren Zhang and Geng Wang and Dawu Gu
Abstract
The construction of zkSNARKs involves designing a Polynomial IOP that matches with the constraint system for which it proves membership. Designing this Polynomial IOP is a challenging task because the constraint system is typically not expressed in terms of polynomials but in terms of matrices and vectors. To mitigate mismatch, we propose a new methodology for the first step in SNARK construction, that first designs a matching Vector Oracle protocol before compiling it into a Polynomial IOP. The native first-class citizens of the Vector Oracle protocol are vectors; and by virtue of matching with the language of the arithmetic constraint system, Vector Oracle protocols are more intuitive to design and analyze. The Vector-Oracle-to-PIOP compilation procedure is protocol-independent, allowing us to present and optimize it as a standalone component, leading to the discovery of a series of acceleration techniques. We apply our methodology to construct three zkSNARKs, each targeting a constraint system: the Rank-1 Constaint System (R1CS), the Hadamard Product Relation (HPR), and a modified PLONK circuit. All three zkSNARKs achieve shorter proofs and/or smaller verification costs compared to the state-of-the-art constructions targeting the same constraint systems. Specifically, VCProof/R1CS defeats Marlin in proof size, with a slightly higher verification cost; VCProof/HPR and VCProof/POV outperform Sonic and PLONK, respectively, in both proof sizes and verification costs. In particular, the proof of VCProof/POV has only two field elements and six group elements, thus becoming the shortest among all existing universal-setup zkSNARKs.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- Zero-KnowledgeSNARKPIOPVector Oracle
- Contact author(s)
- shjdzhangyuncong @ sjtu edu cn
- History
- 2024-02-27: last of 6 revisions
- 2021-05-28: received
- See all versions
- Short URL
- https://ia.cr/2021/710
- License
-
CC BY