Batch Evaluation
We've officially arrived at the very last step in the protocol. As of this point, thanks to our ring-switching reduction, we have brought the outstanding content we still need to prove down to a list of sum claims pertaining to various polynomials—all defined over the single, huge field , though generally of different numbers of variables.
In this subsection, we describe how to batch-process sum claims of this form. Our technique is an extension of that described in the academic work [DP24]. Indeed, that work only describes the commitment of a single polynomial. To extend that work to the batched setting—and in particular, to handle many polynomials, of unequal sizes—we need to exert some extra effort.
The essential efficiency property will be that we will only need to run FRI once, on a single committed polynomial (namely, that described in our batch commitment procedure).
Subsection Directory
This subsection contains the following pages:
- Review of FRI. Here, we drop a crash course on the FRI protocol [BBHR18], a crucial proximity test for Reed–Solomon codes. We also describe a particular instantiation of that protocol—due to [DP24]—designed to play nicely with the additive NTT.
- Front-Loaded Sumcheck. While batching sumchecks on equally-sized polynomials is standard, things get trickier when the polynomials have unequal numbers of variables. Here, we describe our protocol for this sort of thing, which we call the front-loaded sumcheck.
- Evaluating Piecewise Multilinears. Here, we continue our treatment of unequally-sized polynomials. While piecewise multilinears all of whose pieces are the same size are straightforward to deal with, things get much more interesting when the constituent "pieces" are unequally sized.
- The Procedure. Here, we describe our main evaluation procedure, which combines a "front-loaded sumcheck" with FRI folding.