plonky2 icon indicating copy to clipboard operation
plonky2 copied to clipboard

fix: optimize polynomial folding process in batch FRI prover

Open crStiv opened this issue 11 months ago • 0 comments

This PR optimizes the polynomial folding process in the batch FRI prover by performing folding directly in the value domain instead of the coefficient domain.

Technical details:

  • For a polynomial P(x) = sum_{i<r} x^i * P_i(x^r), we compute sum_{i<r} beta^i * P_i(x) directly in the value domain
  • This is mathematically equivalent to the original folding in coefficient domain
  • While we still need one final IFFT transformation for compatibility with the rest of the proof system, we avoid intermediate FFT transformations
  • The optimization reduces the number of field operations needed for folding

The change maintains the same mathematical properties while making the implementation more efficient.

Changes:

  • Removed coefficient domain folding
  • Implemented direct value domain folding with detailed documentation
  • Added explanatory comments for better code maintainability

The optimization addresses the TODO comment in the original code that suggested this improvement.

crStiv avatar Jan 24 '25 22:01 crStiv