Paper 2023/552

Customizable constraint systems for succinct arguments

Srinath Setty, Microsoft Research
Justin Thaler, a16z crypto research and Georgetown University
Riad Wahby, Carnegie Mellon University
Abstract

This paper introduces customizable constraint system (CCS), a generalization of R1CS that can simultaneously capture R1CS, Plonkish, and AIR without overheads. Unlike existing descriptions of Plonkish and AIR, CCS is not tied to any particular proof system. Furthermore, we observe that the linear-time polynomial IOP for R1CS in Spartan (CRYPTO 20) extends easily to CCS, and when combined with a polynomial commitment scheme, it yields a family of SNARKs for CCS, which we refer to as SuperSpartan. SuperSpartan supports high-degree constraints without its prover incurring cryptographic costs that scale with the degree of constraints (only field operations scale with the constraint degree). Moreover, as in Spartan, it does not employ superlinear-time and hard-to-distribute operations such as FFTs. Similar properties were achieved for Plonkish by HyperPlonk (EUROCRYPT 23) via a different route. However, it is unclear how to prove CCS instances (or even R1CS instances) with HyperPlonk (or Plonk itself), without overheads. Furthermore, unlike HyperPlonk, SuperSpartan can prove uniform instances of CCS (including AIR) without requiring a linear-time preprocessing for the verifier, and for those instances, SuperSpartan provides “free” addition gates. SuperSpartan for AIR is the first SNARK for AIR with a linear-time prover, transparent and sublinear-time pre-processing, polylogarithmic proof size, and plausible post-quantum security. In particular, SuperSpartan for AIR provides a faster prover than existing transparent SNARKs for AIR (which are sometimes referred to as STARKs).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
succinct argumentscustomizable constraintsSNARKszero-knowledge
Contact author(s)
srinath @ microsoft com
History
2023-05-03: revised
2023-04-19: received
See all versions
Short URL
https://ia.cr/2023/552
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/552,
      author = {Srinath Setty and Justin Thaler and Riad Wahby},
      title = {Customizable constraint systems for succinct arguments},
      howpublished = {Cryptology ePrint Archive, Paper 2023/552},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/552}},
      url = {https://eprint.iacr.org/2023/552}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.