Paper 2023/1264

An optimization of the addition gate count in Plonkish circuits

Steve Thakur, Panther Protocol
Abstract

We slightly generalize Plonk's ([GWC19]) permutation argument by replacing permutations with (possibly non-injective) self-maps of an interval. We then use this succinct argument to obtain a protocol for weighted sums on committed vectors, which, in turn, allows us to eliminate the intermediate gates arising from high fan-in additions in Plonkish circuits. We use the KZG10 polynomial commitment scheme, which allows for a universal updateable CRS linear in the circuit size. In keeping with our recent work ([Th23]), we have used the monomial basis since it is compatible with any sufficiently large prime scalar field. In settings where the scalar field has a suitable smooth order subgroup, the techniques can be efficiently ported to a Lagrange basis. The proof size is constant, as is the verification time which is dominated by a single pairing check. For committed vectors of length $n$, the proof generation is $O(n\cdot \log(n))$ and is dominated by the $\mathbb{G}_1$-MSMs and a single sum of a few polynomial products over the prime scalar field via multimodular FFTs.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Plonkcircuitaddition gatespermutationKZG
Contact author(s)
stevethakur01 @ gmail com
History
2023-09-13: last of 5 revisions
2023-08-21: received
See all versions
Short URL
https://ia.cr/2023/1264
License
Creative Commons Attribution-ShareAlike
CC BY-SA

BibTeX

@misc{cryptoeprint:2023/1264,
      author = {Steve Thakur},
      title = {An optimization of the addition gate count in Plonkish circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1264},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1264}},
      url = {https://eprint.iacr.org/2023/1264}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.