1use 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
25pub 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 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 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 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 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 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 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 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 *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 .reduce_with(|lhs, rhs| izip!(lhs, rhs).map(|(l, r)| l + &r).collect())
243 .unwrap_or_else(|| vec![RoundEvals::<P, 2>::default(); sums.len()]);
245
246 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 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 #[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 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 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 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 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 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 let mut reduced_point = sumcheck_output.challenges.clone();
400 reduced_point.reverse();
401
402 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 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 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}