Paper 2018/828
Aurora: Transparent Succinct Arguments for R1CS
Eli Ben-Sasson and Alessandro Chiesa and Michael Riabzev and Nicholas Spooner and Madars Virza and Nicholas P. Ward
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 $O(\log^2 n)$; it can be produced with $O(n \log n)$ field operations and verified with $O(n)$. At 128 bits of security, proofs are less than 250kB even for several million constraints, more than 10x 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.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- zero knowledgeinteractive oracle proofssuccinct argumentssumcheck protocol
- Contact author(s)
- alexch @ berkeley edu
- History
- 2019-05-08: revised
- 2018-09-06: received
- See all versions
- Short URL
- https://ia.cr/2018/828
- License
-
CC BY