hyperplonk/poly-iop/src/perm_check/mod.rs
poly-iop/src/perm_check/mod.rsRaw
1//! Main module for the Permutation Check protocol
2
3use crate::{
4 errors::PolyIOPErrors, perm_check::util::compute_prod_0, structs::IOPProof,
5 transcript::IOPTranscript, utils::get_index, PolyIOP, VirtualPolynomial, ZeroCheck,
6};
7use ark_ff::PrimeField;
8use ark_poly::DenseMultilinearExtension;
9use ark_std::{end_timer, start_timer};
10use std::rc::Rc;
11
12pub mod util;
13
14/// A PermutationCheck is derived from ZeroCheck.
15///
16/// A Permutation Check IOP takes the following steps:
17///
18/// Inputs:
19/// - f(x)
20/// - g(x)
21/// - permutation s_perm(x)
22///
23/// Steps:
24/// 1. `generate_challenge` from current transcript (generate beta, gamma)
25/// 2. `compute_product` to build `prod(x)` etc. from f, g and s_perm
26/// 3. push a commitment of `prod(x)` to the transcript (done by the snark
27/// caller)
28/// 4. `update_challenge` with the updated transcript (generate alpha)
29/// 5. `prove` to generate the proof
30pub trait PermutationCheck<F: PrimeField>: ZeroCheck<F> {
31 type PermutationCheckSubClaim;
32 type PermutationChallenge;
33
34 /// Initialize the system with a transcript
35 ///
36 /// This function is optional -- in the case where a PermutationCheck is
37 /// an building block for a more complex protocol, the transcript
38 /// may be initialized by this complex protocol, and passed to the
39 /// PermutationCheck prover/verifier.
40 fn init_transcript() -> Self::Transcript;
41
42 /// Step 1 of the IOP.
43 /// Generate challenge beta and gamma from a transcript.
44 fn generate_challenge(
45 transcript: &mut Self::Transcript,
46 ) -> Result<Self::PermutationChallenge, PolyIOPErrors>;
47
48 /// Step 4 of the IOP.
49 /// Update the challenge with alpha; returns an error if
50 /// alpha already exists.
51 fn update_challenge(
52 challenge: &mut Self::PermutationChallenge,
53 transcript: &mut Self::Transcript,
54 prod_x_binding: &F,
55 ) -> Result<(), PolyIOPErrors>;
56
57 /// Step 2 of the IOP.
58 /// Compute the following 7 polynomials
59 /// - prod(x)
60 /// - prod(0, x)
61 /// - prod(1, x)
62 /// - prod(x, 0)
63 /// - prod(x, 1)
64 /// - numerator
65 /// - denominator
66 ///
67 /// where
68 /// - `prod(0,x) := prod(0, x0, x1, …, xn)` which is the MLE over the
69 /// evaluations of the following polynomial on the boolean hypercube
70 /// {0,1}^n:
71 ///
72 /// (f(x) + \beta s_id(x) + \gamma)/(g(x) + \beta s_perm(x) + \gamma)
73 ///
74 /// where
75 /// - beta and gamma are challenges
76 /// - f(x), g(x), s_id(x), s_perm(x) are mle-s
77 ///
78 /// - `prod(1,x) := prod(x, 0) * prod(x, 1)`
79 /// - numerator is the MLE for `f(x) + \beta s_id(x) + \gamma`
80 /// - denominator is the MLE for `g(x) + \beta s_perm(x) + \gamma`
81 ///
82 /// The caller needs to check num_vars matches in f/g/s_id/s_perm
83 /// Cost: linear in N.
84 fn compute_products(
85 challenge: &Self::PermutationChallenge,
86 fx: &DenseMultilinearExtension<F>,
87 gx: &DenseMultilinearExtension<F>,
88 s_perm: &DenseMultilinearExtension<F>,
89 ) -> Result<[DenseMultilinearExtension<F>; 7], PolyIOPErrors>;
90
91 /// Step 5 of the IOP.
92 ///
93 /// Initialize the prover to argue that an MLE g(x) is a permutation of
94 /// MLE f(x) over a permutation given by s_perm.
95 /// Inputs:
96 /// - 7 MLEs from `Self::compute_products`
97 /// - challenge: `Self::Challenge` that has been updated
98 /// - transcript: a transcript that is used to generate the challenges beta
99 /// and gamma
100 /// Cost: O(N)
101 fn prove(
102 prod_x_and_aux_info: &[DenseMultilinearExtension<F>; 7],
103 challenge: &Self::PermutationChallenge,
104 transcript: &mut IOPTranscript<F>,
105 ) -> Result<Self::Proof, PolyIOPErrors>;
106
107 /// Verify that an MLE g(x) is a permutation of
108 /// MLE f(x) over a permutation given by s_perm.
109 fn verify(
110 proof: &Self::Proof,
111 aux_info: &Self::VPAuxInfo,
112 transcript: &mut Self::Transcript,
113 ) -> Result<Self::PermutationCheckSubClaim, PolyIOPErrors>;
114}
115
116/// A permutation subclaim consists of
117/// - A zero check IOP subclaim for Q(x) is 0, consists of the following:
118/// (See `build_qx` for definition of Q(x).)
119/// - the SubClaim from the SumCheck
120/// - the initial challenge r which is used to build eq(x, r) in ZeroCheck
121/// - A final query for `prod(1, ..., 1, 0) = 1`.
122// Note that this final query is in fact a constant that
123// is independent from the proof. So we should avoid
124// (de)serialize it.
125#[derive(Clone, Debug, Default, PartialEq)]
126pub struct PermutationCheckSubClaim<F: PrimeField, ZC: ZeroCheck<F>> {
127 // the SubClaim from the ZeroCheck
128 zero_check_sub_claim: ZC::ZeroCheckSubClaim,
129 // final query which consists of
130 // - the vector `(1, ..., 1, 0)`
131 // - the evaluation `1`
132 final_query: (Vec<F>, F),
133}
134
135pub struct PermutationChallenge<F: PrimeField> {
136 alpha: Option<F>,
137 beta: F,
138 gamma: F,
139}
140
141/// A PermutationCheck is derived from ZeroCheck.
142///
143/// A Permutation Check IOP takes the following steps:
144///
145/// Inputs:
146/// - f(x)
147/// - g(x)
148/// - permutation s_perm(x)
149///
150/// Steps:
151/// 1. `generate_challenge` from current transcript (generate beta, gamma)
152/// 2. `compute_product` to build `prod(x)` etc. from f, g and s_perm
153/// 3. push a commitment of `prod(x)` to the transcript (done by the snark
154/// caller)
155/// 4. `update_challenge` with the updated transcript (generate alpha)
156/// 5. `prove` to generate the proof
157impl<F: PrimeField> PermutationCheck<F> for PolyIOP<F> {
158 /// A Permutation SubClaim is indeed a ZeroCheck SubClaim that consists of
159 /// - the SubClaim from the SumCheck
160 /// - the initial challenge r which is used to build eq(x, r)
161 type PermutationCheckSubClaim = PermutationCheckSubClaim<F, Self>;
162
163 type PermutationChallenge = PermutationChallenge<F>;
164
165 /// Initialize the system with a transcript
166 ///
167 /// This function is optional -- in the case where a PermutationCheck is
168 /// an building block for a more complex protocol, the transcript
169 /// may be initialized by this complex protocol, and passed to the
170 /// PermutationCheck prover/verifier.
171 fn init_transcript() -> Self::Transcript {
172 IOPTranscript::<F>::new(b"Initializing PermutationCheck transcript")
173 }
174
175 /// Step 1 of the IOP.
176 /// Generate challenge beta and gamma from a transcript.
177 fn generate_challenge(
178 transcript: &mut Self::Transcript,
179 ) -> Result<Self::PermutationChallenge, PolyIOPErrors> {
180 Ok(Self::PermutationChallenge {
181 beta: transcript.get_and_append_challenge(b"beta")?,
182 gamma: transcript.get_and_append_challenge(b"gamma")?,
183 alpha: None,
184 })
185 }
186
187 /// Step 4 of the IOP.
188 /// Update the challenge with alpha; returns an error if
189 /// alpha already exists.
190 fn update_challenge(
191 challenge: &mut Self::PermutationChallenge,
192 transcript: &mut Self::Transcript,
193 prod_x_binding: &F,
194 ) -> Result<(), PolyIOPErrors> {
195 if challenge.alpha.is_some() {
196 return Err(PolyIOPErrors::InvalidTranscript(
197 "alpha should not be sampled at the current stage".to_string(),
198 ));
199 }
200 transcript.append_field_element(b"prod(x)", prod_x_binding)?;
201 challenge.alpha = Some(transcript.get_and_append_challenge(b"alpha")?);
202 Ok(())
203 }
204
205 /// Step 2 of the IOP.
206 /// Compute the following 7 polynomials
207 /// - prod(x)
208 /// - prod(0, x)
209 /// - prod(1, x)
210 /// - prod(x, 0)
211 /// - prod(x, 1)
212 /// - numerator
213 /// - denominator
214 ///
215 /// where
216 /// - `prod(0,x) := prod(0, x0, x1, …, xn)` which is the MLE over the
217 /// evaluations of the following polynomial on the boolean hypercube
218 /// {0,1}^n:
219 ///
220 /// (f(x) + \beta s_id(x) + \gamma)/(g(x) + \beta s_perm(x) + \gamma)
221 ///
222 /// where
223 /// - beta and gamma are challenges
224 /// - f(x), g(x), s_id(x), s_perm(x) are mle-s
225 ///
226 /// - `prod(1,x) := prod(x, 0) * prod(x, 1)`
227 /// - numerator is the MLE for `f(x) + \beta s_id(x) + \gamma`
228 /// - denominator is the MLE for `g(x) + \beta s_perm(x) + \gamma`
229 ///
230 /// The caller needs to check num_vars matches in f/g/s_id/s_perm
231 /// Cost: linear in N.
232 fn compute_products(
233 challenge: &Self::PermutationChallenge,
234 fx: &DenseMultilinearExtension<F>,
235 gx: &DenseMultilinearExtension<F>,
236 s_perm: &DenseMultilinearExtension<F>,
237 ) -> Result<[DenseMultilinearExtension<F>; 7], PolyIOPErrors> {
238 let start = start_timer!(|| "compute all prod polynomial");
239
240 if challenge.alpha.is_some() {
241 return Err(PolyIOPErrors::InvalidTranscript(
242 "alpha is already sampled".to_string(),
243 ));
244 }
245
246 let num_vars = fx.num_vars;
247
248 // ===================================
249 // prod(0, x)
250 // ===================================
251 let (prod_0x, numerator, denominator) =
252 compute_prod_0(&challenge.beta, &challenge.gamma, fx, gx, s_perm)?;
253
254 // ===================================
255 // prod(1, x)
256 // ===================================
257 //
258 // `prod(1, x)` can be computed via recursing the following formula for 2^n-1
259 // times
260 //
261 // `prod(1, x_1, ..., x_n) :=
262 // prod(x_1, x_2, ..., x_n, 0) * prod(x_1, x_2, ..., x_n, 1)`
263 //
264 // At any given step, the right hand side of the equation
265 // is available via either eval_0x or the current view of eval_1x
266 let eval_0x = &prod_0x.evaluations;
267 let mut eval_1x = vec![];
268 for x in 0..(1 << num_vars) - 1 {
269 // sign will decide if the evaluation should be looked up from eval_0x or
270 // eval_1x; x_zero_index is the index for the evaluation (x_2, ..., x_n,
271 // 0); x_one_index is the index for the evaluation (x_2, ..., x_n, 1);
272 let (x_zero_index, x_one_index, sign) = get_index(x, num_vars);
273 if !sign {
274 eval_1x.push(eval_0x[x_zero_index] * eval_0x[x_one_index]);
275 } else {
276 // sanity check: if we are trying to look up from the eval_1x table,
277 // then the target index must already exist
278 if x_zero_index >= eval_1x.len() || x_one_index >= eval_1x.len() {
279 return Err(PolyIOPErrors::ShouldNotArrive);
280 }
281 eval_1x.push(eval_1x[x_zero_index] * eval_1x[x_one_index]);
282 }
283 }
284 // prod(1, 1, ..., 1) := 0
285 eval_1x.push(F::zero());
286
287 // ===================================
288 // prod(x)
289 // ===================================
290 // prod(x)'s evaluation is indeed `e := [eval_0x[..], eval_1x[..]].concat()`
291 let eval = [eval_0x.as_slice(), eval_1x.as_slice()].concat();
292
293 // ===================================
294 // prod(x, 0) and prod(x, 1)
295 // ===================================
296 //
297 // now we compute eval_x0 and eval_x1
298 // eval_0x will be the odd coefficients of eval
299 // and eval_1x will be the even coefficients of eval
300 let mut eval_x0 = vec![];
301 let mut eval_x1 = vec![];
302 for (x, &prod_x) in eval.iter().enumerate() {
303 if x & 1 == 0 {
304 eval_x0.push(prod_x);
305 } else {
306 eval_x1.push(prod_x);
307 }
308 }
309
310 let prod_1x = DenseMultilinearExtension::from_evaluations_vec(num_vars, eval_1x);
311 let prod_x0 = DenseMultilinearExtension::from_evaluations_vec(num_vars, eval_x0);
312 let prod_x1 = DenseMultilinearExtension::from_evaluations_vec(num_vars, eval_x1);
313 let prod = DenseMultilinearExtension::from_evaluations_vec(num_vars + 1, eval);
314
315 end_timer!(start);
316 Ok([
317 prod,
318 prod_0x,
319 prod_1x,
320 prod_x0,
321 prod_x1,
322 numerator,
323 denominator,
324 ])
325 }
326
327 /// Step 5 of the IOP.
328 ///
329 /// Generate a proof to argue that an MLE g(x) is a permutation of
330 /// MLE f(x) over a permutation given by s_perm.
331 /// Inputs:
332 /// - 7 MLEs from `Self::compute_products(*, f, g, s_perm)`
333 /// - challenge: `Self::Challenge` that has been updated
334 /// - transcript: a transcript that is used to generate the challenges beta
335 /// and gamma
336 /// Cost: O(N)
337 fn prove(
338 prod_x_and_aux_info: &[DenseMultilinearExtension<F>; 7],
339 challenge: &Self::PermutationChallenge,
340 transcript: &mut IOPTranscript<F>,
341 ) -> Result<Self::Proof, PolyIOPErrors> {
342 let alpha = match challenge.alpha {
343 Some(p) => p,
344 None => {
345 return Err(PolyIOPErrors::InvalidTranscript(
346 "alpha is not sampled yet".to_string(),
347 ))
348 },
349 };
350
351 let (proof, _q_x) = prove_internal(prod_x_and_aux_info, &alpha, transcript)?;
352 Ok(proof)
353 }
354
355 /// Verify that an MLE g(x) is a permutation of an
356 /// MLE f(x) over a permutation given by s_perm.
357 fn verify(
358 proof: &Self::Proof,
359 aux_info: &Self::VPAuxInfo,
360 transcript: &mut Self::Transcript,
361 ) -> Result<Self::PermutationCheckSubClaim, PolyIOPErrors> {
362 let start = start_timer!(|| "Permutation check verify");
363
364 // invoke the zero check on the iop_proof
365 let zero_check_sub_claim = <Self as ZeroCheck<F>>::verify(proof, aux_info, transcript)?;
366
367 let mut final_query = vec![F::one(); aux_info.num_variables];
368 final_query[aux_info.num_variables - 1] = F::zero();
369 let final_eval = F::one();
370
371 end_timer!(start);
372
373 Ok(PermutationCheckSubClaim {
374 zero_check_sub_claim,
375 final_query: (final_query, final_eval),
376 })
377 }
378}
379
380/// Step 5 of the IOP.
381///
382/// Generate a proof to argue that an MLE g(x) is a permutation of
383/// MLE f(x) over a permutation given by s_perm.
384/// Inputs:
385/// - 7 MLEs from `Self::compute_products(*, f, g, s_perm)`
386/// - challenge: `Self::Challenge` that has been updated
387/// - transcript: a transcript that is used to generate the challenges beta and
388/// gamma
389///
390/// Returns proof and Q(x) for testing purpose.
391///
392/// Cost: O(N)
393fn prove_internal<F: PrimeField>(
394 prod_x_and_aux_info: &[DenseMultilinearExtension<F>; 7],
395 alpha: &F,
396 transcript: &mut IOPTranscript<F>,
397) -> Result<(IOPProof<F>, VirtualPolynomial<F>), PolyIOPErrors> {
398 let start = start_timer!(|| "Permutation check prove");
399
400 // prods consists of the following:
401 // - prod(x)
402 // - prod(0, x)
403 // - prod(1, x)
404 // - prod(x, 0)
405 // - prod(x, 1)
406 // - numerator
407 // - denominator
408 let prod_0x = Rc::new(prod_x_and_aux_info[1].clone());
409 let prod_1x = Rc::new(prod_x_and_aux_info[2].clone());
410 let prod_x1 = Rc::new(prod_x_and_aux_info[3].clone());
411 let prod_x0 = Rc::new(prod_x_and_aux_info[4].clone());
412 let numerator = Rc::new(prod_x_and_aux_info[5].clone());
413 let denominator = Rc::new(prod_x_and_aux_info[6].clone());
414
415 // compute (g(x) + beta * s_perm(x) + gamma) * prod(0, x) * alpha
416 // which is prods[6] * prod[1] * alpha
417 let mut q_x = VirtualPolynomial::new_from_mle(denominator, F::one());
418 q_x.mul_by_mle(prod_0x, *alpha)?;
419
420 // (g(x) + beta * s_perm(x) + gamma) * prod(0, x) * alpha
421 // - (f(x) + beta * s_id(x) + gamma) * alpha
422 q_x.add_mle_list([numerator], -*alpha)?;
423
424 // Q(x) := prod(1,x) - prod(x, 0) * prod(x, 1)
425 // + alpha * (
426 // (g(x) + beta * s_perm(x) + gamma) * prod(0, x)
427 // - (f(x) + beta * s_id(x) + gamma))
428 q_x.add_mle_list([prod_x0, prod_x1], -F::one())?;
429 q_x.add_mle_list([prod_1x], F::one())?;
430 let iop_proof = <PolyIOP<F> as ZeroCheck<F>>::prove(&q_x, transcript)?;
431
432 end_timer!(start);
433 Ok((iop_proof, q_x))
434}
435
436#[cfg(test)]
437mod test {
438
439 use super::PermutationCheck;
440 use crate::{
441 errors::PolyIOPErrors,
442 perm_check::{prove_internal, util::identity_permutation_mle},
443 random_permutation_mle,
444 structs::IOPProof,
445 utils::bit_decompose,
446 virtual_poly::VPAuxInfo,
447 PolyIOP, VirtualPolynomial,
448 };
449 use ark_bls12_381::Fr;
450 use ark_ff::{PrimeField, Zero};
451 use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
452 use ark_std::test_rng;
453 use std::marker::PhantomData;
454
455 fn mock_commit<F: PrimeField>(_f: &DenseMultilinearExtension<F>) -> F {
456 let mut rng = test_rng();
457 F::rand(&mut rng)
458 }
459
460 fn test_permutation_check_helper(
461 f: &DenseMultilinearExtension<Fr>,
462 g: &DenseMultilinearExtension<Fr>,
463 s_perm: &DenseMultilinearExtension<Fr>,
464 ) -> Result<(IOPProof<Fr>, VirtualPolynomial<Fr>), PolyIOPErrors> {
465 let mut transcript = <PolyIOP<Fr> as PermutationCheck<Fr>>::init_transcript();
466 transcript.append_message(b"testing", b"initializing transcript for testing")?;
467
468 let mut challenge =
469 <PolyIOP<Fr> as PermutationCheck<Fr>>::generate_challenge(&mut transcript)?;
470
471 let prod_x_and_aux =
472 <PolyIOP<Fr> as PermutationCheck<Fr>>::compute_products(&challenge, f, g, s_perm)?;
473
474 let prod_x_binding = mock_commit(&prod_x_and_aux[0]);
475
476 <PolyIOP<Fr> as PermutationCheck<Fr>>::update_challenge(
477 &mut challenge,
478 &mut transcript,
479 &prod_x_binding,
480 )?;
481 let alpha = challenge.alpha.unwrap();
482
483 prove_internal(&prod_x_and_aux, &alpha, &mut transcript)
484 }
485
486 fn test_permutation_check(nv: usize) -> Result<(), PolyIOPErrors> {
487 let mut rng = test_rng();
488
489 let poly_info = VPAuxInfo {
490 max_degree: 2,
491 num_variables: nv,
492 phantom: PhantomData::default(),
493 };
494
495 {
496 // good path: w is a permutation of w itself under the identify map
497 let w = DenseMultilinearExtension::rand(nv, &mut rng);
498
499 // s_perm is the identity map
500 let s_perm = identity_permutation_mle(nv);
501
502 let (proof, q_x) = test_permutation_check_helper(&w, &w, &s_perm)?;
503
504 let mut transcript = <PolyIOP<Fr> as PermutationCheck<Fr>>::init_transcript();
505 transcript.append_message(b"testing", b"initializing transcript for testing")?;
506 let subclaim =
507 <PolyIOP<Fr> as PermutationCheck<Fr>>::verify(&proof, &poly_info, &mut transcript)?
508 .zero_check_sub_claim;
509 assert_eq!(
510 q_x.evaluate(&subclaim.sum_check_sub_claim.point).unwrap(),
511 subclaim.sum_check_sub_claim.expected_evaluation,
512 "wrong subclaim"
513 );
514
515 // test q_x is a 0 over boolean hypercube
516 for i in 0..1 << nv {
517 let bit_sequence = bit_decompose(i, nv);
518 let eval: Vec<Fr> = bit_sequence.iter().map(|x| Fr::from(*x as u64)).collect();
519 let res = q_x.evaluate(&eval)?;
520 assert!(res.is_zero())
521 }
522 }
523
524 {
525 // bad path 1: w is a not permutation of w itself under a random map
526 let w = DenseMultilinearExtension::rand(nv, &mut rng);
527
528 // s_perm is a random map
529 let s_perm = random_permutation_mle(nv, &mut rng);
530
531 let (proof, q_x) = test_permutation_check_helper(&w, &w, &s_perm)?;
532
533 let mut transcript = <PolyIOP<Fr> as PermutationCheck<Fr>>::init_transcript();
534 transcript.append_message(b"testing", b"initializing transcript for testing")?;
535 if nv != 1 {
536 assert!(<PolyIOP<Fr> as PermutationCheck<Fr>>::verify(
537 &proof,
538 &poly_info,
539 &mut transcript
540 )
541 .is_err());
542 } else {
543 // a trivial poly is always a permutation of itself, so the zero check should
544 // pass
545 let subclaim = <PolyIOP<Fr> as PermutationCheck<Fr>>::verify(
546 &proof,
547 &poly_info,
548 &mut transcript,
549 )?
550 .zero_check_sub_claim;
551
552 // the evaluation should fail because a different s_perm is used for proof and
553 // for w |-> w mapping
554 assert_ne!(
555 q_x.evaluate(&subclaim.sum_check_sub_claim.point).unwrap(),
556 subclaim.sum_check_sub_claim.expected_evaluation,
557 "wrong subclaim"
558 );
559 }
560 }
561
562 {
563 // bad path 2: f is a not permutation of g under a identity map
564 let f = DenseMultilinearExtension::rand(nv, &mut rng);
565 let g = DenseMultilinearExtension::rand(nv, &mut rng);
566
567 // s_perm is the identity map
568 let s_perm = identity_permutation_mle(nv);
569
570 let (proof, q_x) = test_permutation_check_helper(&f, &g, &s_perm)?;
571
572 let mut transcript = <PolyIOP<Fr> as PermutationCheck<Fr>>::init_transcript();
573 transcript.append_message(b"testing", b"initializing transcript for testing")?;
574 if nv != 1 {
575 assert!(<PolyIOP<Fr> as PermutationCheck<Fr>>::verify(
576 &proof,
577 &poly_info,
578 &mut transcript
579 )
580 .is_err());
581 } else {
582 // a trivial poly is always a permutation of itself, so the zero check should
583 // pass
584 let subclaim = <PolyIOP<Fr> as PermutationCheck<Fr>>::verify(
585 &proof,
586 &poly_info,
587 &mut transcript,
588 )?
589 .zero_check_sub_claim;
590
591 // the evaluation should fail because a different s_perm is used for proof and
592 // for f |-> g mapping
593 assert_ne!(
594 q_x.evaluate(&subclaim.sum_check_sub_claim.point).unwrap(),
595 subclaim.sum_check_sub_claim.expected_evaluation,
596 "wrong subclaim"
597 );
598 }
599 }
600
601 Ok(())
602 }
603
604 #[test]
605 fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
606 test_permutation_check(1)
607 }
608 #[test]
609 fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
610 test_permutation_check(5)
611 }
612
613 #[test]
614 fn zero_polynomial_should_error() -> Result<(), PolyIOPErrors> {
615 assert!(test_permutation_check(0).is_err());
616 Ok(())
617 }
618
619 #[test]
620 fn test_compute_prod() -> Result<(), PolyIOPErrors> {
621 let mut rng = test_rng();
622
623 for num_vars in 2..6 {
624 let f = DenseMultilinearExtension::rand(num_vars, &mut rng);
625 let g = DenseMultilinearExtension::rand(num_vars, &mut rng);
626
627 let s_id = identity_permutation_mle::<Fr>(num_vars);
628 let s_perm = random_permutation_mle(num_vars, &mut rng);
629
630 let mut transcript = <PolyIOP<Fr> as PermutationCheck<Fr>>::init_transcript();
631 transcript.append_message(b"testing", b"initializing transcript for testing")?;
632 let challenge =
633 <PolyIOP<Fr> as PermutationCheck<Fr>>::generate_challenge(&mut transcript)?;
634
635 let res = <PolyIOP<Fr> as PermutationCheck<Fr>>::compute_products(
636 &challenge, &f, &g, &s_perm,
637 )?;
638
639 for i in 0..1 << num_vars {
640 let r: Vec<Fr> = bit_decompose(i, num_vars)
641 .iter()
642 .map(|&x| Fr::from(x))
643 .collect();
644
645 let eval = res[1].evaluate(&r).unwrap();
646
647 let f_eval = f.evaluate(&r).unwrap();
648 let g_eval = g.evaluate(&r).unwrap();
649 let s_id_eval = s_id.evaluate(&r).unwrap();
650 let s_perm_eval = s_perm.evaluate(&r).unwrap();
651 let eval_rec = (f_eval + challenge.beta * s_id_eval + challenge.gamma)
652 / (g_eval + challenge.beta * s_perm_eval + challenge.gamma);
653
654 assert_eq!(eval, eval_rec);
655 }
656 }
657 Ok(())
658 }
659}