1mod 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
41type Srs<E> = (MultilinearUniversalParams<E>, UnivariateUniversalParams<E>);
43type ProverParam<E> = <Srs<E> as StructuredReferenceString>::ProverParam;
44type VerifierParam<E> = <Srs<E> as StructuredReferenceString>::VerifierParam;
45
46pub 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)]
54pub struct MultilinearKzgProof<E: Pairing> {
56 pub proofs: Vec<E::G1Affine>,
58}
59
60#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug, PartialEq, Eq)]
61pub struct MultilinearKzgBatchProof<E: Pairing> {
63 pub proof: MultilinearKzgProof<E>,
65 pub q_x_commit: Commitment<E>,
69 pub q_x_opens: Vec<UnivariateKzgProof<E>>,
71}
72
73#[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 type SRS = Srs<E>;
86 type Polynomial = MLE<E::ScalarField>;
88 type Point = Vec<E::ScalarField>;
89 type Evaluation = E::ScalarField;
90 type Commitment = Commitment<E>;
92 type BatchCommitment = Commitment<E>;
93 type Proof = MultilinearKzgProof<E>;
94 type BatchProof = MultilinearKzgBatchProof<E>;
95
96 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 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 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 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 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 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 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
285fn 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 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[(b << 1) + 1] - f[b << 1];
339
340 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 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
360fn 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 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 let poly1 = MLE::from(DenseMultilinearExtension::rand(8, &mut rng));
462 test_single_helper(¶ms, &poly1, &mut rng)?;
463
464 let poly2 = MLE::from(DenseMultilinearExtension::rand(1, &mut rng));
466 test_single_helper(¶ms, &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 assert!(MultilinearKzgPCS::<E>::gen_srs_for_testing(&mut rng, 0).is_err());
477 }
478}