Paper 2023/1264

An optimization of the addition gate count in Plonkish circuits

Steve Thakur, Panther Protocol

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.

Available format(s)
Cryptographic protocols
Publication info
Plonkcircuitaddition gatespermutationKZG
Contact author(s)
stevethakur01 @ gmail com
2023-09-13: last of 5 revisions
2023-08-21: received
See all versions
Short URL
Creative Commons Attribution-ShareAlike


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.