gnark-crypto
gnark-crypto copied to clipboard
Consensys
FRI+ECFFT
FRI is an interactive oracle proof of proximity for polynomials to assess probabilistically (in a logarithmic-in-the-degree number of rounds) if a function, provided as an oracle, is a low degree polynomial. It leverages the same structure than the FFT, that is it works on a sequence of finite algebraic groups, with associated rational maps (which can be the identity, as in the multiplicative FFT), linked together by surjective maps with given kernel. As the ECFFT is used to mimic the FFT in an arbitrary finite field, the ECFFT technique can be used to implement FRI on an arbitrary finite field. The ECFFT allows to do fast polynomials operations (like division) on an arbitrary finite field. However, when working on arbitrary finite fields, one lacks an efficient polynomial commitment scheme. With FRI+ECFFT, this gap is filled because FRI can be transposed on arbitrary finite fields. It would allow PLONK to work on an arbitrary finite field.
