Paper 2018/828

Aurora: Transparent Succinct Arguments for R1CS

Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P. Ward

Abstract

We design, implement, and evaluate a zkSNARK for Rank-1 Constraint Satisfaction (R1CS), a widely-deployed NP-complete language that is undergoing standardization. Our construction uses 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 130kB even for several million constraints, more than 20x shorter than prior zkSNARK 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, an open-source 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2019
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
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/828,
      author = {Eli Ben-Sasson and Alessandro Chiesa and Michael Riabzev and Nicholas Spooner and Madars Virza and Nicholas P.  Ward},
      title = {Aurora: Transparent Succinct Arguments for R1CS},
      howpublished = {Cryptology ePrint Archive, Paper 2018/828},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/828}},
      url = {https://eprint.iacr.org/2018/828}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.