'Aurora: Transparent Succinct Arguments for R1CS' by DCI's Madars Virza et al.

by: Eli Ben-Sasson (Technion/STARKWare, Haifa, Israel), Alessandro Chiesa (UC Berkeley, Berkeley, USA), Michael Riabzev (Technion/STARKWare, Haifa, Israel), Nicholas Spooner (UC Berkeley, Berkeley, USA), Madars Virza (MIT Media Lab, Cambridge, USA), and Nicholas P. Ward (UC Berkeley, Berkeley, USA).

Abstract:

We design, implement, and evaluate a zero knowledge succinct non-interactive argument (SNARG) for Rank-1 Constraint Satisfaction (R1CS), a widely-deployed NP language undergoing standardization. Our SNARG has a transparent setup, is plausibly post-quantum secure, and uses lightweight cryptography. A proof attesting to the satisfiability of n constraints has size 𝑂(log2𝑛)O(log2⁡n); it can be produced with 𝑂(𝑛log𝑛)O(nlog⁡n) field operations and verified with O(n). At 128 bits of security, proofs are less than 250kB250kB even for several million constraints, more than 10×10× shorter than prior SNARGs with similar features.

A key ingredient of our construction is a new Interactive Oracle Proof (IOP) for solving a univariate analogue of the classical sumcheck problem [LFKN92], originally studied for multivariate polynomials. Our protocol verifies the sum of entries of a Reed–Solomon codeword over any subgroup of a field.

We also provide 𝚕𝚒𝚋𝚒𝚘𝚙libiop, a library for writing IOP-based arguments, in which a toolchain of transformations enables programmers to write new arguments by writing simple IOP sub-components. We have used this library to specify our construction and prior ones, and plan to open-source it.