Paper 2023/1264
An optimization of the addition gate count in Plonkish circuits
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)
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Plonkcircuitaddition gatespermutationKZG
- Contact author(s)
- stevethakur01 @ gmail com
- History
- 2024-03-08: last of 6 revisions
- 2023-08-21: received
- See all versions
- Short URL
- https://ia.cr/2023/1264
- License
-
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}, url = {https://eprint.iacr.org/2023/1264} }