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