Paper 2021/1167

fflonk: a Fast-Fourier inspired verifier efficient version of PlonK

Ariel Gabizon and Zachary J. Williamson

Abstract

We present a variant of the Kate, Zaverucha and Goldberg polynomial commitment scheme [KZG] where $d$ polynomials can be opened at a point that is a $d$'th power, such that the amount of verifier group operations does not depend on $d$. Our method works by reducing opening multiple polynomials at a single point $x$, to opening a single polynomial at many points via an ``FFT-like identity''. As an application we present a version of the PlonK zk-SNARK[GWC] with significantly improved verifier performance, at the cost roughly tripling the prover time. Specifically, in addition to the two pairings, the verifier only performs five scalar multiplications, rather than 16 or 18 as in the versions presented in [GWC].

Note: typos

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
zk-SNARKsPolynomial Commitment Schemes
Contact author(s)
ariel gabizon @ gmail com
History
2021-11-01: last of 4 revisions
2021-09-14: received
See all versions
Short URL
https://ia.cr/2021/1167
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1167,
      author = {Ariel Gabizon and Zachary J.  Williamson},
      title = {fflonk: a Fast-Fourier inspired verifier efficient version of PlonK},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1167},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1167}},
      url = {https://eprint.iacr.org/2021/1167}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.