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 self::util::computer_num_and_denom;
4use crate::{errors::PolyIOPErrors, prelude::ProductCheck, PolyIOP};
5use ark_ec::PairingEngine;
6use ark_poly::DenseMultilinearExtension;
7use ark_std::{end_timer, start_timer};
8use pcs::PolynomialCommitmentScheme;
9use std::rc::Rc;
10use transcript::IOPTranscript;
11
12/// A permutation subclaim consists of
13/// - the SubClaim from the ProductCheck
14/// - Challenges beta and gamma
15#[derive(Clone, Debug, Default, PartialEq)]
16pub struct PermutationCheckSubClaim<E, PCS, PC>
17where
18 E: PairingEngine,
19 PC: ProductCheck<E, PCS>,
20 PCS: PolynomialCommitmentScheme<E>,
21{
22 /// the SubClaim from the ProductCheck
23 pub product_check_sub_claim: PC::ProductCheckSubClaim,
24 /// Challenges beta and gamma
25 pub challenges: (E::Fr, E::Fr),
26}
27
28pub mod util;
29
30/// A PermutationCheck is derived from ZeroCheck.
31///
32/// A Permutation Check IOP takes the following steps:
33///
34/// Inputs:
35/// - f(x)
36/// - g(x)
37/// - permutation s_perm(x)
38pub trait PermutationCheck<E, PCS>: ProductCheck<E, PCS>
39where
40 E: PairingEngine,
41 PCS: PolynomialCommitmentScheme<E>,
42{
43 type PermutationCheckSubClaim;
44 type PermutationProof;
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 /// Inputs:
55 /// - f(x)
56 /// - g(x)
57 /// - permutation s_perm(x)
58 /// Outputs:
59 /// - a permutation check proof proving that g is a permutation of f under
60 /// s_perm
61 /// - the Q(x) polynomial build during product check
62 ///
63 /// Cost: O(N)
64 fn prove(
65 pcs_param: &PCS::ProverParam,
66 fx: &Self::MultilinearExtension,
67 gx: &Self::MultilinearExtension,
68 s_perm: &Self::MultilinearExtension,
69 transcript: &mut IOPTranscript<E::Fr>,
70 ) -> Result<(Self::PermutationProof, Self::MultilinearExtension), PolyIOPErrors>;
71
72 /// Verify that an MLE g(x) is a permutation of
73 /// MLE f(x) over a permutation given by s_perm.
74 fn verify(
75 proof: &Self::PermutationProof,
76 aux_info: &Self::VPAuxInfo,
77 transcript: &mut Self::Transcript,
78 ) -> Result<Self::PermutationCheckSubClaim, PolyIOPErrors>;
79}
80
81/// A PermutationCheck is derived from ZeroCheck.
82///
83/// A Permutation Check IOP takes the following steps:
84///
85/// Inputs:
86/// - f(x)
87/// - g(x)
88/// - permutation s_perm(x)
89///
90/// Steps:
91/// 1. `generate_challenge` from current transcript (generate beta, gamma)
92/// 2. `compute_product` to build `prod(x)` etc. from f, g and s_perm
93/// 3. push a commitment of `prod(x)` to the transcript (done by the snark
94/// caller)
95/// 4. `update_challenge` with the updated transcript (generate alpha)
96/// 5. `prove` to generate the proof
97impl<E, PCS> PermutationCheck<E, PCS> for PolyIOP<E::Fr>
98where
99 E: PairingEngine,
100 PCS: PolynomialCommitmentScheme<E, Polynomial = Rc<DenseMultilinearExtension<E::Fr>>>,
101{
102 /// A Permutation SubClaim is indeed a ZeroCheck SubClaim that consists of
103 /// - the SubClaim from the SumCheck
104 /// - the initial challenge r which is used to build eq(x, r)
105 type PermutationCheckSubClaim = PermutationCheckSubClaim<E, PCS, Self>;
106 type PermutationProof = Self::ProductCheckProof;
107
108 /// Initialize the system with a transcript
109 ///
110 /// This function is optional -- in the case where a PermutationCheck is
111 /// an building block for a more complex protocol, the transcript
112 /// may be initialized by this complex protocol, and passed to the
113 /// PermutationCheck prover/verifier.
114 fn init_transcript() -> Self::Transcript {
115 IOPTranscript::<E::Fr>::new(b"Initializing PermutationCheck transcript")
116 }
117
118 /// Inputs:
119 /// - f(x)
120 /// - g(x)
121 /// - permutation s_perm(x)
122 /// Outputs:
123 /// - a permutation check proof proving that g is a permutation of f under
124 /// s_perm
125 /// - the Q(x) polynomial build during product check
126 ///
127 /// Cost: O(N)
128 fn prove(
129 pcs_param: &PCS::ProverParam,
130 fx: &Self::MultilinearExtension,
131 gx: &Self::MultilinearExtension,
132 s_perm: &Self::MultilinearExtension,
133 transcript: &mut IOPTranscript<E::Fr>,
134 ) -> Result<(Self::PermutationProof, Self::MultilinearExtension), PolyIOPErrors> {
135 let start = start_timer!(|| "Permutation check prove");
136 if fx.num_vars != gx.num_vars {
137 return Err(PolyIOPErrors::InvalidParameters(
138 "fx and gx have different number of variables".to_string(),
139 ));
140 }
141
142 if fx.num_vars != s_perm.num_vars {
143 return Err(PolyIOPErrors::InvalidParameters(
144 "fx and s_perm have different number of variables".to_string(),
145 ));
146 }
147
148 // generate challenge `beta` and `gamma` from current transcript
149 let beta = transcript.get_and_append_challenge(b"beta")?;
150 let gamma = transcript.get_and_append_challenge(b"gamma")?;
151 let (numerator, denominator) = computer_num_and_denom(&beta, &gamma, fx, gx, s_perm)?;
152
153 // invoke product check on numerator and denominator
154 let (proof, poly) =
155 <Self as ProductCheck<E, PCS>>::prove(pcs_param, &numerator, &denominator, transcript)?;
156
157 end_timer!(start);
158 Ok((proof, poly))
159 }
160
161 /// Verify that an MLE g(x) is a permutation of an
162 /// MLE f(x) over a permutation given by s_perm.
163 fn verify(
164 proof: &Self::PermutationProof,
165 aux_info: &Self::VPAuxInfo,
166 transcript: &mut Self::Transcript,
167 ) -> Result<Self::PermutationCheckSubClaim, PolyIOPErrors> {
168 let start = start_timer!(|| "Permutation check verify");
169
170 let beta = transcript.get_and_append_challenge(b"beta")?;
171 let gamma = transcript.get_and_append_challenge(b"gamma")?;
172
173 // invoke the zero check on the iop_proof
174 let product_check_sub_claim =
175 <Self as ProductCheck<E, PCS>>::verify(proof, aux_info, transcript)?;
176
177 end_timer!(start);
178 Ok(PermutationCheckSubClaim {
179 product_check_sub_claim,
180 challenges: (beta, gamma),
181 })
182 }
183}
184
185#[cfg(test)]
186mod test {
187 use super::{util::build_prod_partial_eval, PermutationCheck};
188 use crate::{
189 errors::PolyIOPErrors,
190 perm_check::util::computer_num_and_denom,
191 prelude::{identity_permutation_mle, random_permutation_mle},
192 utils::bit_decompose,
193 PolyIOP,
194 };
195 use arithmetic::{VPAuxInfo, VirtualPolynomial};
196 use ark_bls12_381::Bls12_381;
197 use ark_ec::PairingEngine;
198 use ark_ff::{One, Zero};
199 use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
200 use ark_std::test_rng;
201 use pcs::{prelude::KZGMultilinearPCS, PolynomialCommitmentScheme};
202 use std::{marker::PhantomData, rc::Rc};
203
204 type KZG = KZGMultilinearPCS<Bls12_381>;
205
206 fn test_permutation_check_helper<E, PCS>(
207 pcs_param: &PCS::ProverParam,
208 fx: &Rc<DenseMultilinearExtension<E::Fr>>,
209 gx: &Rc<DenseMultilinearExtension<E::Fr>>,
210 s_perm: &Rc<DenseMultilinearExtension<E::Fr>>,
211 ) -> Result<(), PolyIOPErrors>
212 where
213 E: PairingEngine,
214 PCS: PolynomialCommitmentScheme<E, Polynomial = Rc<DenseMultilinearExtension<E::Fr>>>,
215 {
216 let nv = fx.num_vars;
217 let poly_info = VPAuxInfo {
218 max_degree: 2,
219 num_variables: nv,
220 phantom: PhantomData::default(),
221 };
222
223 // prover
224 let mut transcript = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::init_transcript();
225 transcript.append_message(b"testing", b"initializing transcript for testing")?;
226 let (proof, q_x) = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::prove(
227 pcs_param,
228 fx,
229 gx,
230 s_perm,
231 &mut transcript,
232 )?;
233
234 // verifier
235 let mut transcript = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::init_transcript();
236 transcript.append_message(b"testing", b"initializing transcript for testing")?;
237 let perm_check_sum_claim = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::verify(
238 &proof,
239 &poly_info,
240 &mut transcript,
241 )?;
242
243 let prod_partial_evals = build_prod_partial_eval(&q_x)?;
244 let prod_0x = prod_partial_evals[0].clone();
245 let prod_1x = prod_partial_evals[1].clone();
246 let prod_x0 = prod_partial_evals[2].clone();
247 let prod_x1 = prod_partial_evals[3].clone();
248
249 let (numerator, denominator) = computer_num_and_denom(
250 &perm_check_sum_claim.challenges.0,
251 &perm_check_sum_claim.challenges.1,
252 fx,
253 gx,
254 &s_perm,
255 )?;
256
257 // compute (g(x) + beta * s_perm(x) + gamma) * prod(0, x) * alpha
258 // which is prods[6] * prod[1] * alpha
259 let mut q_x = VirtualPolynomial::new_from_mle(&denominator, E::Fr::one());
260 q_x.mul_by_mle(
261 prod_0x,
262 perm_check_sum_claim.product_check_sub_claim.challenge,
263 )?;
264
265 // (g(x) + beta * s_perm(x) + gamma) * prod(0, x) * alpha
266 // - (f(x) + beta * s_id(x) + gamma) * alpha
267 q_x.add_mle_list(
268 [numerator],
269 -perm_check_sum_claim.product_check_sub_claim.challenge,
270 )?;
271
272 // Q(x) := prod(1,x) - prod(x, 0) * prod(x, 1)
273 // + alpha * (
274 // (g(x) + beta * s_perm(x) + gamma) * prod(0, x)
275 // - (f(x) + beta * s_id(x) + gamma))
276 q_x.add_mle_list([prod_x0, prod_x1], -E::Fr::one())?;
277 q_x.add_mle_list([prod_1x], E::Fr::one())?;
278
279 if q_x
280 .evaluate(
281 &perm_check_sum_claim
282 .product_check_sub_claim
283 .zero_check_sub_claim
284 .sum_check_sub_claim
285 .point,
286 )
287 .unwrap()
288 != perm_check_sum_claim
289 .product_check_sub_claim
290 .zero_check_sub_claim
291 .sum_check_sub_claim
292 .expected_evaluation
293 {
294 return Err(PolyIOPErrors::InvalidVerifier("wrong subclaim".to_string()));
295 };
296
297 // test q_x is a 0 over boolean hypercube
298 for i in 0..1 << nv {
299 let bit_sequence = bit_decompose(i, nv);
300 let eval: Vec<E::Fr> = bit_sequence
301 .iter()
302 .map(|x| E::Fr::from(*x as u64))
303 .collect();
304 let res = q_x.evaluate(&eval).unwrap();
305 if !res.is_zero() {}
306 }
307 Ok(())
308 }
309
310 fn test_permutation_check(nv: usize) -> Result<(), PolyIOPErrors> {
311 let mut rng = test_rng();
312
313 let srs = KZGMultilinearPCS::<Bls12_381>::gen_srs_for_testing(&mut rng, nv + 1)?;
314 let (pcs_param, _) = KZGMultilinearPCS::<Bls12_381>::trim(&srs, nv + 1, Some(nv + 1))?;
315
316 {
317 // good path: w is a permutation of w itself under the identify map
318 let w = Rc::new(DenseMultilinearExtension::rand(nv, &mut rng));
319 // s_perm is the identity map
320 let s_perm = identity_permutation_mle(nv);
321 test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &w, &w, &s_perm)?;
322 }
323
324 {
325 // bad path 1: w is a not permutation of w itself under a random map
326 let w = Rc::new(DenseMultilinearExtension::rand(nv, &mut rng));
327 // s_perm is a random map
328 let s_perm = random_permutation_mle(nv, &mut rng);
329
330 if nv == 1 {
331 test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &w, &w, &s_perm)?;
332 } else {
333 assert!(test_permutation_check_helper::<Bls12_381, KZG>(
334 &pcs_param, &w, &w, &s_perm
335 )
336 .is_err());
337 }
338 }
339
340 {
341 // bad path 2: f is a not permutation of g under a identity map
342 let f = Rc::new(DenseMultilinearExtension::rand(nv, &mut rng));
343 let g = Rc::new(DenseMultilinearExtension::rand(nv, &mut rng));
344 // s_perm is the identity map
345 let s_perm = identity_permutation_mle(nv);
346
347 assert!(
348 test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &f, &g, &s_perm)
349 .is_err()
350 );
351 }
352
353 Ok(())
354 }
355
356 #[test]
357 fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
358 test_permutation_check(1)
359 }
360 #[test]
361 fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
362 test_permutation_check(5)
363 }
364
365 #[test]
366 fn zero_polynomial_should_error() -> Result<(), PolyIOPErrors> {
367 assert!(test_permutation_check(0).is_err());
368 Ok(())
369 }
370}