Skip to main content

binius_ip_prover/sumcheck/
zk_mlecheck.rs

1// Copyright 2026 The Binius Developers
2
3//! Prover for the Libra mask polynomial in ZK MLE-check protocols.
4//!
5//! The Libra ZK-sumcheck protocol uses a masking polynomial g(X_0, ..., X_{n-1}) of the form:
6//! g = sum_{i=0}^{n-1} g_i(X_i)
7//!
8//! where each g_i(X) is a univariate polynomial of configurable degree. This separable structure
9//! allows efficient computation of round polynomials without iterating over the full hypercube.
10
11use std::{iter, ops::Deref};
12
13use binius_field::{Field, PackedField};
14use binius_ip::{mlecheck, sumcheck::RoundCoeffs};
15use binius_math::line::extrapolate_line;
16
17use super::{common::MleCheckProver, round_state::RoundState};
18use crate::{channel::IPProverChannel, libra::Mask};
19
20/// Output of the ZK MLE-check proving protocol.
21#[derive(Debug, Clone)]
22pub struct ProveZKOutput<F: Field> {
23	/// Evaluations of the main multilinear polynomials at the challenge point.
24	pub multilinear_evals: Vec<F>,
25	/// Evaluation of the mask polynomial at the challenge point.
26	pub mask_eval: F,
27	/// Verifier challenges for each round of the sumcheck protocol.
28	pub challenges: Vec<F>,
29}
30
31/// Prover for the Libra mask polynomial in ZK MLE-check.
32///
33/// The mask polynomial has the separable form $g(X_0, ..., X_{n-1}) = sum_{i} g_i(X_i)$,
34/// where each $g_i$ is a univariate polynomial of configurable degree.
35///
36/// This structure allows efficient round polynomial computation in O(degree) time per round.
37pub struct MleCheckMaskProver<F: Field, P: PackedField<Scalar = F>, Data: Deref<Target = [P]>> {
38	/// The mask polynomial (owned)
39	mask: Mask<P, Data>,
40	/// The evaluation point z (in high-to-low variable order)
41	eval_point: Vec<F>,
42	/// Number of variables remaining to process
43	n_vars_remaining: usize,
44	/// Accumulated sum of g_j(r_j) for already-folded variables
45	prefix_sum: F,
46	/// Precomputed (1-z_j)*g_j(0) + z_j*g_j(1) for each variable
47	suffix_sums: Vec<F>,
48	/// State: either last round coefficients (after execute) or current claim (after fold)
49	last_coeffs_or_claim: RoundState<RoundCoeffs<F>, F>,
50}
51
52impl<F: Field, P: PackedField<Scalar = F>, Data: Deref<Target = [P]>>
53	MleCheckMaskProver<F, P, Data>
54{
55	/// Creates a new prover for the Libra mask polynomial.
56	///
57	/// # Arguments
58	///
59	/// * `mask` - The mask polynomial (takes ownership).
60	/// * `eval_point` - The evaluation point z for the MLE-check claim, in high-to-low order.
61	/// * `eval_claim` - The claimed value of the MLE of g at the evaluation point.
62	///
63	/// # Panics
64	///
65	/// Panics if `mask.n_vars() != eval_point.len()`.
66	pub fn new(mask: Mask<P, Data>, eval_point: Vec<F>, eval_claim: F) -> Self {
67		assert_eq!(mask.n_vars(), eval_point.len(), "mask n_vars must match eval_point length");
68
69		let n_vars = eval_point.len();
70
71		// Precompute suffix_sums[j] = (1-z_j)*g_j(0) + z_j*g_j(1)
72		// That is the line through g_j(0) and g_j(1), read at z_j.
73		let suffix_sums: Vec<F> = iter::zip(0..n_vars, &eval_point)
74			.map(|(i, &z_j)| {
75				let g_at_0 = mask.get_coeff(i, 0);
76				let g_at_1 = mask.evaluate_univariate(i, F::ONE);
77				extrapolate_line(g_at_0, g_at_1, z_j)
78			})
79			.collect();
80
81		Self {
82			mask,
83			eval_point,
84			n_vars_remaining: n_vars,
85			prefix_sum: F::ZERO,
86			suffix_sums,
87			last_coeffs_or_claim: RoundState::Claim(eval_claim),
88		}
89	}
90
91	/// Returns the index of the current variable being processed.
92	/// Processing is high-to-low, so we start at n_vars-1 and decrease.
93	const fn current_var_index(&self) -> usize {
94		self.n_vars_remaining - 1
95	}
96}
97
98impl<F: Field, P: PackedField<Scalar = F>, Data: Deref<Target = [P]>> MleCheckProver<F>
99	for MleCheckMaskProver<F, P, Data>
100{
101	fn n_vars(&self) -> usize {
102		self.n_vars_remaining
103	}
104
105	fn execute(&mut self) -> Vec<RoundCoeffs<F>> {
106		self.last_coeffs_or_claim.claim();
107
108		assert_ne!(self.n_vars_remaining, 0, "execute called out of order; expected finish");
109
110		let var_idx = self.current_var_index();
111
112		// Compute suffix sum for variables that haven't been processed yet (indices 0 to var_idx-1)
113		// Since we process high-to-low (n-1, n-2, ..., 0), the suffix is the lower-indexed
114		// variables
115		let suffix_sum: F = self.suffix_sums[..var_idx].iter().copied().sum();
116
117		// Compute the constant offset: prefix_sum + suffix_sum
118		let constant_offset = self.prefix_sum + suffix_sum;
119
120		// Build the round polynomial R(X) = g_i(X) + constant_offset
121		// g_i(X) = sum_{k=0}^{d} a_{i,k} * X^k
122		// So coefficients are: [a_0 + offset, a_1, a_2, ..., a_d]
123		let mut round_coeffs_vec: Vec<F> = self.mask.coeffs_for_var(var_idx).collect();
124		if round_coeffs_vec.is_empty() {
125			round_coeffs_vec.push(constant_offset);
126		} else {
127			round_coeffs_vec[0] += constant_offset;
128		}
129
130		let round_coeffs = RoundCoeffs(round_coeffs_vec);
131		self.last_coeffs_or_claim = RoundState::Coeffs(round_coeffs.clone());
132		vec![round_coeffs]
133	}
134
135	fn fold(&mut self, challenge: F) {
136		let coeffs = self.last_coeffs_or_claim.coeffs();
137
138		// Evaluate round polynomial at challenge to get new claim
139		let new_claim = coeffs.evaluate(&challenge);
140
141		let var_idx = self.current_var_index();
142
143		// Update prefix_sum: add g_i(r_i)
144		self.prefix_sum += self.mask.evaluate_univariate(var_idx, challenge);
145
146		self.n_vars_remaining -= 1;
147		self.last_coeffs_or_claim = RoundState::Claim(new_claim);
148	}
149
150	fn finish(self) -> Vec<F> {
151		assert_eq!(self.n_vars_remaining, 0, "finish called out of order; sumcheck rounds remain");
152
153		// Final evaluation of g at the challenge point is prefix_sum
154		// (since g(r_0, ..., r_{n-1}) = sum_i g_i(r_i))
155		vec![self.prefix_sum]
156	}
157
158	fn eval_point(&self) -> &[F] {
159		// Return remaining coordinates (high-to-low means we return the first n_vars_remaining
160		// elements)
161		&self.eval_point[..self.n_vars_remaining]
162	}
163}
164
165/// Executes the zero-knowledge MLE-check proving protocol for a single multivariate polynomial.
166///
167/// This function proves a single MLE-check while batching with a Libra mask polynomial
168/// to achieve zero-knowledge. The mask polynomial has the separable form
169/// $g(X_0, \ldots, X_{n-1}) = \sum_i g_i(X_i)$ where each $g_i$ is a univariate polynomial.
170///
171/// # Protocol Flow
172///
173/// 1. Compute and write `mask_eval` (MLE of mask polynomial at the evaluation point)
174/// 2. Sample `batch_challenge` and batch evaluation claims
175/// 3. For each round, batch the main and mask round polynomials
176/// 4. Write `mask_eval_out` (mask evaluation at the challenge point)
177///
178/// # Arguments
179///
180/// * `main_prover` - The MLE-check prover for the main polynomial. Must carry exactly one claim.
181/// * `mask` - The mask polynomial.
182/// * `channel` - The channel for sending prover messages and sampling challenges
183///
184/// # Returns
185///
186/// Returns [`ProveZKOutput`] containing the main polynomial's multilinear evaluations
187/// and the round challenges.
188///
189/// # Pre-conditions
190///
191/// * The mask's univariate degree must be at least the degree of the main prover's round
192///   polynomials.
193/// * The two round polynomials are added coefficient by coefficient, so a shorter mask leaves the
194///   high-degree coefficients uncovered and the protocol is no longer hiding.
195///
196/// # Panics
197///
198/// Panics if the main prover emits more than one round polynomial.
199/// Panics if the mask's round polynomial is shorter than the main prover's.
200pub fn prove<F: Field, P: PackedField<Scalar = F>, Data: Deref<Target = [P]>>(
201	mut main_prover: impl MleCheckProver<F>,
202	mask: Mask<P, Data>,
203	channel: &mut impl IPProverChannel<F>,
204) -> ProveZKOutput<F> {
205	let n_vars = main_prover.n_vars();
206	let eval_point = main_prover.eval_point().to_vec();
207
208	// Compute and write mask_eval (MLE of mask polynomial at the evaluation point)
209	let mask_eval = mask.evaluate_mle(&eval_point);
210	channel.send_one(mask_eval);
211
212	// Sample batch challenge and construct mask prover
213	let batch_challenge: F = channel.sample();
214	let batched_mask_eval = batch_challenge * mask_eval;
215	let mut mask_prover = MleCheckMaskProver::new(mask, eval_point, batched_mask_eval);
216
217	let mut challenges = Vec::with_capacity(n_vars);
218
219	for _ in 0..n_vars {
220		// Execute both provers
221		let mut main_round_coeffs_vec = main_prover.execute();
222		assert_eq!(
223			main_round_coeffs_vec.len(),
224			1,
225			"prove requires a main prover with one claim, but it emitted {}",
226			main_round_coeffs_vec.len()
227		);
228		let main_round_coeffs = main_round_coeffs_vec.pop().expect("length checked above");
229
230		let mut mask_round_coeffs_vec = mask_prover.execute();
231		let mask_round_coeffs = mask_round_coeffs_vec
232			.pop()
233			.expect("mask prover has 1 claim");
234
235		// The batching below pads the shorter polynomial with zeros, so any coefficient beyond
236		// the mask's degree would reach the channel exactly as the witness produced it.
237		//
238		//     main   : [a_0, a_1, a_2]
239		//     mask   : [b_0, b_1]      -> padded to [b_0, b_1, 0]
240		//     batched: [a_0 + c*b_0, a_1 + c*b_1, a_2]
241		//                                         ^^^ unmasked
242		assert!(
243			mask_round_coeffs.0.len() >= main_round_coeffs.0.len(),
244			"the mask round polynomial has {} coefficients against the main round polynomial's \
245			 {}, so the excess would be sent unmasked",
246			mask_round_coeffs.0.len(),
247			main_round_coeffs.0.len()
248		);
249
250		// Batch the round coefficients: batched = main + batch_challenge * mask
251		let batched_round_coeffs = main_round_coeffs + &(mask_round_coeffs * batch_challenge);
252
253		// Write truncated coefficients to channel
254		channel.send_many(mlecheck::RoundProof::truncate(batched_round_coeffs).coeffs());
255
256		// Sample challenge and fold both provers
257		let challenge = channel.sample();
258		challenges.push(challenge);
259		main_prover.fold(challenge);
260		mask_prover.fold(challenge);
261	}
262
263	// Finish both provers
264	let main_evals = main_prover.finish();
265	let mask_evals = mask_prover.finish();
266	let mask_eval_out = mask_evals[0];
267
268	// Write final mask evaluation
269	channel.send_one(mask_eval_out);
270
271	ProveZKOutput {
272		multilinear_evals: main_evals,
273		mask_eval: mask_eval_out,
274		challenges,
275	}
276}
277
278#[cfg(test)]
279mod tests {
280	use binius_field::arch::OptimalB128;
281	use binius_ip::{libra::mask_buffer_dimensions, mlecheck};
282	use binius_math::test_utils::{random_field_buffer, random_scalars};
283	use binius_transcript::{ProverTranscript, fiat_shamir::HasherChallenger};
284
285	type StdChallenger = HasherChallenger<sha2::Sha256>;
286	use rand::prelude::*;
287
288	use super::*;
289	use crate::sumcheck::prove_single_mlecheck;
290
291	type B128 = OptimalB128;
292
293	/// Evaluates the mask polynomial g(X) = sum_i g_i(X_i) at a point using the Mask struct.
294	fn evaluate_mask_polynomial<P: PackedField, Data: Deref<Target = [P]>>(
295		mask: &Mask<P, Data>,
296		point: &[P::Scalar],
297	) -> P::Scalar {
298		iter::zip(0..mask.n_vars(), point)
299			.map(|(i, &x)| mask.evaluate_univariate(i, x))
300			.sum()
301	}
302
303	fn test_mask_prover_with_degree(degree: usize) {
304		let n_vars = 6;
305		let mut rng = StdRng::seed_from_u64(0);
306
307		// Generate random mask buffer
308		let (m_n, m_d) = mask_buffer_dimensions(n_vars, degree);
309		let buffer = random_field_buffer::<B128>(&mut rng, m_n + m_d);
310
311		// Generate random evaluation point
312		let eval_point: Vec<B128> = random_scalars(&mut rng, n_vars);
313
314		// Compute the MLE of the mask polynomial at eval_point
315		let mask = Mask::new(n_vars, degree, buffer.as_view());
316		let eval_claim = mask.evaluate_mle(&eval_point);
317
318		// Create the prover (takes ownership of a borrowed mask view)
319		let prover = MleCheckMaskProver::new(mask, eval_point.clone(), eval_claim);
320
321		// Run the proving protocol
322		let mut prover_transcript = ProverTranscript::new(StdChallenger::default());
323		let output = prove_single_mlecheck(prover, &mut prover_transcript);
324
325		// Write the multilinear evaluation to the transcript
326		prover_transcript
327			.message()
328			.write_slice(&output.multilinear_evals);
329
330		// Convert to verifier transcript and run verification
331		let mut verifier_transcript = prover_transcript.into_verifier();
332		let sumcheck_output = mlecheck::verify(
333			&eval_point,
334			degree, // round polynomial degree equals the univariate g_i degree
335			eval_claim,
336			&mut verifier_transcript,
337		)
338		.unwrap();
339
340		// Read the mask evaluation from the transcript
341		let mask_eval_out: B128 = verifier_transcript.message().read().unwrap();
342
343		// Verify the reduced evaluation equals the composition of the evaluations
344		// The mask polynomial is the single "multilinear" here, so its eval should match
345		assert_eq!(mask_eval_out, sumcheck_output.eval);
346
347		// Compute the challenge point (reverse for high-to-low order)
348		let mut challenge_point = sumcheck_output.challenges;
349		challenge_point.reverse();
350
351		// Check that the final evaluation matches direct computation
352		let mask = Mask::new(n_vars, degree, buffer.as_view());
353		let expected_eval = evaluate_mask_polynomial(&mask, &challenge_point);
354		assert_eq!(output.multilinear_evals[0], expected_eval);
355	}
356
357	#[test]
358	fn test_linear_mask() {
359		test_mask_prover_with_degree(1);
360	}
361
362	#[test]
363	fn test_quadratic_mask() {
364		test_mask_prover_with_degree(2);
365	}
366
367	#[test]
368	fn test_cubic_mask() {
369		test_mask_prover_with_degree(3);
370	}
371
372	#[test]
373	fn test_single_variable() {
374		let mut rng = StdRng::seed_from_u64(0);
375
376		// Single variable mask buffer
377		let (m_n, m_d) = mask_buffer_dimensions(1, 2);
378		let buffer = random_field_buffer::<B128>(&mut rng, m_n + m_d);
379
380		let eval_point: Vec<B128> = random_scalars(&mut rng, 1);
381		let mask = Mask::new(1, 2, buffer.as_view());
382		let eval_claim = mask.evaluate_mle(&eval_point);
383
384		let prover = MleCheckMaskProver::new(mask, eval_point.clone(), eval_claim);
385
386		let mut prover_transcript = ProverTranscript::new(StdChallenger::default());
387		let output = prove_single_mlecheck(prover, &mut prover_transcript);
388
389		prover_transcript
390			.message()
391			.write_slice(&output.multilinear_evals);
392
393		let mut verifier_transcript = prover_transcript.into_verifier();
394		let sumcheck_output =
395			mlecheck::verify(&eval_point, 2, eval_claim, &mut verifier_transcript).unwrap();
396
397		let mut challenge_point = sumcheck_output.challenges;
398		challenge_point.reverse();
399
400		let mask = Mask::new(1, 2, buffer.as_view());
401		let expected_eval = evaluate_mask_polynomial(&mask, &challenge_point);
402		assert_eq!(output.multilinear_evals[0], expected_eval);
403	}
404
405	fn test_prove_with_degrees(main_degree: usize, mask_degree: usize) {
406		let n_vars = 6;
407		let mut rng = StdRng::seed_from_u64(0);
408
409		// Generate random main mask buffer (using Mask as a simple MleCheckProver for testing)
410		let (m_n, m_d) = mask_buffer_dimensions(n_vars, main_degree);
411		let main_buffer = random_field_buffer::<B128>(&mut rng, m_n + m_d);
412
413		// Generate random ZK mask buffer
414		let (zk_m_n, zk_m_d) = mask_buffer_dimensions(n_vars, mask_degree);
415		let zk_buffer = random_field_buffer::<B128>(&mut rng, zk_m_n + zk_m_d);
416
417		// Generate random evaluation point
418		let eval_point: Vec<B128> = random_scalars(&mut rng, n_vars);
419
420		// Compute the MLE of the main polynomial at eval_point
421		let main_mask = Mask::new(n_vars, main_degree, main_buffer.as_view());
422		let main_eval_claim = main_mask.evaluate_mle(&eval_point);
423
424		// Create the main prover (using MleCheckMaskProver as a simple MleCheckProver)
425		let main_prover = MleCheckMaskProver::new(main_mask, eval_point.clone(), main_eval_claim);
426
427		// Run the ZK proving protocol
428		let zk_mask = Mask::new(n_vars, mask_degree, zk_buffer.as_view());
429		let mut prover_transcript = ProverTranscript::new(StdChallenger::default());
430		let output = prove(main_prover, zk_mask, &mut prover_transcript);
431
432		// Write the main polynomial evaluation to the transcript
433		prover_transcript
434			.message()
435			.write_slice(&output.multilinear_evals);
436
437		// Convert to verifier transcript and run ZK verification
438		let mut verifier_transcript = prover_transcript.into_verifier();
439		let mlecheck::VerifyZKOutput {
440			eval,
441			mask_eval,
442			challenges,
443		} = mlecheck::verify_zk(
444			&eval_point,
445			main_degree.max(mask_degree), // batched polynomial degree
446			main_eval_claim,
447			&mut verifier_transcript,
448		)
449		.unwrap();
450
451		// Read the main polynomial evaluation from the transcript
452		let main_eval_out: B128 = verifier_transcript.message().read().unwrap();
453
454		// Verify the reduced evaluation matches
455		assert_eq!(main_eval_out, eval);
456
457		// Compute the challenge point (reverse for high-to-low order)
458		let mut challenge_point = challenges;
459		challenge_point.reverse();
460
461		// Check that the final main evaluation matches direct computation
462		let main_mask = Mask::new(n_vars, main_degree, main_buffer.as_view());
463		let expected_main_eval = evaluate_mask_polynomial(&main_mask, &challenge_point);
464		assert_eq!(output.multilinear_evals[0], expected_main_eval);
465
466		// Check that the mask evaluation matches the zk_mask evaluation at the challenge point
467		let zk_mask = Mask::new(n_vars, mask_degree, zk_buffer.as_view());
468		let expected_mask_eval = evaluate_mask_polynomial(&zk_mask, &challenge_point);
469		assert_eq!(mask_eval, expected_mask_eval);
470	}
471
472	#[test]
473	fn test_prove() {
474		// Both round polynomials carry three coefficients, so every one of them is covered.
475		test_prove_with_degrees(2, 2);
476	}
477
478	#[test]
479	fn test_prove_mask_above_main_degree() {
480		// A mask that overshoots is still hiding.
481		//
482		//     main   : [a_0, a_1]
483		//     mask   : [b_0, b_1, b_2]
484		//     batched: [a_0 + c*b_0, a_1 + c*b_1, c*b_2]
485		//
486		// The verifier is told the batched degree, so the proof still checks out.
487		test_prove_with_degrees(1, 2);
488	}
489
490	#[test]
491	#[should_panic(expected = "would be sent unmasked")]
492	fn test_prove_mask_below_main_degree() {
493		// A mask one degree short leaves the top coefficient of every round in the clear.
494		//
495		//     main   : [a_0, a_1, a_2]
496		//     mask   : [b_0, b_1]      -> zero-padded to [b_0, b_1, 0]
497		//     batched: [a_0 + c*b_0, a_1 + c*b_1, a_2]
498		//                                         ^^^ witness-dependent, unmasked
499		//
500		// The transcript truncates the constant term, so this coefficient is sent every round.
501		test_prove_with_degrees(2, 1);
502	}
503}