1// Copyright (c) 2022 Espresso Systems (espressosys.com)
  2// This file is part of the Jellyfish library.
  3
  4// You should have received a copy of the MIT License
  5// along with the Jellyfish library. If not, see <https://mit-license.org/>.
  6
  7//! Main module for multilinear KZG commitment scheme
  8
  9pub(crate) mod batching;
 10pub(crate) mod srs;
 11pub(crate) mod util;
 12
 13use crate::{
 14    pcs::{prelude::Commitment, PCSError, PolynomialCommitmentScheme, StructuredReferenceString},
 15    BatchProof,
 16};
 17use arithmetic::evaluate_opt;
 18use ark_ec::{
 19    msm::{FixedBaseMSM, VariableBaseMSM},
 20    AffineCurve, PairingEngine, ProjectiveCurve,
 21};
 22use ark_ff::PrimeField;
 23use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
 24use ark_serialize::{CanonicalDeserialize, CanonicalSerialize, Read, SerializationError, Write};
 25use ark_std::{
 26    borrow::Borrow,
 27    end_timer, format,
 28    marker::PhantomData,
 29    rand::{CryptoRng, RngCore},
 30    start_timer,
 31    string::ToString,
 32    sync::Arc,
 33    vec,
 34    vec::Vec,
 35    One, Zero,
 36};
 37// use batching::{batch_verify_internal, multi_open_internal};
 38use srs::{MultilinearProverParam, MultilinearUniversalParams, MultilinearVerifierParam};
 39use transcript::IOPTranscript;
 40
 41use self::batching::{batch_verify_internal, multi_open_internal};
 42
 43/// KZG Polynomial Commitment Scheme on multilinear polynomials.
 44pub struct MultilinearKzgPCS<E: PairingEngine> {
 45    #[doc(hidden)]
 46    phantom: PhantomData<E>,
 47}
 48
 49#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug, PartialEq, Eq)]
 50/// proof of opening
 51pub struct MultilinearKzgProof<E: PairingEngine> {
 52    /// Evaluation of quotients
 53    pub proofs: Vec<E::G1Affine>,
 54}
 55
 56impl<E: PairingEngine> PolynomialCommitmentScheme<E> for MultilinearKzgPCS<E> {
 57    // Parameters
 58    type ProverParam = MultilinearProverParam<E>;
 59    type VerifierParam = MultilinearVerifierParam<E>;
 60    type SRS = MultilinearUniversalParams<E>;
 61    // Polynomial and its associated types
 62    type Polynomial = Arc<DenseMultilinearExtension<E::Fr>>;
 63    type Point = Vec<E::Fr>;
 64    type Evaluation = E::Fr;
 65    // Commitments and proofs
 66    type Commitment = Commitment<E>;
 67    type Proof = MultilinearKzgProof<E>;
 68    type BatchProof = BatchProof<E, Self>;
 69
 70    /// Build SRS for testing.
 71    ///
 72    /// - For univariate polynomials, `log_size` is the log of maximum degree.
 73    /// - For multilinear polynomials, `log_size` is the number of variables.
 74    ///
 75    /// WARNING: THIS FUNCTION IS FOR TESTING PURPOSE ONLY.
 76    /// THE OUTPUT SRS SHOULD NOT BE USED IN PRODUCTION.
 77    fn gen_srs_for_testing<R: RngCore + CryptoRng>(
 78        rng: &mut R,
 79        log_size: usize,
 80    ) -> Result<Self::SRS, PCSError> {
 81        MultilinearUniversalParams::<E>::gen_srs_for_testing(rng, log_size)
 82    }
 83
 84    /// Trim the universal parameters to specialize the public parameters.
 85    /// Input both `supported_log_degree` for univariate and
 86    /// `supported_num_vars` for multilinear.
 87    fn trim(
 88        srs: impl Borrow<Self::SRS>,
 89        supported_degree: Option<usize>,
 90        supported_num_vars: Option<usize>,
 91    ) -> Result<(Self::ProverParam, Self::VerifierParam), PCSError> {
 92        assert!(supported_degree.is_none());
 93
 94        let supported_num_vars = match supported_num_vars {
 95            Some(p) => p,
 96            None => {
 97                return Err(PCSError::InvalidParameters(
 98                    "multilinear should receive a num_var param".to_string(),
 99                ))
100            },
101        };
102        let (ml_ck, ml_vk) = srs.borrow().trim(supported_num_vars)?;
103
104        Ok((ml_ck, ml_vk))
105    }
106
107    /// Generate a commitment for a polynomial.
108    ///
109    /// This function takes `2^num_vars` number of scalar multiplications over
110    /// G1.
111    fn commit(
112        prover_param: impl Borrow<Self::ProverParam>,
113        poly: &Self::Polynomial,
114    ) -> Result<Self::Commitment, PCSError> {
115        let prover_param = prover_param.borrow();
116        let commit_timer = start_timer!(|| "commit");
117        if prover_param.num_vars < poly.num_vars {
118            return Err(PCSError::InvalidParameters(format!(
119                "MlE length ({}) exceeds param limit ({})",
120                poly.num_vars, prover_param.num_vars
121            )));
122        }
123        let ignored = prover_param.num_vars - poly.num_vars;
124        let scalars: Vec<_> = poly
125            .to_evaluations()
126            .into_iter()
127            .map(|x| x.into_repr())
128            .collect();
129        let msm_timer = start_timer!(|| format!(
130            "msm of size {}",
131            prover_param.powers_of_g[ignored].evals.len()
132        ));
133        let commitment = VariableBaseMSM::multi_scalar_mul(
134            &prover_param.powers_of_g[ignored].evals,
135            scalars.as_slice(),
136        )
137        .into_affine();
138        end_timer!(msm_timer);
139
140        end_timer!(commit_timer);
141        Ok(Commitment(commitment))
142    }
143
144    /// On input a polynomial `p` and a point `point`, outputs a proof for the
145    /// same. This function does not need to take the evaluation value as an
146    /// input.
147    ///
148    /// This function takes 2^{num_var +1} number of scalar multiplications over
149    /// G1:
150    /// - it prodceeds with `num_var` number of rounds,
151    /// - at round i, we compute an MSM for `2^{num_var - i + 1}` number of G2
152    ///   elements.
153    fn open(
154        prover_param: impl Borrow<Self::ProverParam>,
155        polynomial: &Self::Polynomial,
156        point: &Self::Point,
157    ) -> Result<(Self::Proof, Self::Evaluation), PCSError> {
158        open_internal(prover_param.borrow(), polynomial, point)
159    }
160
161    /// Input a list of multilinear extensions, and a same number of points, and
162    /// a transcript, compute a multi-opening for all the polynomials.
163    fn multi_open(
164        prover_param: impl Borrow<Self::ProverParam>,
165        polynomials: &[Self::Polynomial],
166        points: &[Self::Point],
167        evals: &[Self::Evaluation],
168        transcript: &mut IOPTranscript<E::Fr>,
169    ) -> Result<BatchProof<E, Self>, PCSError> {
170        multi_open_internal(
171            prover_param.borrow(),
172            polynomials,
173            points,
174            evals,
175            transcript,
176        )
177    }
178
179    /// Verifies that `value` is the evaluation at `x` of the polynomial
180    /// committed inside `comm`.
181    ///
182    /// This function takes
183    /// - num_var number of pairing product.
184    /// - num_var number of MSM
185    fn verify(
186        verifier_param: &Self::VerifierParam,
187        commitment: &Self::Commitment,
188        point: &Self::Point,
189        value: &E::Fr,
190        proof: &Self::Proof,
191    ) -> Result<bool, PCSError> {
192        verify_internal(verifier_param, commitment, point, value, proof)
193    }
194
195    /// Verifies that `value_i` is the evaluation at `x_i` of the polynomial
196    /// `poly_i` committed inside `comm`.
197    fn batch_verify(
198        verifier_param: &Self::VerifierParam,
199        commitments: &[Self::Commitment],
200        points: &[Self::Point],
201        batch_proof: &Self::BatchProof,
202        transcript: &mut IOPTranscript<E::Fr>,
203    ) -> Result<bool, PCSError> {
204        batch_verify_internal(verifier_param, commitments, points, batch_proof, transcript)
205    }
206}
207
208/// On input a polynomial `p` and a point `point`, outputs a proof for the
209/// same. This function does not need to take the evaluation value as an
210/// input.
211///
212/// This function takes 2^{num_var} number of scalar multiplications over
213/// G1:
214/// - it proceeds with `num_var` number of rounds,
215/// - at round i, we compute an MSM for `2^{num_var - i}` number of G1 elements.
216fn open_internal<E: PairingEngine>(
217    prover_param: &MultilinearProverParam<E>,
218    polynomial: &DenseMultilinearExtension<E::Fr>,
219    point: &[E::Fr],
220) -> Result<(MultilinearKzgProof<E>, E::Fr), PCSError> {
221    let open_timer = start_timer!(|| format!("open mle with {} variable", polynomial.num_vars));
222
223    if polynomial.num_vars() > prover_param.num_vars {
224        return Err(PCSError::InvalidParameters(format!(
225            "Polynomial num_vars {} exceed the limit {}",
226            polynomial.num_vars, prover_param.num_vars
227        )));
228    }
229
230    if polynomial.num_vars() != point.len() {
231        return Err(PCSError::InvalidParameters(format!(
232            "Polynomial num_vars {} does not match point len {}",
233            polynomial.num_vars,
234            point.len()
235        )));
236    }
237
238    let nv = polynomial.num_vars();
239    // the first `ignored` SRS vectors are unused for opening.
240    let ignored = prover_param.num_vars - nv + 1;
241    let mut f = polynomial.to_evaluations();
242
243    let mut proofs = Vec::new();
244
245    for (i, (&point_at_k, gi)) in point
246        .iter()
247        .zip(prover_param.powers_of_g[ignored..ignored + nv].iter())
248        .enumerate()
249    {
250        let ith_round = start_timer!(|| format!("{}-th round", i));
251
252        let k = nv - 1 - i;
253        let cur_dim = 1 << k;
254        let mut q = vec![E::Fr::zero(); cur_dim];
255        let mut r = vec![E::Fr::zero(); cur_dim];
256
257        let ith_round_eval = start_timer!(|| format!("{}-th round eval", i));
258        for b in 0..(1 << k) {
259            // q[b] = f[1, b] - f[0, b]
260            q[b] = f[(b << 1) + 1] - f[b << 1];
261
262            // r[b] = f[0, b] + q[b] * p
263            r[b] = f[b << 1] + (q[b] * point_at_k);
264        }
265        f = r;
266        end_timer!(ith_round_eval);
267        let scalars: Vec<_> = q.iter().map(|x| x.into_repr()).collect();
268
269        // this is a MSM over G1 and is likely to be the bottleneck
270        let msm_timer = start_timer!(|| format!("msm of size {} at round {}", gi.evals.len(), i));
271
272        proofs.push(VariableBaseMSM::multi_scalar_mul(&gi.evals, &scalars).into_affine());
273        end_timer!(msm_timer);
274
275        end_timer!(ith_round);
276    }
277    let eval = evaluate_opt(polynomial, point);
278    end_timer!(open_timer);
279    Ok((MultilinearKzgProof { proofs }, eval))
280}
281
282/// Verifies that `value` is the evaluation at `x` of the polynomial
283/// committed inside `comm`.
284///
285/// This function takes
286/// - num_var number of pairing product.
287/// - num_var number of MSM
288fn verify_internal<E: PairingEngine>(
289    verifier_param: &MultilinearVerifierParam<E>,
290    commitment: &Commitment<E>,
291    point: &[E::Fr],
292    value: &E::Fr,
293    proof: &MultilinearKzgProof<E>,
294) -> Result<bool, PCSError> {
295    let verify_timer = start_timer!(|| "verify");
296    let num_var = point.len();
297
298    if num_var > verifier_param.num_vars {
299        return Err(PCSError::InvalidParameters(format!(
300            "point length ({}) exceeds param limit ({})",
301            num_var, verifier_param.num_vars
302        )));
303    }
304
305    let prepare_inputs_timer = start_timer!(|| "prepare pairing inputs");
306
307    let scalar_size = E::Fr::size_in_bits();
308    let window_size = FixedBaseMSM::get_mul_window_size(num_var);
309
310    let h_table = FixedBaseMSM::get_window_table(
311        scalar_size,
312        window_size,
313        verifier_param.h.into_projective(),
314    );
315    let h_mul: Vec<E::G2Projective> =
316        FixedBaseMSM::multi_scalar_mul(scalar_size, window_size, &h_table, point);
317
318    let ignored = verifier_param.num_vars - num_var;
319    let h_vec: Vec<_> = (0..num_var)
320        .map(|i| verifier_param.h_mask[ignored + i].into_projective() - h_mul[i])
321        .collect();
322    let h_vec: Vec<E::G2Affine> = E::G2Projective::batch_normalization_into_affine(&h_vec);
323    end_timer!(prepare_inputs_timer);
324
325    let pairing_product_timer = start_timer!(|| "pairing product");
326
327    let mut pairings: Vec<_> = proof
328        .proofs
329        .iter()
330        .map(|&x| E::G1Prepared::from(x))
331        .zip(h_vec.into_iter().take(num_var).map(E::G2Prepared::from))
332        .collect();
333
334    pairings.push((
335        E::G1Prepared::from(
336            (verifier_param.g.mul(*value) - commitment.0.into_projective()).into_affine(),
337        ),
338        E::G2Prepared::from(verifier_param.h),
339    ));
340
341    let res = E::product_of_pairings(pairings.iter()) == E::Fqk::one();
342
343    end_timer!(pairing_product_timer);
344    end_timer!(verify_timer);
345    Ok(res)
346}
347
348#[cfg(test)]
349mod tests {
350    use super::*;
351    use ark_bls12_381::Bls12_381;
352    use ark_ec::PairingEngine;
353    use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
354    use ark_std::{rand::RngCore, test_rng, vec::Vec, UniformRand};
355
356    type E = Bls12_381;
357    type Fr = <E as PairingEngine>::Fr;
358
359    fn test_single_helper<R: RngCore + CryptoRng>(
360        params: &MultilinearUniversalParams<E>,
361        poly: &Arc<DenseMultilinearExtension<Fr>>,
362        rng: &mut R,
363    ) -> Result<(), PCSError> {
364        let nv = poly.num_vars();
365        assert_ne!(nv, 0);
366        let (ck, vk) = MultilinearKzgPCS::trim(params, None, Some(nv))?;
367        let point: Vec<_> = (0..nv).map(|_| Fr::rand(rng)).collect();
368        let com = MultilinearKzgPCS::commit(&ck, poly)?;
369        let (proof, value) = MultilinearKzgPCS::open(&ck, poly, &point)?;
370
371        assert!(MultilinearKzgPCS::verify(
372            &vk, &com, &point, &value, &proof
373        )?);
374
375        let value = Fr::rand(rng);
376        assert!(!MultilinearKzgPCS::verify(
377            &vk, &com, &point, &value, &proof
378        )?);
379
380        Ok(())
381    }
382
383    #[test]
384    fn test_single_commit() -> Result<(), PCSError> {
385        let mut rng = test_rng();
386
387        let params = MultilinearKzgPCS::<E>::gen_srs_for_testing(&mut rng, 10)?;
388
389        // normal polynomials
390        let poly1 = Arc::new(DenseMultilinearExtension::rand(8, &mut rng));
391        test_single_helper(&params, &poly1, &mut rng)?;
392
393        // single-variate polynomials
394        let poly2 = Arc::new(DenseMultilinearExtension::rand(1, &mut rng));
395        test_single_helper(&params, &poly2, &mut rng)?;
396
397        Ok(())
398    }
399
400    #[test]
401    fn setup_commit_verify_constant_polynomial() {
402        let mut rng = test_rng();
403
404        // normal polynomials
405        assert!(MultilinearKzgPCS::<E>::gen_srs_for_testing(&mut rng, 0).is_err());
406    }
407}