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) =
125            <Self as ProductCheck<E, PCS>>::prove(pcs_param, &numerator, &denominator, transcript)?;
126
127        end_timer!(start);
128        Ok((proof, prod_poly))
129    }
130
131    /// Verify that an MLE g(x) is a permutation of an
132    /// MLE f(x) over a permutation given by s_perm.
133    fn verify(
134        proof: &Self::PermutationProof,
135        aux_info: &Self::VPAuxInfo,
136        transcript: &mut Self::Transcript,
137    ) -> Result<Self::PermutationCheckSubClaim, PolyIOPErrors> {
138        let start = start_timer!(|| "Permutation check verify");
139
140        let beta = transcript.get_and_append_challenge(b"beta")?;
141        let gamma = transcript.get_and_append_challenge(b"gamma")?;
142
143        // invoke the zero check on the iop_proof
144        let product_check_sub_claim =
145            <Self as ProductCheck<E, PCS>>::verify(proof, aux_info, transcript)?;
146
147        end_timer!(start);
148        Ok(PermutationCheckSubClaim {
149            product_check_sub_claim,
150            challenges: (beta, gamma),
151        })
152    }
153}
154
155#[cfg(test)]
156mod test {
157    use super::PermutationCheck;
158    use crate::{
159        pcs::{prelude::MultilinearKzgPCS, PolynomialCommitmentScheme},
160        poly_iop::{errors::PolyIOPErrors, PolyIOP},
161    };
162    use arithmetic::{evaluate_opt, identity_permutation_mle, random_permutation_mle, VPAuxInfo};
163    use ark_bls12_381::Bls12_381;
164    use ark_ec::PairingEngine;
165    use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
166    use ark_std::test_rng;
167    use std::{marker::PhantomData, rc::Rc};
168
169    type KZG = MultilinearKzgPCS<Bls12_381>;
170
171    fn test_permutation_check_helper<E, PCS>(
172        pcs_param: &PCS::ProverParam,
173        fx: &Rc<DenseMultilinearExtension<E::Fr>>,
174        gx: &Rc<DenseMultilinearExtension<E::Fr>>,
175        s_perm: &Rc<DenseMultilinearExtension<E::Fr>>,
176    ) -> Result<(), PolyIOPErrors>
177    where
178        E: PairingEngine,
179        PCS: PolynomialCommitmentScheme<E, Polynomial = Rc<DenseMultilinearExtension<E::Fr>>>,
180    {
181        let nv = fx.num_vars;
182        let poly_info = VPAuxInfo {
183            max_degree: 2,
184            num_variables: nv,
185            phantom: PhantomData::default(),
186        };
187
188        // prover
189        let mut transcript = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::init_transcript();
190        transcript.append_message(b"testing", b"initializing transcript for testing")?;
191        let (proof, prod_x) = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::prove(
192            pcs_param,
193            fx,
194            gx,
195            s_perm,
196            &mut transcript,
197        )?;
198
199        // verifier
200        let mut transcript = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::init_transcript();
201        transcript.append_message(b"testing", b"initializing transcript for testing")?;
202        let perm_check_sub_claim = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::verify(
203            &proof,
204            &poly_info,
205            &mut transcript,
206        )?;
207
208        // check product subclaim
209        if evaluate_opt(
210            &prod_x,
211            &perm_check_sub_claim.product_check_sub_claim.final_query.0,
212        ) != perm_check_sub_claim.product_check_sub_claim.final_query.1
213        {
214            return Err(PolyIOPErrors::InvalidVerifier("wrong subclaim".to_string()));
215        };
216
217        Ok(())
218    }
219
220    fn test_permutation_check(nv: usize) -> Result<(), PolyIOPErrors> {
221        let mut rng = test_rng();
222
223        let srs = MultilinearKzgPCS::<Bls12_381>::gen_srs_for_testing(&mut rng, nv + 1)?;
224        let (pcs_param, _) = MultilinearKzgPCS::<Bls12_381>::trim(&srs, None, Some(nv + 1))?;
225
226        {
227            // good path: w is a permutation of w itself under the identify map
228            let w = Rc::new(DenseMultilinearExtension::rand(nv, &mut rng));
229            // s_perm is the identity map
230            let s_perm = identity_permutation_mle(nv);
231            test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &w, &w, &s_perm)?;
232        }
233
234        {
235            // bad path 1: w is a not permutation of w itself under a random map
236            let w = Rc::new(DenseMultilinearExtension::rand(nv, &mut rng));
237            // s_perm is a random map
238            let s_perm = random_permutation_mle(nv, &mut rng);
239
240            assert!(
241                test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &w, &w, &s_perm)
242                    .is_err()
243            );
244        }
245
246        {
247            // bad path 2: f is a not permutation of g under a identity map
248            let f = Rc::new(DenseMultilinearExtension::rand(nv, &mut rng));
249            let g = Rc::new(DenseMultilinearExtension::rand(nv, &mut rng));
250            // s_perm is the identity map
251            let s_perm = identity_permutation_mle(nv);
252
253            assert!(
254                test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &f, &g, &s_perm)
255                    .is_err()
256            );
257        }
258
259        Ok(())
260    }
261
262    #[test]
263    fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
264        test_permutation_check(1)
265    }
266    #[test]
267    fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
268        test_permutation_check(5)
269    }
270
271    #[test]
272    fn zero_polynomial_should_error() -> Result<(), PolyIOPErrors> {
273        assert!(test_permutation_check(0).is_err());
274        Ok(())
275    }
276}