1//! Main module for the Permutation Check protocol
  2
  3use self::util::computer_num_and_denom;
  4use crate::{
  5    pcs::PolynomialCommitmentScheme,
  6    poly_iop::{errors::PolyIOPErrors, prelude::ProductCheck, PolyIOP},
  7};
  8use ark_ec::PairingEngine;
  9use ark_poly::DenseMultilinearExtension;
 10use ark_std::{end_timer, start_timer};
 11use std::rc::Rc;
 12use transcript::IOPTranscript;
 13
 14/// A permutation subclaim consists of
 15/// - the SubClaim from the ProductCheck
 16/// - Challenges beta and gamma
 17#[derive(Clone, Debug, Default, PartialEq)]
 18pub struct PermutationCheckSubClaim<E, PCS, PC>
 19where
 20    E: PairingEngine,
 21    PC: ProductCheck<E, PCS>,
 22    PCS: PolynomialCommitmentScheme<E>,
 23{
 24    /// the SubClaim from the ProductCheck
 25    pub product_check_sub_claim: PC::ProductCheckSubClaim,
 26    /// Challenges beta and gamma
 27    pub challenges: (E::Fr, E::Fr),
 28}
 29
 30pub mod util;
 31
 32/// A PermutationCheck w.r.t. `(f, g, perm)`
 33/// proves that g is a permutation of f under
 34/// permutation `perm`
 35/// It is derived from ProductCheck.
 36///
 37/// A Permutation Check IOP takes the following steps:
 38///
 39/// Inputs:
 40/// - f(x)
 41/// - g(x)
 42/// - permutation s_perm(x)
 43pub trait PermutationCheck<E, PCS>: ProductCheck<E, PCS>
 44where
 45    E: PairingEngine,
 46    PCS: PolynomialCommitmentScheme<E>,
 47{
 48    type PermutationCheckSubClaim;
 49    type PermutationProof;
 50
 51    /// Initialize the system with a transcript
 52    ///
 53    /// This function is optional -- in the case where a PermutationCheck is
 54    /// an building block for a more complex protocol, the transcript
 55    /// may be initialized by this complex protocol, and passed to the
 56    /// PermutationCheck prover/verifier.
 57    fn init_transcript() -> Self::Transcript;
 58
 59    /// Inputs:
 60    /// - f(x)
 61    /// - g(x)
 62    /// - permutation s_perm(x)
 63    /// Outputs:
 64    /// - a permutation check proof proving that g is a permutation of f under
 65    ///   s_perm
 66    /// - the product polynomial build during product check
 67    ///
 68    /// Cost: O(N)
 69    fn prove(
 70        pcs_param: &PCS::ProverParam,
 71        fx: &Self::MultilinearExtension,
 72        gx: &Self::MultilinearExtension,
 73        s_perm: &Self::MultilinearExtension,
 74        transcript: &mut IOPTranscript<E::Fr>,
 75    ) -> Result<(Self::PermutationProof, Self::MultilinearExtension), PolyIOPErrors>;
 76
 77    /// Verify that an MLE g(x) is a permutation of
 78    /// MLE f(x) over a permutation given by s_perm.
 79    fn verify(
 80        proof: &Self::PermutationProof,
 81        aux_info: &Self::VPAuxInfo,
 82        transcript: &mut Self::Transcript,
 83    ) -> Result<Self::PermutationCheckSubClaim, PolyIOPErrors>;
 84}
 85
 86impl<E, PCS> PermutationCheck<E, PCS> for PolyIOP<E::Fr>
 87where
 88    E: PairingEngine,
 89    PCS: PolynomialCommitmentScheme<E, Polynomial = Rc<DenseMultilinearExtension<E::Fr>>>,
 90{
 91    type PermutationCheckSubClaim = PermutationCheckSubClaim<E, PCS, Self>;
 92    type PermutationProof = Self::ProductCheckProof;
 93
 94    fn init_transcript() -> Self::Transcript {
 95        IOPTranscript::<E::Fr>::new(b"Initializing PermutationCheck transcript")
 96    }
 97
 98    fn prove(
 99        pcs_param: &PCS::ProverParam,
100        fx: &Self::MultilinearExtension,
101        gx: &Self::MultilinearExtension,
102        s_perm: &Self::MultilinearExtension,
103        transcript: &mut IOPTranscript<E::Fr>,
104    ) -> Result<(Self::PermutationProof, Self::MultilinearExtension), PolyIOPErrors> {
105        let start = start_timer!(|| "Permutation check prove");
106        if fx.num_vars != gx.num_vars {
107            return Err(PolyIOPErrors::InvalidParameters(
108                "fx and gx have different number of variables".to_string(),
109            ));
110        }
111
112        if fx.num_vars != s_perm.num_vars {
113            return Err(PolyIOPErrors::InvalidParameters(
114                "fx and s_perm have different number of variables".to_string(),
115            ));
116        }
117
118        // generate challenge `beta` and `gamma` from current transcript
119        let beta = transcript.get_and_append_challenge(b"beta")?;
120        let gamma = transcript.get_and_append_challenge(b"gamma")?;
121        let (numerator, denominator) = computer_num_and_denom(&beta, &gamma, fx, gx, s_perm)?;
122
123        // invoke product check on numerator and denominator
124        let (proof, prod_poly, _frac_poly) = <Self as ProductCheck<E, PCS>>::prove(
125            pcs_param,
126            &[numerator],
127            &[denominator],
128            transcript,
129        )?;
130
131        end_timer!(start);
132        Ok((proof, prod_poly))
133    }
134
135    /// Verify that an MLE g(x) is a permutation of an
136    /// MLE f(x) over a permutation given by s_perm.
137    fn verify(
138        proof: &Self::PermutationProof,
139        aux_info: &Self::VPAuxInfo,
140        transcript: &mut Self::Transcript,
141    ) -> Result<Self::PermutationCheckSubClaim, PolyIOPErrors> {
142        let start = start_timer!(|| "Permutation check verify");
143
144        let beta = transcript.get_and_append_challenge(b"beta")?;
145        let gamma = transcript.get_and_append_challenge(b"gamma")?;
146
147        // invoke the zero check on the iop_proof
148        let product_check_sub_claim =
149            <Self as ProductCheck<E, PCS>>::verify(proof, aux_info, transcript)?;
150
151        end_timer!(start);
152        Ok(PermutationCheckSubClaim {
153            product_check_sub_claim,
154            challenges: (beta, gamma),
155        })
156    }
157}
158
159#[cfg(test)]
160mod test {
161    use super::PermutationCheck;
162    use crate::{
163        pcs::{prelude::MultilinearKzgPCS, PolynomialCommitmentScheme},
164        poly_iop::{errors::PolyIOPErrors, PolyIOP},
165    };
166    use arithmetic::{evaluate_opt, identity_permutation_mle, random_permutation_mle, VPAuxInfo};
167    use ark_bls12_381::Bls12_381;
168    use ark_ec::PairingEngine;
169    use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
170    use ark_std::test_rng;
171    use std::{marker::PhantomData, rc::Rc};
172
173    type KZG = MultilinearKzgPCS<Bls12_381>;
174
175    fn test_permutation_check_helper<E, PCS>(
176        pcs_param: &PCS::ProverParam,
177        fx: &Rc<DenseMultilinearExtension<E::Fr>>,
178        gx: &Rc<DenseMultilinearExtension<E::Fr>>,
179        s_perm: &Rc<DenseMultilinearExtension<E::Fr>>,
180    ) -> Result<(), PolyIOPErrors>
181    where
182        E: PairingEngine,
183        PCS: PolynomialCommitmentScheme<E, Polynomial = Rc<DenseMultilinearExtension<E::Fr>>>,
184    {
185        let nv = fx.num_vars;
186        let poly_info = VPAuxInfo {
187            max_degree: 2,
188            num_variables: nv,
189            phantom: PhantomData::default(),
190        };
191
192        // prover
193        let mut transcript = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::init_transcript();
194        transcript.append_message(b"testing", b"initializing transcript for testing")?;
195        let (proof, prod_x) = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::prove(
196            pcs_param,
197            fx,
198            gx,
199            s_perm,
200            &mut transcript,
201        )?;
202
203        // verifier
204        let mut transcript = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::init_transcript();
205        transcript.append_message(b"testing", b"initializing transcript for testing")?;
206        let perm_check_sub_claim = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::verify(
207            &proof,
208            &poly_info,
209            &mut transcript,
210        )?;
211
212        // check product subclaim
213        if evaluate_opt(
214            &prod_x,
215            &perm_check_sub_claim.product_check_sub_claim.final_query.0,
216        ) != perm_check_sub_claim.product_check_sub_claim.final_query.1
217        {
218            return Err(PolyIOPErrors::InvalidVerifier("wrong subclaim".to_string()));
219        };
220
221        Ok(())
222    }
223
224    fn test_permutation_check(nv: usize) -> Result<(), PolyIOPErrors> {
225        let mut rng = test_rng();
226
227        let srs = MultilinearKzgPCS::<Bls12_381>::gen_srs_for_testing(&mut rng, nv + 1)?;
228        let (pcs_param, _) = MultilinearKzgPCS::<Bls12_381>::trim(&srs, None, Some(nv + 1))?;
229
230        {
231            // good path: w is a permutation of w itself under the identify map
232            let w = Rc::new(DenseMultilinearExtension::rand(nv, &mut rng));
233            // s_perm is the identity map
234            let s_perm = identity_permutation_mle(nv);
235            test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &w, &w, &s_perm)?;
236        }
237
238        {
239            // bad path 1: w is a not permutation of w itself under a random map
240            let w = Rc::new(DenseMultilinearExtension::rand(nv, &mut rng));
241            // s_perm is a random map
242            let s_perm = random_permutation_mle(nv, &mut rng);
243
244            assert!(
245                test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &w, &w, &s_perm)
246                    .is_err()
247            );
248        }
249
250        {
251            // bad path 2: f is a not permutation of g under a identity map
252            let f = Rc::new(DenseMultilinearExtension::rand(nv, &mut rng));
253            let g = Rc::new(DenseMultilinearExtension::rand(nv, &mut rng));
254            // s_perm is the identity map
255            let s_perm = identity_permutation_mle(nv);
256
257            assert!(
258                test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &f, &g, &s_perm)
259                    .is_err()
260            );
261        }
262
263        Ok(())
264    }
265
266    #[test]
267    fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
268        test_permutation_check(1)
269    }
270    #[test]
271    fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
272        test_permutation_check(5)
273    }
274
275    #[test]
276    fn zero_polynomial_should_error() -> Result<(), PolyIOPErrors> {
277        assert!(test_permutation_check(0).is_err());
278        Ok(())
279    }
280}