Cryptology ePrint Archive: Report 2019/953

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

Ariel Gabizon and Zachary J. Williamson and 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.

Category / Keywords: zk-SNARKs

Date: received 21 Aug 2019, last revised 3 Sep 2020

Contact author: ariel gabizon at gmail com

Available format(s): PDF | BibTeX Citation

Note: degree correction in last section - ack Thore Hildebrandt

Version: 20200903:165011 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]