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