Add support for ECNTT

[samlaf]

gnark-crypto provides a nice parallelized FFT algorithm on all field elements. I plan to move our codebase (eigenda) to use gnark's FFT instead of our current non-parallelized version (see this PR).

However, we also make use of ECNTT on BN254's G1 curve: https://github.com/Layr-Labs/eigenda/blob/master/encoding/fft/fft_g1.go

Wondering if gnark-crypto has plans to add support for ECNTT, or if there is some reason why it doesn't. The performance gains on ECNTT would be much more significant to us than the improvements we are seeing on Fr. Our slowest ECNTT is ~5seconds on CPU.

[ThomasPiellard]

Hi @samlaf , thank you for using gnark :)

I am not sure to understand, are you talking about the ecfft from Ben Sasson or are you talking about turning an SRS from Canonical form to Lagrange form (as we do here) ?

For the ECNTT (from Ben Sasson), we contemplated doing it at some point, but in fact we don't need it for Linea, and since we currently support only plonk (and some custom version of it) and Groth16 we don't need it for those schemes either. AFAIU the ECNTT is useful when working on a field which does not contain a multiplicative subgroup whose size is a large power of two, and all the curves that we work with have this property.

But if you have a working version of the ECFFT, it could be a nice fit for gnark-crypto.

For which usecase do you need ECFFT ?

[samlaf]

Salut @ThomasPiellard !

I did mean something like the SRS, and not Ben Sasson's field ecftt.
Didn't know you had the ToLagrangeForm function exposed, which is awesome!
One issue though is that it's using a hardcoded private difFFTG1 function, which afaiu only goes in the reverse (IFFT) direction.

Our use case is generating kzg multiproofs following https://eprint.iacr.org/2023/033.pdf, and for that we need G1 FFT in both directions (see here)

Would you be open to me putting up a PR to generalize your difFFTG1 function to be public and go in both directions?

[ThomasPiellard]

Oh I see, I remember this paper yes, there was an fft like operation indeed at some point. Yes you can submit a PR, we'll review it, I need to read the paper again to check everything. Right now we are a bit busy with Linea, so we might not be able to do the review right now