Paper 2019/953

PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

Ariel Gabizon, Aztec
Zachary J. Williamson
Oana Ciobotaru
Abstract

zk-SNARK constructions that utilize an updatable universal structured reference string remove one of the main obstacles in deploying zk-SNARKs [GKMMM, Crypto 2018]. The important work of Maller et al. [MBKM, CCS 2019] presented $\mathsf{Sonic}$ - the first potentially practical zk-SNARK with fully succinct verification for general arithmetic circuits with such an SRS. However, the version of $\mathsf{Sonic}$ enabling fully succinct verification still requires relatively high proof construction overheads. We present a universal SNARK construction with fully succinct verification, and significantly lower prover running time (roughly 7.5-20 less group exponentiations than [MBKM] in the fully succinct verifier mode depending on circuit structure). Similarly to [MBKM], we rely on a permutation argument based on Bayer and Groth [Eurocrypt 2012]. However, we focus on ``Evaluations on a subgroup rather than coefficients of monomials''; which enables simplifying both the permutation argument and the artihmetization step.

Note: Inaccuray in sec 6 reg public inputs removed - ack. Patrick Towa

Metadata
Available format(s)
PDF
Publication info
Preprint.
Keywords
zk-SNARKs
Contact author(s)
ariel gabizon @ gmail com
History
2024-02-23: last of 42 revisions
2019-08-21: received
See all versions
Short URL
https://ia.cr/2019/953
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/953,
      author = {Ariel Gabizon and Zachary J.  Williamson and Oana Ciobotaru},
      title = {PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2019/953},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/953}},
      url = {https://eprint.iacr.org/2019/953}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.