1//! Main module for the Permutation Check protocol
  2
  3use self::util::computer_nums_and_denoms;
  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. `(fs, gs, perms)`
 33/// proves that (g1, ..., gk) is a permutation of (f1, ..., fk) under
 34/// permutation `(p1, ..., pk)`
 35/// It is derived from ProductCheck.
 36///
 37/// A Permutation Check IOP takes the following steps:
 38///
 39/// Inputs:
 40/// - fs = (f1, ..., fk)
 41/// - gs = (g1, ..., gk)
 42/// - permutation oracles = (p1, ..., pk)
 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    /// - fs = (f1, ..., fk)
 61    /// - gs = (g1, ..., gk)
 62    /// - permutation oracles = (p1, ..., pk)
 63    /// Outputs:
 64    /// - a permutation check proof proving that gs is a permutation of fs under
 65    ///   permutation
 66    /// - the product polynomial build during product check (for testing)
 67    ///
 68    /// Cost: O(N)
 69    fn prove(
 70        pcs_param: &PCS::ProverParam,
 71        fxs: &[Self::MultilinearExtension],
 72        gxs: &[Self::MultilinearExtension],
 73        perms: &[Self::MultilinearExtension],
 74        transcript: &mut IOPTranscript<E::Fr>,
 75    ) -> Result<(Self::PermutationProof, Self::MultilinearExtension), PolyIOPErrors>;
 76
 77    /// Verify that (g1, ..., gk) is a permutation of
 78    /// (f1, ..., fk) over the permutation oracles (perm1, ..., permk)
 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        fxs: &[Self::MultilinearExtension],
101        gxs: &[Self::MultilinearExtension],
102        perms: &[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 fxs.is_empty() {
107            return Err(PolyIOPErrors::InvalidParameters("fxs is empty".to_string()));
108        }
109        if (fxs.len() != gxs.len()) || (fxs.len() != perms.len()) {
110            return Err(PolyIOPErrors::InvalidProof(format!(
111                "fxs.len() = {}, gxs.len() = {}, perms.len() = {}",
112                fxs.len(),
113                gxs.len(),
114                perms.len(),
115            )));
116        }
117
118        let num_vars = fxs[0].num_vars;
119        for ((fx, gx), perm) in fxs.iter().zip(gxs.iter()).zip(perms.iter()) {
120            if (fx.num_vars != num_vars) || (gx.num_vars != num_vars) || (perm.num_vars != num_vars)
121            {
122                return Err(PolyIOPErrors::InvalidParameters(
123                    "number of variables unmatched".to_string(),
124                ));
125            }
126        }
127
128        // generate challenge `beta` and `gamma` from current transcript
129        let beta = transcript.get_and_append_challenge(b"beta")?;
130        let gamma = transcript.get_and_append_challenge(b"gamma")?;
131        let (numerators, denominators) = computer_nums_and_denoms(&beta, &gamma, fxs, gxs, perms)?;
132
133        // invoke product check on numerator and denominator
134        let (proof, prod_poly, _) = <Self as ProductCheck<E, PCS>>::prove(
135            pcs_param,
136            &numerators,
137            &denominators,
138            transcript,
139        )?;
140
141        end_timer!(start);
142        Ok((proof, prod_poly))
143    }
144
145    fn verify(
146        proof: &Self::PermutationProof,
147        aux_info: &Self::VPAuxInfo,
148        transcript: &mut Self::Transcript,
149    ) -> Result<Self::PermutationCheckSubClaim, PolyIOPErrors> {
150        let start = start_timer!(|| "Permutation check verify");
151
152        let beta = transcript.get_and_append_challenge(b"beta")?;
153        let gamma = transcript.get_and_append_challenge(b"gamma")?;
154
155        // invoke the zero check on the iop_proof
156        let product_check_sub_claim =
157            <Self as ProductCheck<E, PCS>>::verify(proof, aux_info, transcript)?;
158
159        end_timer!(start);
160        Ok(PermutationCheckSubClaim {
161            product_check_sub_claim,
162            challenges: (beta, gamma),
163        })
164    }
165}
166
167#[cfg(test)]
168mod test {
169    use super::PermutationCheck;
170    use crate::{
171        pcs::{prelude::MultilinearKzgPCS, PolynomialCommitmentScheme},
172        poly_iop::{errors::PolyIOPErrors, PolyIOP},
173    };
174    use arithmetic::{evaluate_opt, identity_permutation_mles, random_permutation_mles, VPAuxInfo};
175    use ark_bls12_381::Bls12_381;
176    use ark_ec::PairingEngine;
177    use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
178    use ark_std::test_rng;
179    use std::{marker::PhantomData, rc::Rc};
180
181    type KZG = MultilinearKzgPCS<Bls12_381>;
182
183    fn test_permutation_check_helper<E, PCS>(
184        pcs_param: &PCS::ProverParam,
185        fxs: &[Rc<DenseMultilinearExtension<E::Fr>>],
186        gxs: &[Rc<DenseMultilinearExtension<E::Fr>>],
187        perms: &[Rc<DenseMultilinearExtension<E::Fr>>],
188    ) -> Result<(), PolyIOPErrors>
189    where
190        E: PairingEngine,
191        PCS: PolynomialCommitmentScheme<E, Polynomial = Rc<DenseMultilinearExtension<E::Fr>>>,
192    {
193        let nv = fxs[0].num_vars;
194        // what's AuxInfo used for?
195        let poly_info = VPAuxInfo {
196            max_degree: fxs.len() + 1,
197            num_variables: nv,
198            phantom: PhantomData::default(),
199        };
200
201        // prover
202        let mut transcript = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::init_transcript();
203        transcript.append_message(b"testing", b"initializing transcript for testing")?;
204        let (proof, prod_x) = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::prove(
205            pcs_param,
206            fxs,
207            gxs,
208            perms,
209            &mut transcript,
210        )?;
211
212        // verifier
213        let mut transcript = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::init_transcript();
214        transcript.append_message(b"testing", b"initializing transcript for testing")?;
215        let perm_check_sub_claim = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::verify(
216            &proof,
217            &poly_info,
218            &mut transcript,
219        )?;
220
221        // check product subclaim
222        if evaluate_opt(
223            &prod_x,
224            &perm_check_sub_claim.product_check_sub_claim.final_query.0,
225        ) != perm_check_sub_claim.product_check_sub_claim.final_query.1
226        {
227            return Err(PolyIOPErrors::InvalidVerifier("wrong subclaim".to_string()));
228        };
229
230        Ok(())
231    }
232
233    fn test_permutation_check(nv: usize) -> Result<(), PolyIOPErrors> {
234        let mut rng = test_rng();
235
236        let srs = MultilinearKzgPCS::<Bls12_381>::gen_srs_for_testing(&mut rng, nv)?;
237        let (pcs_param, _) = MultilinearKzgPCS::<Bls12_381>::trim(&srs, None, Some(nv))?;
238        let id_perms = identity_permutation_mles(nv, 2);
239
240        {
241            // good path: (w1, w2) is a permutation of (w1, w2) itself under the identify
242            // map
243            let ws = vec![
244                Rc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
245                Rc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
246            ];
247            // perms is the identity map
248            test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &ws, &ws, &id_perms)?;
249        }
250
251        {
252            // good path: f = (w1, w2) is a permutation of g = (w2, w1) itself under a map
253            let mut fs = vec![
254                Rc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
255                Rc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
256            ];
257            let gs = fs.clone();
258            fs.reverse();
259            // perms is the reverse identity map
260            let mut perms = id_perms.clone();
261            perms.reverse();
262            test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &fs, &gs, &perms)?;
263        }
264
265        {
266            // bad path 1: w is a not permutation of w itself under a random map
267            let ws = vec![
268                Rc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
269                Rc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
270            ];
271            // perms is a random map
272            let perms = random_permutation_mles(nv, 2, &mut rng);
273
274            assert!(
275                test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &ws, &ws, &perms)
276                    .is_err()
277            );
278        }
279
280        {
281            // bad path 2: f is a not permutation of g under a identity map
282            let fs = vec![
283                Rc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
284                Rc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
285            ];
286            let gs = vec![
287                Rc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
288                Rc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
289            ];
290            // s_perm is the identity map
291
292            assert!(test_permutation_check_helper::<Bls12_381, KZG>(
293                &pcs_param, &fs, &gs, &id_perms
294            )
295            .is_err());
296        }
297
298        Ok(())
299    }
300
301    #[test]
302    fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
303        test_permutation_check(1)
304    }
305    #[test]
306    fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
307        test_permutation_check(5)
308    }
309
310    #[test]
311    fn zero_polynomial_should_error() -> Result<(), PolyIOPErrors> {
312        assert!(test_permutation_check(0).is_err());
313        Ok(())
314    }
315}