Paper 2021/710

VOProof: 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 (PIOP) that matches with the constraint system for which it proves membership. Designing this PIOP 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 this mismatch, we propose a new methodology for designing PIOP, which first designs a middle layer protocol matching the constraint system, called the Vector Oracle protocol, and then compiles it into a PIOP. 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 than PIOPs. The Vector-Oracle-to-PIOP compilation procedure is protocol-independent, allowing us to present and optimize it as a standalone component, leading to a series of improvements. 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 the PLONK circuit. All three zkSNARKs achieve shorter proofs and smaller or identical verification costs compared to the state-of-the-art constructions targeting the same constraint systems. Specifically, VOR1CS defeats Marlin in proof size; VOHPR and VOPLONK outperform Sonic and PLONK, respectively, in both proof sizes and verification costs. In particular, the proof of VOPLONK has only two field elements and seven group elements, thus becoming the shortest among all existing universal-setup zkSNARKs.