Implement KZG commitments in Lagrange basis

[lopeetall]

KZG commitments typically use a monomial basis for its structured reference string (SRS). By switching to a Lagrange basis for the SRS we can avoid computing an iFFT for each commitment.

Monomial basis KZG

For secret scalar s and group generator G we have {G, sG, s^2G, ... , s^nG}

Lagrange basis KZG

For secret scalar s and group generator G we have {L_0(s)G, L_1(s)G, L_2(G), ...., L_{n-1}(s)G} where L_k is the kth Lagrange basis polynomial over the domain H, where H is a multiplicative subgroup generated by w. That is, L_k is the polynomial for which L_k(w^k) = 1 but takes the value 0 on all other powers of w.

If the SRS is in Lagrange form (evaluation form), committing to a polynomial that is also in evaluation form is just a multi-scalar multiplication and an iFFT does not need to be performed. Justin Drake refers to this trick in this ZK Study Club talk: https://www.youtube.com/watch?v=TbNauD5wgXM

Changes to be made in ark-plonk

All commitments would need to be modified so that they no longer perform an iFFT before committing if the SRS is in Lagrange form.

Changes to be made elsewhere

KZG setup and commit functions will need to be changed in ark-poly-commit to support Lagrange form setup and commitment

Possibilities

It may be possible to to convert an SRS that was created in monomial form into one in Lagrange form. This might be a major computation but would only need to be done once per setup.

[bhgomes]

Maybe ark-poly-commit could have traits related to choosing an SRS basis, then we just pick the basis we want for our purposes by choosing one trait impl over another.

[simonmasson]

I am working on this task, first in ark-poly-commit and then in this repo.

[CPerezz]

Hey @simonmasson how's this going?

[simonmasson]

Hi. I was able to make the polynomial commitment work in Lagrange basis, but the integration in PLONK is not as simple as expected (it is actually not possible with the current PLONK implementation). It is now in standby (see here for details).