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