1// Copyright (c) 2023 Espresso Systems (espressosys.com)
  2// This file is part of the HyperPlonk library.
  3
  4// You should have received a copy of the MIT License
  5// along with the HyperPlonk library. If not, see <https://mit-license.org/>.
  6
  7//! Main module for the Permutation Check protocol
  8
  9use self::util::computer_nums_and_denoms;
 10use crate::{
 11    pcs::PolynomialCommitmentScheme,
 12    poly_iop::{errors::PolyIOPErrors, prelude::ProductCheck, PolyIOP},
 13};
 14use ark_ec::PairingEngine;
 15use ark_poly::DenseMultilinearExtension;
 16use ark_std::{end_timer, start_timer};
 17use std::sync::Arc;
 18use transcript::IOPTranscript;
 19
 20/// A permutation subclaim consists of
 21/// - the SubClaim from the ProductCheck
 22/// - Challenges beta and gamma
 23#[derive(Clone, Debug, Default, PartialEq)]
 24pub struct PermutationCheckSubClaim<E, PCS, PC>
 25where
 26    E: PairingEngine,
 27    PC: ProductCheck<E, PCS>,
 28    PCS: PolynomialCommitmentScheme<E>,
 29{
 30    /// the SubClaim from the ProductCheck
 31    pub product_check_sub_claim: PC::ProductCheckSubClaim,
 32    /// Challenges beta and gamma
 33    pub challenges: (E::Fr, E::Fr),
 34}
 35
 36pub mod util;
 37
 38/// A PermutationCheck w.r.t. `(fs, gs, perms)`
 39/// proves that (g1, ..., gk) is a permutation of (f1, ..., fk) under
 40/// permutation `(p1, ..., pk)`
 41/// It is derived from ProductCheck.
 42///
 43/// A Permutation Check IOP takes the following steps:
 44///
 45/// Inputs:
 46/// - fs = (f1, ..., fk)
 47/// - gs = (g1, ..., gk)
 48/// - permutation oracles = (p1, ..., pk)
 49pub trait PermutationCheck<E, PCS>: ProductCheck<E, PCS>
 50where
 51    E: PairingEngine,
 52    PCS: PolynomialCommitmentScheme<E>,
 53{
 54    type PermutationCheckSubClaim;
 55    type PermutationProof;
 56
 57    /// Initialize the system with a transcript
 58    ///
 59    /// This function is optional -- in the case where a PermutationCheck is
 60    /// an building block for a more complex protocol, the transcript
 61    /// may be initialized by this complex protocol, and passed to the
 62    /// PermutationCheck prover/verifier.
 63    fn init_transcript() -> Self::Transcript;
 64
 65    /// Inputs:
 66    /// - fs = (f1, ..., fk)
 67    /// - gs = (g1, ..., gk)
 68    /// - permutation oracles = (p1, ..., pk)
 69    /// Outputs:
 70    /// - a permutation check proof proving that gs is a permutation of fs under
 71    ///   permutation
 72    /// - the product polynomial built during product check
 73    /// - the fractional polynomial built during product check
 74    ///
 75    /// Cost: O(N)
 76    #[allow(clippy::type_complexity)]
 77    fn prove(
 78        pcs_param: &PCS::ProverParam,
 79        fxs: &[Self::MultilinearExtension],
 80        gxs: &[Self::MultilinearExtension],
 81        perms: &[Self::MultilinearExtension],
 82        transcript: &mut IOPTranscript<E::Fr>,
 83    ) -> Result<
 84        (
 85            Self::PermutationProof,
 86            Self::MultilinearExtension,
 87            Self::MultilinearExtension,
 88        ),
 89        PolyIOPErrors,
 90    >;
 91
 92    /// Verify that (g1, ..., gk) is a permutation of
 93    /// (f1, ..., fk) over the permutation oracles (perm1, ..., permk)
 94    fn verify(
 95        proof: &Self::PermutationProof,
 96        aux_info: &Self::VPAuxInfo,
 97        transcript: &mut Self::Transcript,
 98    ) -> Result<Self::PermutationCheckSubClaim, PolyIOPErrors>;
 99}
100
101impl<E, PCS> PermutationCheck<E, PCS> for PolyIOP<E::Fr>
102where
103    E: PairingEngine,
104    PCS: PolynomialCommitmentScheme<E, Polynomial = Arc<DenseMultilinearExtension<E::Fr>>>,
105{
106    type PermutationCheckSubClaim = PermutationCheckSubClaim<E, PCS, Self>;
107    type PermutationProof = Self::ProductCheckProof;
108
109    fn init_transcript() -> Self::Transcript {
110        IOPTranscript::<E::Fr>::new(b"Initializing PermutationCheck transcript")
111    }
112
113    fn prove(
114        pcs_param: &PCS::ProverParam,
115        fxs: &[Self::MultilinearExtension],
116        gxs: &[Self::MultilinearExtension],
117        perms: &[Self::MultilinearExtension],
118        transcript: &mut IOPTranscript<E::Fr>,
119    ) -> Result<
120        (
121            Self::PermutationProof,
122            Self::MultilinearExtension,
123            Self::MultilinearExtension,
124        ),
125        PolyIOPErrors,
126    > {
127        let start = start_timer!(|| "Permutation check prove");
128        if fxs.is_empty() {
129            return Err(PolyIOPErrors::InvalidParameters("fxs is empty".to_string()));
130        }
131        if (fxs.len() != gxs.len()) || (fxs.len() != perms.len()) {
132            return Err(PolyIOPErrors::InvalidProof(format!(
133                "fxs.len() = {}, gxs.len() = {}, perms.len() = {}",
134                fxs.len(),
135                gxs.len(),
136                perms.len(),
137            )));
138        }
139
140        let num_vars = fxs[0].num_vars;
141        for ((fx, gx), perm) in fxs.iter().zip(gxs.iter()).zip(perms.iter()) {
142            if (fx.num_vars != num_vars) || (gx.num_vars != num_vars) || (perm.num_vars != num_vars)
143            {
144                return Err(PolyIOPErrors::InvalidParameters(
145                    "number of variables unmatched".to_string(),
146                ));
147            }
148        }
149
150        // generate challenge `beta` and `gamma` from current transcript
151        let beta = transcript.get_and_append_challenge(b"beta")?;
152        let gamma = transcript.get_and_append_challenge(b"gamma")?;
153        let (numerators, denominators) = computer_nums_and_denoms(&beta, &gamma, fxs, gxs, perms)?;
154
155        // invoke product check on numerator and denominator
156        let (proof, prod_poly, frac_poly) = <Self as ProductCheck<E, PCS>>::prove(
157            pcs_param,
158            &numerators,
159            &denominators,
160            transcript,
161        )?;
162
163        end_timer!(start);
164        Ok((proof, prod_poly, frac_poly))
165    }
166
167    fn verify(
168        proof: &Self::PermutationProof,
169        aux_info: &Self::VPAuxInfo,
170        transcript: &mut Self::Transcript,
171    ) -> Result<Self::PermutationCheckSubClaim, PolyIOPErrors> {
172        let start = start_timer!(|| "Permutation check verify");
173
174        let beta = transcript.get_and_append_challenge(b"beta")?;
175        let gamma = transcript.get_and_append_challenge(b"gamma")?;
176
177        // invoke the zero check on the iop_proof
178        let product_check_sub_claim =
179            <Self as ProductCheck<E, PCS>>::verify(proof, aux_info, transcript)?;
180
181        end_timer!(start);
182        Ok(PermutationCheckSubClaim {
183            product_check_sub_claim,
184            challenges: (beta, gamma),
185        })
186    }
187}
188
189#[cfg(test)]
190mod test {
191    use super::PermutationCheck;
192    use crate::{
193        pcs::{prelude::MultilinearKzgPCS, PolynomialCommitmentScheme},
194        poly_iop::{errors::PolyIOPErrors, PolyIOP},
195    };
196    use arithmetic::{evaluate_opt, identity_permutation_mles, random_permutation_mles, VPAuxInfo};
197    use ark_bls12_381::Bls12_381;
198    use ark_ec::PairingEngine;
199    use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
200    use ark_std::test_rng;
201    use std::{marker::PhantomData, sync::Arc};
202
203    type KZG = MultilinearKzgPCS<Bls12_381>;
204
205    fn test_permutation_check_helper<E, PCS>(
206        pcs_param: &PCS::ProverParam,
207        fxs: &[Arc<DenseMultilinearExtension<E::Fr>>],
208        gxs: &[Arc<DenseMultilinearExtension<E::Fr>>],
209        perms: &[Arc<DenseMultilinearExtension<E::Fr>>],
210    ) -> Result<(), PolyIOPErrors>
211    where
212        E: PairingEngine,
213        PCS: PolynomialCommitmentScheme<E, Polynomial = Arc<DenseMultilinearExtension<E::Fr>>>,
214    {
215        let nv = fxs[0].num_vars;
216        // what's AuxInfo used for?
217        let poly_info = VPAuxInfo {
218            max_degree: fxs.len() + 1,
219            num_variables: nv,
220            phantom: PhantomData::default(),
221        };
222
223        // prover
224        let mut transcript = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::init_transcript();
225        transcript.append_message(b"testing", b"initializing transcript for testing")?;
226        let (proof, prod_x, _frac_poly) = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::prove(
227            pcs_param,
228            fxs,
229            gxs,
230            perms,
231            &mut transcript,
232        )?;
233
234        // verifier
235        let mut transcript = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::init_transcript();
236        transcript.append_message(b"testing", b"initializing transcript for testing")?;
237        let perm_check_sub_claim = <PolyIOP<E::Fr> as PermutationCheck<E, PCS>>::verify(
238            &proof,
239            &poly_info,
240            &mut transcript,
241        )?;
242
243        // check product subclaim
244        if evaluate_opt(
245            &prod_x,
246            &perm_check_sub_claim.product_check_sub_claim.final_query.0,
247        ) != perm_check_sub_claim.product_check_sub_claim.final_query.1
248        {
249            return Err(PolyIOPErrors::InvalidVerifier("wrong subclaim".to_string()));
250        };
251
252        Ok(())
253    }
254
255    fn test_permutation_check(nv: usize) -> Result<(), PolyIOPErrors> {
256        let mut rng = test_rng();
257
258        let srs = MultilinearKzgPCS::<Bls12_381>::gen_srs_for_testing(&mut rng, nv)?;
259        let (pcs_param, _) = MultilinearKzgPCS::<Bls12_381>::trim(&srs, None, Some(nv))?;
260        let id_perms = identity_permutation_mles(nv, 2);
261
262        {
263            // good path: (w1, w2) is a permutation of (w1, w2) itself under the identify
264            // map
265            let ws = vec![
266                Arc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
267                Arc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
268            ];
269            // perms is the identity map
270            test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &ws, &ws, &id_perms)?;
271        }
272
273        {
274            // good path: f = (w1, w2) is a permutation of g = (w2, w1) itself under a map
275            let mut fs = vec![
276                Arc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
277                Arc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
278            ];
279            let gs = fs.clone();
280            fs.reverse();
281            // perms is the reverse identity map
282            let mut perms = id_perms.clone();
283            perms.reverse();
284            test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &fs, &gs, &perms)?;
285        }
286
287        {
288            // bad path 1: w is a not permutation of w itself under a random map
289            let ws = vec![
290                Arc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
291                Arc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
292            ];
293            // perms is a random map
294            let perms = random_permutation_mles(nv, 2, &mut rng);
295
296            assert!(
297                test_permutation_check_helper::<Bls12_381, KZG>(&pcs_param, &ws, &ws, &perms)
298                    .is_err()
299            );
300        }
301
302        {
303            // bad path 2: f is a not permutation of g under a identity map
304            let fs = vec![
305                Arc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
306                Arc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
307            ];
308            let gs = vec![
309                Arc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
310                Arc::new(DenseMultilinearExtension::rand(nv, &mut rng)),
311            ];
312            // s_perm is the identity map
313
314            assert!(test_permutation_check_helper::<Bls12_381, KZG>(
315                &pcs_param, &fs, &gs, &id_perms
316            )
317            .is_err());
318        }
319
320        Ok(())
321    }
322
323    #[test]
324    fn test_trivial_polynomial() -> Result<(), PolyIOPErrors> {
325        test_permutation_check(1)
326    }
327    #[test]
328    fn test_normal_polynomial() -> Result<(), PolyIOPErrors> {
329        test_permutation_check(5)
330    }
331
332    #[test]
333    fn zero_polynomial_should_error() -> Result<(), PolyIOPErrors> {
334        assert!(test_permutation_check(0).is_err());
335        Ok(())
336    }
337}