Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Simplify and improve the FFT functions (das branch) #444

Closed
asn-d6 opened this issue Jun 24, 2024 · 1 comment
Closed

Simplify and improve the FFT functions (das branch) #444

asn-d6 opened this issue Jun 24, 2024 · 1 comment

Comments

@asn-d6
Copy link
Contributor

asn-d6 commented Jun 24, 2024

This is related to #439 and something I encountered while coding ethereum/consensus-specs#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 asn-d6 changed the title Simplify and improve the FFT functions Simplify and improve the FFT functions (das branch) Jun 27, 2024
@asn-d6
Copy link
Contributor Author

asn-d6 commented Aug 5, 2024

Opened #470 for this

@asn-d6 asn-d6 closed this as completed Aug 5, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant