Welcome to the resource topic for 2023/1264
Title:
An optimization of the addition gate count in Plonkish circuits
Authors: Steve Thakur
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.
ePrint: https://eprint.iacr.org/2023/1264
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .