FRI folding twiddle factor warning + naive sumcheck polynomial evaluation

[jiayaoqijia]

Summary

Two related performance issues: (1) reorder_and_dft checks twiddle precomputation and logs a warning but continues execution, adding overhead from on-the-fly twiddle generation, and (2) sumcheck prover uses O(n^2) polynomial evaluation instead of FFT-based evaluation.

Severity

MEDIUM -- Combined ~3x slowdown over a typical WHIR proof.

Location

FRI twiddle factors:

• crates/whir/src/utils.rs:81-83 -- if dft.max_n_twiddles() < dft_size { tracing::warn!(...) } warns but continues execution

Sumcheck evaluation:

• crates/backend/sumcheck/src/prove.rs -- ProductComputation does not use FFT-based evaluation for the round polynomial; evaluates at 3 points per round using O(n) scalar work per point without NTT acceleration

Impact

FRI: ~30% overhead per FRI folding round from on-the-fly twiddle computation.

Sumcheck: ~2x slowdown for polynomials with 2^20+ variables compared to production STARK provers.

Suggested Fix

FRI: Auto-precompute twiddles when first needed, or promote the warning to an error to ensure callers properly initialize.

Sumcheck: For n > 2^16, use NTT-based multipoint evaluation to compute the round polynomial at {0, 1, 2}.

References

• Full audit: https://github.com/jiayaoqijia/eth2030/blob/master/docs/plans/lean-vm-audit.md
• Findings: F-10, F-12