c-kzg-4844 icon indicating copy to clipboard operation
c-kzg-4844 copied to clipboard

Simplify and improve the FFT functions (`das` branch)

Open asn-d6 opened this issue 8 months ago • 0 comments

This is related to https://github.com/ethereum/c-kzg-4844/issues/439 and something I encountered while coding https://github.com/ethereum/consensus-specs/pull/3781 in c-kzg.

The function fft_fr() in c-kzg is hardcoded to use expanded_roots_of_unity (subgroup of size 8192) even tho it takes a configurable size n parameter.

The function is used with at least n=8192 (good case), n=2048 and n=128 throughout the protocol.

Due to hardcoding a specific subgroup, when it's called with the wrong n the FFT does not do what it's supposed to do (evaluate/interpolate the polynomial), but it does work in the sense of: recovered_poly_coeff == ifft(fft(poly_coeff)) and hence the protocol carries through.

We should make sure that the code does what it's supposed to do here for all cases of n.

Also, we should simplify the FFT implementation when possible. For example, is there a reason for the stride arguments?

asn-d6 avatar Jun 24 '24 12:06 asn-d6