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