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