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, 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 = 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 = Proof<E>;
68 type BatchProof = BatchProof<E>;
69 type BatchCommitment = Commitment<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 /// Generate a commitment for a polynomial.
89 ///
90 /// This function takes `2^num_vars` number of scalar multiplications over
91 /// G1.
92 fn commit(
93 prover_param: &Self::ProverParam,
94 poly: &Self::Polynomial,
95 ) -> Result<Self::Commitment, PCSErrors> {
96 let commit_timer = start_timer!(|| "commit");
97
98 let scalars: Vec<_> = poly
99 .to_evaluations()
100 .into_iter()
101 .map(|x| x.into_repr())
102 .collect();
103 let commitment = VariableBaseMSM::multi_scalar_mul(
104 &prover_param.0.powers_of_g[0].evals,
105 scalars.as_slice(),
106 )
107 .into_affine();
108
109 end_timer!(commit_timer);
110 Ok(Commitment { commitment })
111 }
112
113 /// Generate a commitment for a list of polynomials.
114 ///
115 /// This function takes `2^(num_vars + log(polys.len())` number of scalar
116 /// multiplications over G1.
117 fn multi_commit(
118 prover_param: &Self::ProverParam,
119 polys: &[Self::Polynomial],
120 ) -> Result<Self::Commitment, PCSErrors> {
121 let commit_timer = start_timer!(|| "multi commit");
122 let poly = merge_polynomials(polys)?;
123
124 let scalars: Vec<_> = poly
125 .to_evaluations()
126 .iter()
127 .map(|x| x.into_repr())
128 .collect();
129
130 let commitment = VariableBaseMSM::multi_scalar_mul(
131 &prover_param.0.powers_of_g[0].evals,
132 scalars.as_slice(),
133 )
134 .into_affine();
135
136 end_timer!(commit_timer);
137 Ok(Commitment { commitment })
138 }
139
140 /// On input a polynomial `p` and a point `point`, outputs a proof for the
141 /// same. This function does not need to take the evaluation value as an
142 /// input.
143 ///
144 /// This function takes 2^{num_var +1} number of scalar multiplications over
145 /// G1:
146 /// - it prodceeds with `num_var` number of rounds,
147 /// - at round i, we compute an MSM for `2^{num_var - i + 1}` number of G2
148 /// elements.
149 fn open(
150 prover_param: &Self::ProverParam,
151 polynomial: &Self::Polynomial,
152 point: &Self::Point,
153 ) -> Result<(Self::Proof, Self::Evaluation), PCSErrors> {
154 open_internal(&prover_param.0, polynomial, point)
155 }
156
157 /// Input
158 /// - the prover parameters for univariate KZG,
159 /// - the prover parameters for multilinear KZG,
160 /// - a list of MLEs,
161 /// - a commitment to all MLEs
162 /// - and a same number of points,
163 /// compute a multi-opening for all the polynomials.
164 ///
165 /// For simplicity, this API requires each MLE to have only one point. If
166 /// the caller wish to use more than one points per MLE, it should be
167 /// handled at the caller layer.
168 ///
169 /// Returns an error if the lengths do not match.
170 ///
171 /// Returns the proof, consists of
172 /// - the multilinear KZG opening
173 /// - the univariate KZG commitment to q(x)
174 /// - the openings and evaluations of q(x) at omega^i and r
175 ///
176 /// Steps:
177 /// 1. build `l(points)` which is a list of univariate polynomials that goes
178 /// through the points
179 /// 2. build MLE `w` which is the merge of all MLEs.
180 /// 3. build `q(x)` which is a univariate polynomial `W circ l`
181 /// 4. commit to q(x) and sample r from transcript
182 /// transcript contains: w commitment, points, q(x)'s commitment
183 /// 5. build q(omega^i) and their openings
184 /// 6. build q(r) and its opening
185 /// 7. get a point `p := l(r)`
186 /// 8. output an opening of `w` over point `p`
187 /// 9. output `w(p)`
188 fn multi_open(
189 prover_param: &Self::ProverParam,
190 multi_commitment: &Self::Commitment,
191 polynomials: &[Self::Polynomial],
192 points: &[Self::Point],
193 ) -> Result<(Self::BatchProof, Vec<Self::Evaluation>), PCSErrors> {
194 multi_open_internal::<E>(
195 &prover_param.1,
196 &prover_param.0,
197 polynomials,
198 multi_commitment,
199 points,
200 )
201 }
202
203 /// Verifies that `value` is the evaluation at `x` of the polynomial
204 /// committed inside `comm`.
205 ///
206 /// This function takes
207 /// - num_var number of pairing product.
208 /// - num_var number of MSM
209 fn verify(
210 verifier_param: &Self::VerifierParam,
211 commitment: &Self::Commitment,
212 point: &Self::Point,
213 value: &E::Fr,
214 proof: &Self::Proof,
215 ) -> Result<bool, PCSErrors> {
216 verify_internal(&verifier_param.0, commitment, point, value, proof)
217 }
218
219 /// Verifies that `value` is the evaluation at `x_i` of the polynomial
220 /// `poly_i` committed inside `comm`.
221 /// steps:
222 ///
223 /// 1. put `q(x)`'s evaluations over `(1, omega,...)` into transcript
224 /// 2. sample `r` from transcript
225 /// 3. check `q(r) == value`
226 /// 4. build `l(points)` which is a list of univariate polynomials that goes
227 /// through the points
228 /// 5. get a point `p := l(r)`
229 /// 6. verifies `p` is verifies against proof
230 fn batch_verify<R: RngCore>(
231 verifier_param: &Self::VerifierParam,
232 multi_commitment: &Self::BatchCommitment,
233 points: &[Self::Point],
234 values: &[E::Fr],
235 batch_proof: &Self::BatchProof,
236 _rng: &mut R,
237 ) -> Result<bool, PCSErrors> {
238 batch_verify_internal(
239 &verifier_param.1,
240 &verifier_param.0,
241 multi_commitment,
242 points,
243 values,
244 batch_proof,
245 )
246 }
247}
248
249/// On input a polynomial `p` and a point `point`, outputs a proof for the
250/// same. This function does not need to take the evaluation value as an
251/// input.
252///
253/// This function takes 2^{num_var +1} number of scalar multiplications over
254/// G1:
255/// - it proceeds with `num_var` number of rounds,
256/// - at round i, we compute an MSM for `2^{num_var - i + 1}` number of G2
257/// elements.
258fn open_internal<E: PairingEngine>(
259 prover_param: &MultilinearProverParam<E>,
260 polynomial: &DenseMultilinearExtension<E::Fr>,
261 point: &[E::Fr],
262) -> Result<(Proof<E>, E::Fr), PCSErrors> {
263 let open_timer = start_timer!(|| format!("open mle with {} variable", polynomial.num_vars));
264
265 assert_eq!(
266 polynomial.num_vars(),
267 prover_param.num_vars,
268 "Invalid size of polynomial"
269 );
270 let nv = polynomial.num_vars();
271 let mut r: Vec<Vec<E::Fr>> = (0..nv + 1).map(|_| Vec::new()).collect();
272 let mut q: Vec<Vec<E::Fr>> = (0..nv + 1).map(|_| Vec::new()).collect();
273
274 r[nv] = polynomial.to_evaluations();
275
276 let mut proofs = Vec::new();
277
278 for (i, (&point_at_k, gi)) in point
279 .iter()
280 .zip(prover_param.powers_of_g.iter())
281 .take(nv)
282 .enumerate()
283 {
284 let ith_round = start_timer!(|| format!("{}-th round", i));
285
286 let k = nv - i;
287 let cur_dim = 1 << (k - 1);
288 let mut cur_q = vec![E::Fr::zero(); cur_dim];
289 let mut cur_r = vec![E::Fr::zero(); cur_dim];
290
291 for b in 0..(1 << (k - 1)) {
292 // q_b = pre_r [2^b + 1] - pre_r [2^b]
293 cur_q[b] = r[k][(b << 1) + 1] - r[k][b << 1];
294
295 // r_b = pre_r [2^b]*(1-p) + pre_r [2^b + 1] * p
296 cur_r[b] =
297 r[k][b << 1] * (E::Fr::one() - point_at_k) + (r[k][(b << 1) + 1] * point_at_k);
298 }
299
300 let scalars: Vec<_> = (0..(1 << k)).map(|x| cur_q[x >> 1].into_repr()).collect();
301
302 q[k] = cur_q;
303 r[k - 1] = cur_r;
304
305 // this is a MSM over G1 and is likely to be the bottleneck
306 proofs.push(VariableBaseMSM::multi_scalar_mul(&gi.evals, &scalars).into_affine());
307 end_timer!(ith_round);
308 }
309 let eval = polynomial.evaluate(point).ok_or_else(|| {
310 PCSErrors::InvalidParameters("fail to evaluate the polynomial".to_string())
311 })?;
312 end_timer!(open_timer);
313 Ok((Proof { proofs }, eval))
314}
315
316/// Verifies that `value` is the evaluation at `x` of the polynomial
317/// committed inside `comm`.
318///
319/// This function takes
320/// - num_var number of pairing product.
321/// - num_var number of MSM
322fn verify_internal<E: PairingEngine>(
323 verifier_param: &MultilinearVerifierParam<E>,
324 commitment: &Commitment<E>,
325 point: &[E::Fr],
326 value: &E::Fr,
327 proof: &Proof<E>,
328) -> Result<bool, PCSErrors> {
329 let verify_timer = start_timer!(|| "verify");
330 let prepare_inputs_timer = start_timer!(|| "prepare pairing inputs");
331
332 let scalar_size = E::Fr::size_in_bits();
333 let window_size = FixedBaseMSM::get_mul_window_size(verifier_param.num_vars);
334
335 let h_table = FixedBaseMSM::get_window_table(
336 scalar_size,
337 window_size,
338 verifier_param.h.into_projective(),
339 );
340 let h_mul: Vec<E::G2Projective> =
341 FixedBaseMSM::multi_scalar_mul(scalar_size, window_size, &h_table, point);
342
343 let h_vec: Vec<_> = (0..verifier_param.num_vars)
344 .map(|i| verifier_param.h_mask[i].into_projective() - h_mul[i])
345 .collect();
346 let h_vec: Vec<E::G2Affine> = E::G2Projective::batch_normalization_into_affine(&h_vec);
347 end_timer!(prepare_inputs_timer);
348
349 let pairing_product_timer = start_timer!(|| "pairing product");
350
351 let mut pairings: Vec<_> = proof
352 .proofs
353 .iter()
354 .map(|&x| E::G1Prepared::from(x))
355 .zip(
356 h_vec
357 .into_iter()
358 .take(verifier_param.num_vars)
359 .map(E::G2Prepared::from),
360 )
361 .collect();
362
363 pairings.push((
364 E::G1Prepared::from(
365 (verifier_param.g.mul(*value) - commitment.commitment.into_projective()).into_affine(),
366 ),
367 E::G2Prepared::from(verifier_param.h),
368 ));
369
370 let res = E::product_of_pairings(pairings.iter()) == E::Fqk::one();
371
372 end_timer!(pairing_product_timer);
373 end_timer!(verify_timer);
374 Ok(res)
375}
376
377#[cfg(test)]
378mod tests {
379 use super::*;
380 use crate::StructuredReferenceString;
381 use ark_bls12_381::Bls12_381;
382 use ark_ec::PairingEngine;
383 use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
384 use ark_std::{rand::RngCore, test_rng, vec::Vec, UniformRand};
385 type E = Bls12_381;
386 type Fr = <E as PairingEngine>::Fr;
387
388 fn test_single_helper<R: RngCore>(
389 params: &(MultilinearUniversalParams<E>, UnivariateUniversalParams<E>),
390 poly: &DenseMultilinearExtension<Fr>,
391 rng: &mut R,
392 ) -> Result<(), PCSErrors> {
393 let nv = poly.num_vars();
394 assert_ne!(nv, 0);
395 let uni_degree = 1;
396 let (uni_ck, uni_vk) = params.1.trim(uni_degree)?;
397 let (ml_ck, ml_vk) = params.0.trim(nv)?;
398 let ck = (ml_ck, uni_ck);
399 let vk = (ml_vk, uni_vk);
400
401 let point: Vec<_> = (0..nv).map(|_| Fr::rand(rng)).collect();
402 let com = KZGMultilinearPCS::commit(&ck, poly)?;
403 let (proof, value) = KZGMultilinearPCS::open(&ck, poly, &point)?;
404
405 assert!(KZGMultilinearPCS::verify(
406 &vk, &com, &point, &value, &proof
407 )?);
408
409 let value = Fr::rand(rng);
410 assert!(!KZGMultilinearPCS::verify(
411 &vk, &com, &point, &value, &proof
412 )?);
413
414 Ok(())
415 }
416
417 #[test]
418 fn test_single_commit() -> Result<(), PCSErrors> {
419 let mut rng = test_rng();
420
421 let params = KZGMultilinearPCS::<E>::gen_srs_for_testing(&mut rng, 10)?;
422
423 // normal polynomials
424 let poly1 = DenseMultilinearExtension::rand(8, &mut rng);
425 test_single_helper(¶ms, &poly1, &mut rng)?;
426
427 // single-variate polynomials
428 let poly2 = DenseMultilinearExtension::rand(1, &mut rng);
429 test_single_helper(¶ms, &poly2, &mut rng)?;
430
431 Ok(())
432 }
433
434 #[test]
435 fn setup_commit_verify_constant_polynomial() {
436 let mut rng = test_rng();
437
438 // normal polynomials
439 assert!(KZGMultilinearPCS::<E>::gen_srs_for_testing(&mut rng, 0).is_err());
440 }
441}