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 jf_primitives::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::{
157        errors::PolyIOPErrors,
158        prelude::{identity_permutation_mle, random_permutation_mle},
159        PolyIOP,
160    };
161    use arithmetic::VPAuxInfo;
162    use ark_bls12_381::Bls12_381;
163    use ark_ec::PairingEngine;
164    use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
165    use ark_std::test_rng;
166    use jf_primitives::pcs::{prelude::MultilinearKzgPCS, PolynomialCommitmentScheme};
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 prod_x
210            .evaluate(&perm_check_sub_claim.product_check_sub_claim.final_query.0)
211            .unwrap()
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, nv + 1, 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            if nv == 1 {
241                test_permutation_check_helper::<Bls12_381, Kzg>(&pcs_param, &w, &w, &s_perm)?;
242            } else {
243                assert!(test_permutation_check_helper::<Bls12_381, Kzg>(
244                    &pcs_param, &w, &w, &s_perm
245                )
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}