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