jf_pcs/multilinear_kzg/
mod.rs

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
9mod batching;
10pub(crate) mod srs;
11pub(crate) mod util;
12
13use crate::{
14    prelude::{Commitment, UnivariateUniversalParams},
15    univariate_kzg::UnivariateKzgProof,
16    PCSError, PolynomialCommitmentScheme, StructuredReferenceString,
17};
18#[cfg(target_has_atomic = "ptr")]
19use alloc::sync::Arc;
20use ark_ec::{
21    pairing::Pairing, scalar_mul::variable_base::VariableBaseMSM, AffineRepr, CurveGroup, ScalarMul,
22};
23use ark_ff::PrimeField;
24use ark_poly::{DenseMultilinearExtension, MultilinearExtension, Polynomial};
25use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
26use ark_std::{
27    borrow::Borrow,
28    end_timer, format,
29    marker::PhantomData,
30    rand::{CryptoRng, RngCore},
31    start_timer,
32    string::ToString,
33    vec,
34    vec::Vec,
35    One, Zero,
36};
37use batching::{batch_open_internal, batch_verify_internal};
38use srs::{MultilinearProverParam, MultilinearUniversalParams, MultilinearVerifierParam};
39use util::merge_polynomials;
40
41// type alias for SRS
42type Srs<E> = (MultilinearUniversalParams<E>, UnivariateUniversalParams<E>);
43type ProverParam<E> = <Srs<E> as StructuredReferenceString>::ProverParam;
44type VerifierParam<E> = <Srs<E> as StructuredReferenceString>::VerifierParam;
45
46/// KZG Polynomial Commitment Scheme on multilinear polynomials.
47pub struct MultilinearKzgPCS<E: Pairing> {
48    #[doc(hidden)]
49    phantom: PhantomData<E>,
50}
51
52#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize, Clone, Debug, PartialEq, Eq)]
53#[derivative(Hash)]
54/// proof of opening
55pub struct MultilinearKzgProof<E: Pairing> {
56    /// Evaluation of quotients
57    pub proofs: Vec<E::G1Affine>,
58}
59
60#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug, PartialEq, Eq)]
61/// proof of batch opening
62pub struct MultilinearKzgBatchProof<E: Pairing> {
63    /// The actual proof
64    pub proof: MultilinearKzgProof<E>,
65    /// Commitment to q(x):= w(l(x)) where
66    /// - `w` is the merged MLE
67    /// - `l` is the list of univariate polys that goes through all points
68    pub q_x_commit: Commitment<E>,
69    /// openings of q(x) at 1, omega, ..., and r
70    pub q_x_opens: Vec<UnivariateKzgProof<E>>,
71}
72
73/// Multi-linear Extension (MLE) polynomial, this type alias is set to owned
74/// `DenseMultilinearExtension` on wasm platforms since only message-passing
75/// concurrency is supported. And set to `Arc<DenseMultilinearExtension>` for
76/// platforms that supports atomic operations (e.g. mostly non-wasm, MIPS, x86
77/// etc.)
78#[cfg(target_has_atomic = "ptr")]
79pub type MLE<F> = Arc<DenseMultilinearExtension<F>>;
80#[cfg(not(target_has_atomic = "ptr"))]
81pub type MLE<F> = DenseMultilinearExtension<F>;
82
83impl<E: Pairing> PolynomialCommitmentScheme for MultilinearKzgPCS<E> {
84    // Config
85    type SRS = Srs<E>;
86    // Polynomial and its associated types
87    type Polynomial = MLE<E::ScalarField>;
88    type Point = Vec<E::ScalarField>;
89    type Evaluation = E::ScalarField;
90    // Commitments and proofs
91    type Commitment = Commitment<E>;
92    type BatchCommitment = Commitment<E>;
93    type Proof = MultilinearKzgProof<E>;
94    type BatchProof = MultilinearKzgBatchProof<E>;
95
96    /// Trim the universal parameters to specialize the public parameters.
97    /// Input both `supported_log_degree` for univariate and
98    /// `supported_num_vars` for multilinear.
99    fn trim(
100        srs: impl Borrow<Self::SRS>,
101        supported_log_degree: usize,
102        supported_num_vars: Option<usize>,
103    ) -> Result<(ProverParam<E>, VerifierParam<E>), PCSError> {
104        let supported_num_vars = match supported_num_vars {
105            Some(p) => p,
106            None => {
107                return Err(PCSError::InvalidParameters(
108                    "multilinear should receive a num_var param".to_string(),
109                ))
110            },
111        };
112        let (uni_ck, uni_vk) = srs.borrow().1.trim(supported_log_degree)?;
113        let (ml_ck, ml_vk) = srs.borrow().0.trim(supported_num_vars)?;
114
115        Ok(((ml_ck, uni_ck), (ml_vk, uni_vk)))
116    }
117
118    /// Generate a commitment for a polynomial.
119    ///
120    /// This function takes `2^num_vars` number of scalar multiplications over
121    /// G1.
122    fn commit(
123        prover_param: impl Borrow<ProverParam<E>>,
124        poly: &Self::Polynomial,
125    ) -> Result<Self::Commitment, PCSError> {
126        let prover_param = prover_param.borrow();
127        let commit_timer = start_timer!(|| "commit");
128        if prover_param.0.num_vars < poly.num_vars {
129            return Err(PCSError::InvalidParameters(format!(
130                "Poly length ({}) exceeds param limit ({})",
131                poly.num_vars, prover_param.0.num_vars
132            )));
133        }
134        let ignored = prover_param.0.num_vars - poly.num_vars;
135        let scalars: Vec<_> = poly
136            .to_evaluations()
137            .into_iter()
138            .map(|x| x.into_bigint())
139            .collect();
140        let commitment = E::G1::msm_bigint(
141            &prover_param.0.powers_of_g[ignored].evals,
142            scalars.as_slice(),
143        )
144        .into_affine();
145
146        end_timer!(commit_timer);
147        Ok(Commitment(commitment))
148    }
149
150    /// Batch commit a list of polynomials.
151    ///
152    /// This function takes `2^(num_vars + log(polys.len())` number of scalar
153    /// multiplications over G1.
154    fn batch_commit(
155        prover_param: impl Borrow<ProverParam<E>>,
156        polys: &[Self::Polynomial],
157    ) -> Result<Self::Commitment, PCSError> {
158        let prover_param = prover_param.borrow();
159        let commit_timer = start_timer!(|| "multi commit");
160        let poly = merge_polynomials(polys)?;
161
162        let scalars: Vec<_> = poly
163            .to_evaluations()
164            .iter()
165            .map(|x| x.into_bigint())
166            .collect();
167
168        let commitment =
169            E::G1::msm_bigint(&prover_param.0.powers_of_g[0].evals, scalars.as_slice())
170                .into_affine();
171
172        end_timer!(commit_timer);
173        Ok(Commitment(commitment))
174    }
175
176    /// On input a polynomial `p` and a point `point`, outputs a proof for the
177    /// same. This function does not need to take the evaluation value as an
178    /// input.
179    ///
180    /// This function takes 2^{num_var +1} number of scalar multiplications over
181    /// G1:
182    /// - it proceeds with `num_var` number of rounds,
183    /// - at round i, we compute an MSM for `2^{num_var - i + 1}` number of G2
184    ///   elements.
185    fn open(
186        prover_param: impl Borrow<ProverParam<E>>,
187        polynomial: &Self::Polynomial,
188        point: &Self::Point,
189    ) -> Result<(Self::Proof, Self::Evaluation), PCSError> {
190        open_internal(&prover_param.borrow().0, polynomial, point)
191    }
192
193    /// Input
194    /// - the prover parameters for univariate KZG,
195    /// - the prover parameters for multilinear KZG,
196    /// - a list of polynomials,
197    /// - a (batch) commitment to all polynomials,
198    /// - and the same number of points,
199    /// compute a batch opening for all the polynomials.
200    ///
201    /// For simplicity, this API requires each MLE to have only one point. If
202    /// the caller wish to use more than one point per MLE, it should be
203    /// handled at the caller layer.
204    ///
205    /// Returns an error if the lengths do not match.
206    ///
207    /// Returns the proof, consists of
208    /// - the multilinear KZG opening
209    /// - the univariate KZG commitment to q(x)
210    /// - the openings and evaluations of q(x) at omega^i and r
211    ///
212    /// Steps:
213    /// 1. build `l(points)` which is a list of univariate polynomials that goes
214    /// through the points
215    /// 2. build MLE `w` which is the merge of all MLEs.
216    /// 3. build `q(x)` which is a univariate polynomial `W circ l`
217    /// 4. commit to q(x) and sample r from transcript
218    /// transcript contains: w commitment, points, q(x)'s commitment
219    /// 5. build q(omega^i) and their openings
220    /// 6. build q(r) and its opening
221    /// 7. get a point `p := l(r)`
222    /// 8. output an opening of `w` over point `p`
223    /// 9. output `w(p)`
224    fn batch_open(
225        prover_param: impl Borrow<ProverParam<E>>,
226        batch_commitment: &Self::BatchCommitment,
227        polynomials: &[Self::Polynomial],
228        points: &[Self::Point],
229    ) -> Result<(Self::BatchProof, Vec<Self::Evaluation>), PCSError> {
230        batch_open_internal::<E>(
231            &prover_param.borrow().1,
232            &prover_param.borrow().0,
233            polynomials,
234            batch_commitment,
235            points,
236        )
237    }
238
239    /// Verifies that `value` is the evaluation at `x` of the polynomial
240    /// committed inside `comm`.
241    ///
242    /// This function takes
243    /// - num_var number of pairing product.
244    /// - num_var number of MSM
245    fn verify(
246        verifier_param: &VerifierParam<E>,
247        commitment: &Self::Commitment,
248        point: &Self::Point,
249        value: &E::ScalarField,
250        proof: &Self::Proof,
251    ) -> Result<bool, PCSError> {
252        verify_internal(&verifier_param.0, commitment, point, value, proof)
253    }
254
255    /// Verifies that `value` is the evaluation at `x_i` of the polynomial
256    /// `poly_i` committed inside `commitment`.
257    /// steps:
258    ///
259    /// 1. put `q(x)`'s evaluations over `(1, omega,...)` into transcript
260    /// 2. sample `r` from transcript
261    /// 3. check `q(r) == value`
262    /// 4. build `l(points)` which is a list of univariate polynomials that goes
263    /// through the points
264    /// 5. get a point `p := l(r)`
265    /// 6. verifies `p` is verifies against proof
266    fn batch_verify<R: RngCore + CryptoRng>(
267        verifier_param: &VerifierParam<E>,
268        batch_commitment: &Self::BatchCommitment,
269        points: &[Self::Point],
270        values: &[E::ScalarField],
271        batch_proof: &Self::BatchProof,
272        _rng: &mut R,
273    ) -> Result<bool, PCSError> {
274        batch_verify_internal(
275            &verifier_param.1,
276            &verifier_param.0,
277            batch_commitment,
278            points,
279            values,
280            batch_proof,
281        )
282    }
283}
284
285/// On input a polynomial `p` and a point `point`, outputs a proof for the
286/// same. This function does not need to take the evaluation value as an
287/// input.
288///
289/// This function takes 2^{num_var} number of scalar multiplications over
290/// G1:
291/// - it proceeds with `num_var` number of rounds,
292/// - at round i, we compute an MSM for `2^{num_var - i}` number of G1 elements.
293fn open_internal<E: Pairing>(
294    prover_param: &MultilinearProverParam<E>,
295    polynomial: &DenseMultilinearExtension<E::ScalarField>,
296    point: &Vec<E::ScalarField>,
297) -> Result<(MultilinearKzgProof<E>, E::ScalarField), PCSError> {
298    let open_timer = start_timer!(|| format!("open mle with {} variable", polynomial.num_vars));
299
300    if polynomial.num_vars() > prover_param.num_vars {
301        return Err(PCSError::InvalidParameters(format!(
302            "Polynomial num_vars {} exceed the limit {}",
303            polynomial.num_vars, prover_param.num_vars
304        )));
305    }
306
307    if polynomial.num_vars() != point.len() {
308        return Err(PCSError::InvalidParameters(format!(
309            "Polynomial num_vars {} does not match point len {}",
310            polynomial.num_vars,
311            point.len()
312        )));
313    }
314
315    let nv = polynomial.num_vars();
316    // the first `ignored` SRS vectors are unused
317    let ignored = prover_param.num_vars - nv + 1;
318
319    let mut f = polynomial.to_evaluations();
320
321    let mut proofs = Vec::new();
322
323    for (i, (&point_at_k, gi)) in point
324        .iter()
325        .zip(prover_param.powers_of_g[ignored..ignored + nv].iter())
326        .enumerate()
327    {
328        let ith_round = start_timer!(|| format!("{}-th round", i));
329
330        let k = nv - 1 - i;
331        let cur_dim = 1 << k;
332        let mut q = vec![E::ScalarField::zero(); cur_dim];
333        let mut r = vec![E::ScalarField::zero(); cur_dim];
334
335        let ith_round_eval = start_timer!(|| format!("{}-th round eval", i));
336        for b in 0..(1 << k) {
337            // q[b] = f[1, b] - f[0, b]
338            q[b] = f[(b << 1) + 1] - f[b << 1];
339
340            // r[b] = f[0, b] + q[b] * p
341            r[b] = f[b << 1] + (q[b] * point_at_k);
342        }
343        f = r;
344        end_timer!(ith_round_eval);
345        let scalars: Vec<_> = q.iter().map(|x| x.into_bigint()).collect();
346
347        // this is a MSM over G1 and is likely to be the bottleneck
348        let msm_timer = start_timer!(|| format!("msm of size {} at round {}", gi.evals.len(), i));
349
350        proofs.push(E::G1::msm_bigint(&gi.evals, &scalars).into_affine());
351        end_timer!(msm_timer);
352
353        end_timer!(ith_round);
354    }
355    let eval = polynomial.evaluate(point);
356    end_timer!(open_timer);
357    Ok((MultilinearKzgProof { proofs }, eval))
358}
359
360/// Verifies that `value` is the evaluation at `x` of the polynomial
361/// committed inside `comm`.
362///
363/// This function takes
364/// - num_var number of pairing product.
365/// - num_var number of MSM
366fn verify_internal<E: Pairing>(
367    verifier_param: &MultilinearVerifierParam<E>,
368    commitment: &Commitment<E>,
369    point: &[E::ScalarField],
370    value: &E::ScalarField,
371    proof: &MultilinearKzgProof<E>,
372) -> Result<bool, PCSError> {
373    let verify_timer = start_timer!(|| "verify");
374    let num_var = point.len();
375
376    if num_var > verifier_param.num_vars {
377        return Err(PCSError::InvalidParameters(format!(
378            "point length ({}) exceeds param limit ({})",
379            num_var, verifier_param.num_vars
380        )));
381    }
382
383    let prepare_inputs_timer = start_timer!(|| "prepare pairing inputs");
384
385    let h_mul = verifier_param.h.clone().into_group().batch_mul(&point);
386
387    // the first `ignored` G2 parameters are unused
388    let ignored = verifier_param.num_vars - num_var;
389    let h_vec: Vec<_> = (0..num_var)
390        .map(|i| verifier_param.h_mask[ignored + i].into_group() - h_mul[i])
391        .collect();
392    let h_vec: Vec<E::G2Affine> = E::G2::normalize_batch(&h_vec);
393    end_timer!(prepare_inputs_timer);
394
395    let pairing_product_timer = start_timer!(|| "pairing product");
396
397    let mut pairings_l: Vec<E::G1Prepared> = proof
398        .proofs
399        .iter()
400        .map(|&x| E::G1Prepared::from(x))
401        .collect();
402
403    let mut pairings_r: Vec<E::G2Prepared> = h_vec
404        .into_iter()
405        .take(num_var)
406        .map(E::G2Prepared::from)
407        .collect();
408    pairings_l.push(E::G1Prepared::from(
409        (verifier_param.g * (*value) - commitment.0.into_group()).into_affine(),
410    ));
411    pairings_r.push(E::G2Prepared::from(verifier_param.h));
412
413    let res = E::multi_pairing(pairings_l, pairings_r).0 == E::TargetField::one();
414
415    end_timer!(pairing_product_timer);
416    end_timer!(verify_timer);
417    Ok(res)
418}
419
420#[cfg(test)]
421mod tests {
422    use super::*;
423    use ark_bls12_381::Bls12_381;
424    use ark_std::UniformRand;
425    use jf_utils::test_rng;
426    type E = Bls12_381;
427    type Fr = <E as Pairing>::ScalarField;
428
429    fn test_single_helper<R: RngCore + CryptoRng>(
430        params: &(MultilinearUniversalParams<E>, UnivariateUniversalParams<E>),
431        poly: &MLE<Fr>,
432        rng: &mut R,
433    ) -> Result<(), PCSError> {
434        let nv = poly.num_vars();
435        assert_ne!(nv, 0);
436        let uni_degree = 1;
437        let (ck, vk) = MultilinearKzgPCS::trim(params, uni_degree, Some(nv))?;
438        let point: Vec<_> = (0..nv).map(|_| Fr::rand(rng)).collect();
439        let com = MultilinearKzgPCS::commit(&ck, poly)?;
440        let (proof, value) = MultilinearKzgPCS::open(&ck, poly, &point)?;
441
442        assert!(MultilinearKzgPCS::verify(
443            &vk, &com, &point, &value, &proof
444        )?);
445
446        let value = Fr::rand(rng);
447        assert!(!MultilinearKzgPCS::verify(
448            &vk, &com, &point, &value, &proof
449        )?);
450
451        Ok(())
452    }
453
454    #[test]
455    fn test_single_commit() -> Result<(), PCSError> {
456        let mut rng = test_rng();
457
458        let params = MultilinearKzgPCS::<E>::gen_srs_for_testing(&mut rng, 10)?;
459
460        // normal polynomials
461        let poly1 = MLE::from(DenseMultilinearExtension::rand(8, &mut rng));
462        test_single_helper(&params, &poly1, &mut rng)?;
463
464        // single-variate polynomials
465        let poly2 = MLE::from(DenseMultilinearExtension::rand(1, &mut rng));
466        test_single_helper(&params, &poly2, &mut rng)?;
467
468        Ok(())
469    }
470
471    #[test]
472    fn setup_commit_verify_constant_polynomial() {
473        let mut rng = test_rng();
474
475        // normal polynomials
476        assert!(MultilinearKzgPCS::<E>::gen_srs_for_testing(&mut rng, 0).is_err());
477    }
478}