Skip to main content

binius_prover/protocols/intmul/
selector_mle.rs

1// Copyright 2023-2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::iter;
5
6use binius_alloc::Allocator;
7use binius_core::word::Word;
8use binius_field::{BinaryField, Field, PackedField, WideMul};
9use binius_ip::sumcheck::RoundCoeffs;
10use binius_ip_prover::sumcheck::{
11	common::SumcheckProver, eq_tracker::ChunkedEqTracker, round_evals::RoundEvals,
12	round_state::RoundState,
13};
14use binius_math::{FieldBuffer, FieldVec, multilinear::fold::fold_highest_var_inplace};
15use binius_utils::rayon::prelude::*;
16use itertools::izip;
17
18use super::switchover::BinarySwitchover;
19
20pub struct Claim<F: Field> {
21	pub point: Vec<F>,
22	pub value: F,
23}
24
25/// A [`SumcheckProver`] implementation that proves an mlecheck over many compositions of the
26/// form `selected * selector + (1 - selector)`, where `selected` is the shared large field
27/// multilinear and `selector` is one of the `Word::BITS` one-bit multilinears of a word list.
28/// Unlike other multi mlecheck provers however the evaluation point is _not_ shared but is
29/// specified per selector.
30///
31/// Selector `b` is the multilinear whose `i`-th value is bit `b` of word `i`. The bits stay packed
32/// in words until `BinarySwitchover` folds them, which keeps the selectors' memory at the size of
33/// `selected`. The need to expand the equality indicator for each selector still results in some
34/// blowup.
35pub struct SelectorMlecheckProver<'alloc, P: PackedField, A: Allocator> {
36	last_coeffs_or_sums: RoundState<Vec<RoundCoeffs<P::Scalar>>, Vec<P::Scalar>>,
37	selected: FieldVec<P, A>,
38	eq_trackers: Vec<ChunkedEqTracker<P>>,
39	weights: Vec<P::Scalar>,
40	switchover: BinarySwitchover<'alloc, P, A>,
41}
42
43impl<'alloc, F: BinaryField, P: PackedField<Scalar = F>, A: Allocator>
44	SelectorMlecheckProver<'alloc, P, A>
45{
46	/// Constructs a prover, given `selected` being the shared large field multilinear, individual
47	/// `claims` per selector, `words` whose bits are the selectors (missing words read as zero),
48	/// and `weights` to combine the per-selector round polynomials into one (one weight per claim).
49	///
50	/// The prover exposes a single claim — the `weights`-combination `Σ_i weights[i] · C_i` of the
51	/// per-selector claims. Supplying the equality-indicator tensor `eq_k(γ, ·)` as the weights
52	/// batches the claims with `eq_k(γ, i)`.
53	pub fn new(
54		alloc: &'alloc A,
55		selected: FieldVec<P, A>,
56		claims: Vec<Claim<F>>,
57		words: &[Word],
58		weights: Vec<F>,
59	) -> Self {
60		let n_vars = selected.log_len();
61
62		assert_eq!(claims.len(), Word::BITS, "one claim per selector");
63
64		assert!(
65			claims.iter().all(|claim| claim.point.len() == n_vars),
66			"multilinears must have equal number of variables"
67		);
68
69		assert_eq!(
70			weights.len(),
71			claims.len(),
72			"number of weights must match the number of claims"
73		);
74
75		assert!(
76			words.len() <= selected.len(),
77			"words must not outnumber the selected multilinear's values"
78		);
79
80		const MAX_CHUNK_VARS: usize = 8;
81		let (eq_trackers, sums) = claims
82			.into_par_iter()
83			.map(|Claim { point, value }| (ChunkedEqTracker::new(MAX_CHUNK_VARS, &point), value))
84			.collect::<(Vec<_>, Vec<_>)>();
85
86		let switchover = BinarySwitchover::new(alloc, words, n_vars);
87		let last_coeffs_or_sums = RoundState::Claim(sums);
88
89		Self {
90			last_coeffs_or_sums,
91			selected,
92			eq_trackers,
93			weights,
94			switchover,
95		}
96	}
97}
98
99impl<F, P, A> SumcheckProver<F> for SelectorMlecheckProver<'_, P, A>
100where
101	F: BinaryField,
102	P: PackedField<Scalar = F>,
103	A: Allocator,
104{
105	fn n_vars(&self) -> usize {
106		self.selected.log_len()
107	}
108
109	fn execute(&mut self) -> Vec<RoundCoeffs<F>> {
110		let sums = self.last_coeffs_or_sums.claim();
111
112		assert!(self.n_vars() > 0);
113
114		// Perform chunked summation: for every row, evaluate all compositions and add up
115		// results to an array of round evals accumulators. Alternative would be to sum each
116		// composition on its own pass, but that would require reading the entirety of eq field
117		// buffer on each pass, which will evict the latter from the cache. By doing chunked
118		// compute, we reasonably hope that eq chunk always stays in L1 cache. We can also
119		// leverage the outer product representation of the eq indicator.
120		//
121		// We also do switchover there, which by definition requires small scratchpads to hold
122		// large field partial evaluations of the transparent multilinears.
123		let chunk_vars = self
124			.eq_trackers
125			.first()
126			.map(|eq_tracker| eq_tracker.chunk().log_len())
127			.unwrap_or_default();
128		let chunk_count = 1 << (self.n_vars() - 1 - chunk_vars);
129
130		// The fold below reads both halves concurrently from many rayon tasks.
131		// Borrowed halves cross that boundary for any backing store the buffer is built on.
132		let (selected_0, selected_1) = self.selected.split_half();
133		let selectors = self.switchover.selectors();
134		let is_binary = selectors.is_binary();
135
136		let packed_prime_evals = (0..chunk_count)
137			.into_par_iter()
138			.fold(
139				|| {
140					let binary_chunk = FieldBuffer::<P>::zeros(chunk_vars);
141					let masks = [(); 2].map(|_| {
142						(0..binary_chunk.as_ref().len())
143							.map(|_| P::make_mask(iter::empty()))
144							.collect::<Vec<_>>()
145					});
146					(
147						vec![RoundEvals::<P, 2>::default(); sums.len()],
148						binary_chunk.clone(),
149						binary_chunk,
150						masks,
151					)
152				},
153				|(mut packed_prime_evals, mut binary_chunk_0, mut binary_chunk_1, mut masks),
154				 chunk_index| {
155					let selected_0_chunk = selected_0.chunk(chunk_vars, chunk_index);
156					let selected_1_chunk = selected_1.chunk(chunk_vars, chunk_index);
157
158					for (selector, (round_evals, eq_tracker)) in
159						izip!(&mut packed_prime_evals, &self.eq_trackers).enumerate()
160					{
161						let eq_chunk = eq_tracker.chunk();
162						let eq_suffix_eval = eq_tracker.suffix().get(chunk_index);
163
164						// Accumulate `eq_i * composition` in unreduced (wide) form and reduce once
165						// at the end of the chunk. Only the final multiply by `eq_i` is widened;
166						// the `composition` product is reduced as usual because it feeds into that
167						// widening multiply.
168						let mut wide_y_1 = <P as WideMul>::Output::default();
169						let mut wide_y_inf = <P as WideMul>::Output::default();
170						let mut accumulate = |eq_i, y_1_prod, y_inf_prod| {
171							wide_y_1 += P::wide_mul(eq_i, y_1_prod);
172							wide_y_inf += P::wide_mul(eq_i, y_inf_prod);
173						};
174						if is_binary {
175							// Every selector value is a bit, so the composition products are
176							// lane selects.
177							let [masks_1, masks_inf] = &mut masks;
178							selectors.fill_bit_masks(
179								selector,
180								chunk_vars,
181								chunk_index,
182								[masks_1, masks_inf],
183							);
184							for (&eq_i, &selected_0_i, &selected_1_i, mask_1, mask_inf) in izip!(
185								eq_chunk.as_ref(),
186								selected_0_chunk.as_ref(),
187								selected_1_chunk.as_ref(),
188								&masks[0],
189								&masks[1],
190							) {
191								// @one: selected if the selector is set, else 1
192								// @inf: selected_inf if the selector halves differ, else 0
193								let y_1_prod = (selected_1_i + P::one()).select(mask_1) + P::one();
194								let y_inf_prod = (selected_0_i + selected_1_i).select(mask_inf);
195								accumulate(eq_i, y_1_prod, y_inf_prod);
196							}
197						} else {
198							selectors.fill_halves(
199								selector,
200								chunk_vars,
201								chunk_index,
202								[binary_chunk_0.as_mut_view(), binary_chunk_1.as_mut_view()],
203							);
204							for (
205								&eq_i,
206								&selected_0_i,
207								&selected_1_i,
208								&selector_0_i,
209								&selector_1_i,
210							) in izip!(
211								eq_chunk.as_ref(),
212								selected_0_chunk.as_ref(),
213								selected_1_chunk.as_ref(),
214								binary_chunk_0.as_ref(),
215								binary_chunk_1.as_ref(),
216							) {
217								let selected_inf_i = selected_0_i + selected_1_i;
218								let selector_inf_i = selector_0_i + selector_1_i;
219
220								// selected * selector + (1 - selector)
221								// @one: selector * (selected - 1) + 1
222								// @inf: selector * selected (note that lower degree terms are
223								// dropped)
224								let y_1_prod = selector_1_i * (selected_1_i - P::one()) + P::one();
225								let y_inf_prod = selector_inf_i * selected_inf_i;
226								accumulate(eq_i, y_1_prod, y_inf_prod);
227							}
228						}
229						let chunk_round_evals = RoundEvals([wide_y_1, wide_y_inf]).reduce::<P>();
230
231						// Apply the common factor from the outer product representation of the eq
232						// ind
233						*round_evals += &(chunk_round_evals * eq_suffix_eval);
234					}
235
236					(packed_prime_evals, binary_chunk_0, binary_chunk_1, masks)
237				},
238			)
239			.map(|(evals, ..)| evals)
240			// A merge seeded with a partial that already exists never touches a buffer of zeros.
241			// An identity would allocate and zero one accumulator per merge, then add all of it.
242			.reduce_with(|lhs, rhs| izip!(lhs, rhs).map(|(l, r)| l + &r).collect())
243			// An empty hypercube yields no partials at all, and its round evals are zero.
244			.unwrap_or_else(|| vec![RoundEvals::<P, 2>::default(); sums.len()]);
245
246		// This prover has multiple evaluation points and cannot implement MleCheckProver.
247		let (prime_coeffs, round_coeffs) = izip!(&self.eq_trackers, sums, packed_prime_evals)
248			.map(|(eq_tracker, &sum, packed_prime_evals)| {
249				eq_tracker.interpolate2(sum, packed_prime_evals.sum_scalars(self.n_vars() - 1))
250			})
251			.unzip::<_, _, Vec<_>, Vec<_>>();
252
253		self.last_coeffs_or_sums = RoundState::Coeffs(prime_coeffs);
254
255		// Combine the per-claim round polynomials into the single weighted round polynomial
256		// `Σ_i weights[i] · R_i`.
257		let combined = izip!(round_coeffs, &self.weights)
258			.map(|(coeffs, &w)| coeffs * w)
259			.sum();
260		vec![combined]
261	}
262
263	fn fold(&mut self, challenge: F) {
264		let prime_coeffs = self.last_coeffs_or_sums.coeffs();
265
266		assert!(self.n_vars() > 0);
267
268		let sums = prime_coeffs
269			.iter()
270			.map(|coeffs| coeffs.evaluate(&challenge))
271			.collect();
272
273		self.eq_trackers
274			.par_iter_mut()
275			.for_each(|eq_tracker| eq_tracker.fold(challenge));
276
277		self.switchover.fold(challenge);
278		fold_highest_var_inplace(&mut self.selected, challenge);
279
280		self.last_coeffs_or_sums = RoundState::Claim(sums);
281	}
282
283	fn finish(self) -> Vec<F> {
284		assert_eq!(self.n_vars(), 0, "finish called out of order; sumcheck rounds remain");
285
286		let mut multilinear_evals = self.switchover.finish();
287		multilinear_evals.push(self.selected.get(0));
288		multilinear_evals
289	}
290}
291
292#[cfg(test)]
293mod tests {
294	use std::iter::repeat_with;
295
296	use binius_alloc::GlobalAllocator;
297	use binius_field::FieldOps;
298	use binius_ip::sumcheck::verify;
299	use binius_ip_prover::sumcheck::prove_single;
300	use binius_math::{
301		multilinear::{eq::eq_ind, evaluate::evaluate},
302		test_utils::{Packed128b, random_scalars},
303	};
304	use binius_transcript::{ProverTranscript, fiat_shamir::HasherChallenger};
305	use itertools::Itertools;
306	use rand::prelude::*;
307	use rstest::rstest;
308
309	use super::*;
310
311	type P = Packed128b;
312	type F = <P as FieldOps>::Scalar;
313	type StdChallenger = HasherChallenger<sha2::Sha256>;
314
315	// Prove/verify roundtrip: drive the prover through a transcript, verify with the generic
316	// sumcheck verifier, and reconstruct the reduced claim from the returned multilinear
317	// evaluations. This mirrors the verifier's selector-sumcheck check (`verify_phase_3` in
318	// `binius-verifier`'s intmul protocol), which recombines per-selector terms
319	// `(selector·(selected − 1) + 1)·eq(point_i, r)` weighted by an equality tensor.
320	//
321	// The word list stops short of `2^n_vars`, so the missing words read as zero.
322	#[rstest]
323	#[case::padded_single_block(3)]
324	#[case::exactly_one_block(6)]
325	#[case::several_blocks(9)]
326	fn test_selector_mlecheck_prove_verify(#[case] n_vars: usize) {
327		let mut rng = StdRng::seed_from_u64(0);
328
329		let selector_count = Word::BITS;
330
331		let words = repeat_with(|| Word::from_u64(rng.random()))
332			.take((1 << n_vars) - 3)
333			.collect_vec();
334
335		let selected_scalars = random_scalars::<F>(&mut rng, 1 << n_vars);
336		let selected = FieldBuffer::<P>::from_values(&selected_scalars);
337
338		// The 1-bit selector columns, extracted from the words.
339		let selector_columns = (0..selector_count)
340			.map(|b| {
341				(0..1 << n_vars)
342					.map(|i| {
343						let bit = words.get(i).is_some_and(|word| word.extract_bit(b));
344						if bit { F::ONE } else { F::ZERO }
345					})
346					.collect_vec()
347			})
348			.collect_vec();
349
350		// One claim per selector: the composition `selected * selector + (1 - selector)` evaluated
351		// at an independent random point.
352		let points = repeat_with(|| random_scalars::<F>(&mut rng, n_vars))
353			.take(selector_count)
354			.collect_vec();
355		let claims = izip!(&selector_columns, &points)
356			.map(|(selector_scalars, point)| {
357				let masked = izip!(&selected_scalars, selector_scalars)
358					.map(|(&selected, &selector)| selected * selector + (F::ONE - selector))
359					.collect_vec();
360				let value = evaluate(&FieldBuffer::<P>::from_values(&masked), point);
361				Claim {
362					point: point.clone(),
363					value,
364				}
365			})
366			.collect_vec();
367
368		let weights = random_scalars::<F>(&mut rng, selector_count);
369
370		// The prover reduces the per-selector claims to a single weighted sumcheck claim.
371		let claim: F = izip!(&claims, &weights).map(|(c, &w)| c.value * w).sum();
372
373		let prover = SelectorMlecheckProver::new(
374			&GlobalAllocator,
375			FieldBuffer::from_view_in(&GlobalAllocator, selected.as_view()),
376			claims,
377			&words,
378			weights.clone(),
379		);
380
381		// Run the prover through the transcript and append the final multilinear evaluations.
382		let mut prover_transcript = ProverTranscript::new(StdChallenger::default());
383		let output = prove_single(prover, &mut prover_transcript);
384		prover_transcript
385			.message()
386			.write_slice(&output.multilinear_evals);
387
388		// Verify against the generic sumcheck verifier. The composition has degree 3: a degree-2
389		// product (`selected * selector`) times the equality indicator.
390		let mut verifier_transcript = prover_transcript.into_verifier();
391		let sumcheck_output = verify(n_vars, 3, claim, &mut verifier_transcript).unwrap();
392
393		assert_eq!(
394			output.challenges, sumcheck_output.challenges,
395			"prover and verifier challenges must match"
396		);
397
398		// The prover binds variables high-to-low; `evaluate` and `eq_ind` expect low-to-high.
399		let mut reduced_point = sumcheck_output.challenges.clone();
400		reduced_point.reverse();
401
402		// `finish()` returns `[selector_0(r), .., selector_{k-1}(r), selected(r)]`.
403		let multilinear_evals: Vec<F> = verifier_transcript
404			.message()
405			.read_vec(selector_count + 1)
406			.unwrap();
407		let (selector_evals, selected_eval) = multilinear_evals.split_at(selector_count);
408		let selected_eval = selected_eval[0];
409
410		// The claimed evaluations must match direct evaluation of the multilinears at the challenge
411		// point.
412		assert_eq!(selected_eval, evaluate(&selected, &reduced_point), "selected evaluation");
413		for (i, (&selector_eval, selector_scalars)) in
414			izip!(selector_evals, &selector_columns).enumerate()
415		{
416			assert_eq!(
417				selector_eval,
418				evaluate(&FieldBuffer::<P>::from_values(selector_scalars), &reduced_point),
419				"selector {i} evaluation"
420			);
421		}
422
423		// Reconstruct the reduced sumcheck claim from the multilinear evaluations:
424		// `Σ_i weights[i] · (selected(r)·selector_i(r) + (1 − selector_i(r))) · eq(point_i, r)`.
425		let expected_eval: F = izip!(selector_evals, &points, &weights)
426			.map(|(&selector_eval, point, &weight)| {
427				let composition = selected_eval * selector_eval + (F::ONE - selector_eval);
428				weight * composition * eq_ind(point, &reduced_point)
429			})
430			.sum();
431		assert_eq!(
432			expected_eval, sumcheck_output.eval,
433			"reduced sumcheck claim must match the composition evaluated at the challenge point"
434		);
435	}
436}