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