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
Summary
Two related performance issues: (1)
reorder_and_dftchecks 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 executionSumcheck evaluation:
crates/backend/sumcheck/src/prove.rs--ProductComputationdoes not use FFT-based evaluation for the round polynomial; evaluates at 3 points per round using O(n) scalar work per point without NTT accelerationImpact
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