Struct CommonProversState

pub struct CommonProversState<MultilinearId, PW, M, Backend>
where
    MultilinearId: Hash + Eq + Sync,
    PW: PackedField,
    M: MultilinearPoly<PW> + Send + Sync,
    Backend: ComputationBackend,
{ /* private fields */ }

A common provers state for a generalized batched sumcheck protocol.

The family of generalized sumcheck protocols includes regular sumcheck, zerocheck and others. The zerocheck case permits many important optimizations, enumerated in Gruen24. These algorithms are used to prove the interactive multivariate sumcheck protocol in the specific case that the polynomial is a composite of multilinears. This prover state is responsible for updating and evaluating the composed multilinears.

Once initialized, the expected caller behavior is, for a total of n_rounds:

1. At the beginning of each step, call Self::extend with multilinears introduced in this round
2. Then call Self::pre_execute_rounds to perform query expansion, folding, and other bookkeeping.
3. Call Self::calculate_round_coeffs on each multilinear subset with an appropriate evaluator.

We associate with each multilinear a switchover round number, which controls small field optimization and corresponding time/memory tradeoff. In rounds $0, \ldots, switchover-1$ the partial evaluation of a specific multilinear is obtained by doing $2^{n\_vars - round}$ inner products, with total time complexity proportional to the number of polynomial coefficients.

After switchover the inner products are stored in a new MLE in large field, which is halved on each round. There are two tradeoffs at play:

1. Pre-switchover rounds perform Small * Large field multiplications, but do $2^{round}$ as many of them.
2. Pre-switchover rounds require no additional memory, but initial folding allocates a new MLE in a large field that is $2^{switchover}$ times smaller - for example for 1-bit polynomial and 128-bit large field a switchover of 7 would require additional memory identical to the polynomial size.

NB. Note that switchover=0 does not make sense, as first round is never folded. Also note that switchover rounds are numbered relative introduction round.

Implementations

impl<MultilinearId, PW, M, Backend> CommonProversState<MultilinearId, PW, M, Backend>

where MultilinearId: Clone + Hash + Eq + Sync + Debug, PW: PackedField, M: MultilinearPoly<PW> + Sync + Send, Backend: ComputationBackend,

pub fn new( n_vars: usize, switchover_fn: impl Fn(usize) -> usize + 'static, backend: Backend, ) -> Self

pub fn extend( &mut self, multilinears: impl IntoIterator<Item = (MultilinearId, M)>, ) -> Result<(), Error>

pub fn pre_execute_rounds( &mut self, prev_rd_challenge: Option<PW::Scalar>, ) -> Result<(), PolynomialError>

pub fn calculate_round_coeffs<VS>( &self, multilinear_ids: &[MultilinearId], evaluator: impl AbstractSumcheckEvaluator<PW, VertexState = VS>, current_round_sum: PW::Scalar, vertex_state_iterator: impl IndexedParallelIterator<Item = VS>, ) -> Result<Vec<PW::Scalar>, Error>

Compute the sum of the partial polynomial evaluations over the hypercube.