Consensys
bug: FFT should error if size of input doesn't match domain
Description
Currently in the process of moving our codebase from using our own non-parallelized Fr.FFT implementation to gnark-crypto's implementation, which is much faster (up to 6x on 16iB blobs).
In doing so, I ran into a pretty nasty bug. Our current implementation allows to use a larger domain becuase we store all roots of unity and just skip when input is smaller power of 2 than number of roots of unity. We thus share a large domain for a few different sized FFTs. When moving to gnark-crypto's FFT, I also reused the same strategy, only to realize that gnark-crypto's FFT will happily encode the data and given wrong results! (not super sure why yet.. assuming it has to do with twiddles used... or CardinalityInv... or all of these reasons)
Expected/Actual Behavior
Is this expected? Is there a use case for using a different sized domain?
Possible Fix
If there is no reason, then I suggest checking the len against len cardinality, and returning an error if not the same size. If there is some weird reason... then would be nice to document it and explain the behavior (FFT's documentation is pretty sparse..)
Steps to Reproduce
Pretty late right now, but I can pretty easily create a reproducible test if needed tomorrow. Let me know.
Your Environment
- gnark-crypto version used: v0.18.0
- go version (e.g. 1.20.6): 1.24
- Operating System and version: macos 15.7.1
Thanks for the report. Indeed I think it should be possible to use larger canonical FFT domain for doing FFT on smaller domains (by computing the canonical basis from sliced canonical basis). I'm currently not fully sure which basis we store, but I think there should be a nice solution.
We'll look into it after a few days. Please ping again next week if issue seems stale :)
