binius_ip_prover/sumcheck/
mle_to_sumcheck.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use binius_field::{Field, PackedField, WideMul};
5use binius_ip::sumcheck::RoundCoeffs;
6use binius_math::multilinear::eq::eq_one_var;
7
8use crate::sumcheck::{
9	common::{MleCheckProver, SumcheckProver},
10	mle_store::{EqId, EvaluationChunk, RoundContext},
11	round_evaluator::{MleCheckRoundEvaluator, SumcheckRoundEvaluator},
12};
13
14/// Adaptor that exposes a `SumcheckProver` interface for an internal `MleCheckProver`.
15///
16/// This struct implements the technique from [Gruen24] to convert an MLE-check protocol
17/// into a standard sumcheck protocol. The key insight is that the MLE-check claim
18/// $\sum_{v \in \{0,1\}^n} F(v) \cdot \text{eq}(v, z) = s$ can be rewritten as a sumcheck
19/// claim by multiplying in the equality polynomial term-by-term during the protocol execution.
20///
21/// In each round, the adaptor multiplies the round polynomials from the inner MLE-check
22/// prover by a linear polynomial term $(X - \alpha)$ where $\alpha$ is the corresponding
23/// coordinate of the evaluation point. This effectively transforms the MLE-check round
24/// polynomial into a sumcheck round polynomial that includes the equality check.
25///
26/// The `eq_prefix_eval` field accumulates the product of all previously factored equality
27/// terms, ensuring the round polynomials maintain the correct scaling throughout the protocol.
28///
29/// [Gruen24]: <https://eprint.iacr.org/2024/108>
30#[derive(Debug, Clone)]
31pub struct MleToSumCheckDecorator<F: Field, InnerProver> {
32	mlecheck_prover: InnerProver,
33	eq_prefix_eval: F,
34}
35
36impl<F: Field, InnerProver: MleCheckProver<F>> MleToSumCheckDecorator<F, InnerProver> {
37	pub const fn new(mlecheck_prover: InnerProver) -> Self {
38		Self {
39			mlecheck_prover,
40			eq_prefix_eval: F::ONE,
41		}
42	}
43}
44
45impl<F: Field, InnerProver: MleCheckProver<F>> SumcheckProver<F>
46	for MleToSumCheckDecorator<F, InnerProver>
47{
48	fn n_vars(&self) -> usize {
49		self.mlecheck_prover.n_vars()
50	}
51
52	fn execute(&mut self) -> Vec<RoundCoeffs<F>> {
53		let round_coeffs_multi = self.mlecheck_prover.execute();
54
55		// Multiply the round polynomials from the inner MLE-check prover by (X - α).
56		let alpha = self.mlecheck_prover.eval_point()[self.n_vars() - 1];
57		round_coeffs_multi
58			.into_iter()
59			.map(|round_coeffs| round_coeffs.mul_by_eq(alpha) * self.eq_prefix_eval)
60			.collect()
61	}
62
63	fn fold(&mut self, challenge: F) {
64		assert_ne!(self.n_vars(), 0, "fold called out of order; expected finish");
65
66		let alpha = self.mlecheck_prover.eval_point()[self.n_vars() - 1];
67		self.eq_prefix_eval *= eq_one_var(challenge, alpha);
68
69		self.mlecheck_prover.fold(challenge);
70	}
71
72	fn finish(self) -> Vec<F> {
73		self.mlecheck_prover.finish()
74	}
75}
76
77/// Adaptor that turns an [`MleCheckRoundEvaluator`] into a [`SumcheckRoundEvaluator`].
78///
79/// This is the evaluator-level mirror of [`MleToSumCheckDecorator`], applying the same [Gruen24]
80/// technique: each round, the inner evaluator's prime round polynomials are multiplied by the
81/// linear equality term in the bound coordinate and by the accumulated equality prefix. It lets
82/// eq-weighted and plain claims live in one evaluator group behind a single
83/// [`SharedSumcheckProver`].
84///
85/// Unlike a bare [`MleCheckRoundEvaluator`], whose driving [`SharedMleCheckProver`] owns the eq
86/// tracker, this wrapper runs under a [`SharedSumcheckProver`] that knows nothing of eq indicators.
87/// So the wrapper itself holds the [`EqId`] of the shared evaluation point's eq tracker, and
88/// supplies the round's eq chunk to [`MleCheckRoundEvaluator::accumulate`] and its alpha and
89/// equality prefix to [`MleCheckRoundEvaluator::interpolate`] — all read from that tracker, which
90/// the store folds in lockstep, so the wrapper keeps no copy of the point and no equality
91/// bookkeeping of its own.
92///
93/// [`SharedSumcheckProver`]: super::round_evaluator::SharedSumcheckProver
94/// [`SharedMleCheckProver`]: super::round_evaluator::SharedMleCheckProver
95/// [Gruen24]: <https://eprint.iacr.org/2024/108>
96pub struct MleToSumCheckEvaluator<Inner> {
97	inner: Inner,
98	// The shared eq tracker for the inner MLE-check evaluation point; the store maintains its
99	// current alpha and equality prefix.
100	eq_tracker: EqId,
101}
102
103impl<Inner> MleToSumCheckEvaluator<Inner> {
104	/// Wraps an MLE-check evaluator whose claims share the point of eq tracker `eq_tracker`.
105	pub const fn new(inner: Inner, eq_tracker: EqId) -> Self {
106		Self { inner, eq_tracker }
107	}
108}
109
110impl<F, P, Inner> SumcheckRoundEvaluator<F, P> for MleToSumCheckEvaluator<Inner>
111where
112	F: Field,
113	P: PackedField<Scalar = F>,
114	Inner: MleCheckRoundEvaluator<F, P>,
115{
116	fn degree(&self) -> usize {
117		// The eq factor multiplies the emitted round polynomial, not the accumulator: the wide
118		// slots still hold the inner evaluator's prime-polynomial evaluations.
119		self.inner.degree()
120	}
121
122	fn accumulate(&self, chunk: &EvaluationChunk<'_, P>, accum: &mut [<P as WideMul>::Output]) {
123		self.inner
124			.accumulate(chunk, chunk.eq(self.eq_tracker).as_view(), accum);
125	}
126
127	fn interpolate(&self, ctx: &RoundContext<'_, P>, accum: &[P], claim: F) -> RoundCoeffs<F> {
128		// `claim` is the sumcheck round claim: the inner MLE-check claim `m` scaled by the
129		// accumulated equality prefix. Recover `m` for the inner evaluator by dividing the prefix
130		// back out. (`invert_or_zero` mirrors the interpolation routines; the prefix is a product
131		// of non-degenerate equality factors for honest challenges.)
132		//
133		// alpha and the equality prefix are read from the shared eq tracker (the store has not yet
134		// folded this round, so the tracker is at the current round's alpha and prefix).
135		let eq_prefix = ctx.eq_prefix(self.eq_tracker);
136		let alpha = ctx.eq_alpha(self.eq_tracker);
137		let inner_claim = claim * eq_prefix.invert_or_zero();
138		// The inner evaluator interpolates its prime polynomial from the same reduced slots.
139		let round_coeffs = self.inner.interpolate(ctx, accum, inner_claim, alpha);
140
141		// Multiply the inner MLE-check round polynomial by (X - α) and the equality prefix.
142		round_coeffs.mul_by_eq(alpha) * eq_prefix
143	}
144}
binius_ip_prover/sumcheck/mle_to_sumcheck.rs

binius_ip_prover/sumcheck/
mle_to_sumcheck.rs
