Batch Prove Convolution Sumchecks

[Zyouell]

Overview

In the code to be added by PR #105 we make reductions in the size of the commitment to the weights filter. This is achieved by performing an extra Sumcheck to prove the weights have been FFTed correctly. This Sumcheck could be batched in with the existing FFT Sumcheck on the input as they are both multiplied by the same FFT matrix.

In addition the FFT delegation proofs can be batched together to reduce this to a single invocation of GKR in convolution steps.

Finally the evaluation point and claim for the non-FFTed weights commitment can be computed from the claim the FFT Sumcechk produces about the weights. If the Sumcheck outputs the point point, the real weights have dimension k x k and the padded weights have dimension n x n then the actual evaluation can be calculated as:

let multiplier = point[k..n].iter().chain(point[n+k..].iter()).fold(GoldilocksExt2::ONE, |acc, &p| acc * (GoldilocksExt2::ONE - p)).invert().unwrap();
let real_weights_eval = sumcheck_eval * multiplier;

let weights_claim = Claim { point: [&point[..k], &point[n..n+k]].concat(), eval: real_weights_eval };

Tasks

• Batch the input FFT and weights FFT sumchecks together into one
• Batch all the FFT and iFFT evaluation delegation proofs into a single GKR instance
• Remove partial_evals from the convolution proof and have the verifier reconstruct the real weights evaluation as described above

Definition of Done

All current tests should pass but the number of Sumcheck proofs included in the convolution proof should be roughly half what they are now.