binius_ip_prover/sumcheck/
zk_mlecheck.rs1use 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#[derive(Debug, Clone)]
22pub struct ProveZKOutput<F: Field> {
23 pub multilinear_evals: Vec<F>,
25 pub mask_eval: F,
27 pub challenges: Vec<F>,
29}
30
31pub struct MleCheckMaskProver<F: Field, P: PackedField<Scalar = F>, Data: Deref<Target = [P]>> {
38 mask: Mask<P, Data>,
40 eval_point: Vec<F>,
42 n_vars_remaining: usize,
44 prefix_sum: F,
46 suffix_sums: Vec<F>,
48 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 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 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 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 let suffix_sum: F = self.suffix_sums[..var_idx].iter().copied().sum();
116
117 let constant_offset = self.prefix_sum + suffix_sum;
119
120 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 let new_claim = coeffs.evaluate(&challenge);
140
141 let var_idx = self.current_var_index();
142
143 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 vec![self.prefix_sum]
156 }
157
158 fn eval_point(&self) -> &[F] {
159 &self.eval_point[..self.n_vars_remaining]
162 }
163}
164
165pub 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 let mask_eval = mask.evaluate_mle(&eval_point);
210 channel.send_one(mask_eval);
211
212 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 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 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 let batched_round_coeffs = main_round_coeffs + &(mask_round_coeffs * batch_challenge);
252
253 channel.send_many(mlecheck::RoundProof::truncate(batched_round_coeffs).coeffs());
255
256 let challenge = channel.sample();
258 challenges.push(challenge);
259 main_prover.fold(challenge);
260 mask_prover.fold(challenge);
261 }
262
263 let main_evals = main_prover.finish();
265 let mask_evals = mask_prover.finish();
266 let mask_eval_out = mask_evals[0];
267
268 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 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 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 let eval_point: Vec<B128> = random_scalars(&mut rng, n_vars);
313
314 let mask = Mask::new(n_vars, degree, buffer.as_view());
316 let eval_claim = mask.evaluate_mle(&eval_point);
317
318 let prover = MleCheckMaskProver::new(mask, eval_point.clone(), eval_claim);
320
321 let mut prover_transcript = ProverTranscript::new(StdChallenger::default());
323 let output = prove_single_mlecheck(prover, &mut prover_transcript);
324
325 prover_transcript
327 .message()
328 .write_slice(&output.multilinear_evals);
329
330 let mut verifier_transcript = prover_transcript.into_verifier();
332 let sumcheck_output = mlecheck::verify(
333 &eval_point,
334 degree, eval_claim,
336 &mut verifier_transcript,
337 )
338 .unwrap();
339
340 let mask_eval_out: B128 = verifier_transcript.message().read().unwrap();
342
343 assert_eq!(mask_eval_out, sumcheck_output.eval);
346
347 let mut challenge_point = sumcheck_output.challenges;
349 challenge_point.reverse();
350
351 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 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 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 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 let eval_point: Vec<B128> = random_scalars(&mut rng, n_vars);
419
420 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 let main_prover = MleCheckMaskProver::new(main_mask, eval_point.clone(), main_eval_claim);
426
427 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 prover_transcript
434 .message()
435 .write_slice(&output.multilinear_evals);
436
437 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), main_eval_claim,
447 &mut verifier_transcript,
448 )
449 .unwrap();
450
451 let main_eval_out: B128 = verifier_transcript.message().read().unwrap();
453
454 assert_eq!(main_eval_out, eval);
456
457 let mut challenge_point = challenges;
459 challenge_point.reverse();
460
461 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 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 test_prove_with_degrees(2, 2);
476 }
477
478 #[test]
479 fn test_prove_mask_above_main_degree() {
480 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 test_prove_with_degrees(2, 1);
502 }
503}