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.