hyperplonk/pcs/src/commit.rs
pcs/src/commit.rsRaw
1use crate::{
2 util::{build_l, compute_w_circ_l, merge_polynomials},
3 KZGMultilinearPC, MultilinearCommitmentScheme, PCSErrors, ProverParam, UniversalParams,
4 VerifierParam,
5};
6use ark_ec::{
7 msm::{FixedBaseMSM, VariableBaseMSM},
8 AffineCurve, PairingEngine, ProjectiveCurve,
9};
10use ark_ff::PrimeField;
11use ark_poly::{univariate::DensePolynomial, MultilinearExtension, Polynomial, UVPolynomial};
12use ark_serialize::{CanonicalDeserialize, CanonicalSerialize, Read, SerializationError, Write};
13use ark_std::{end_timer, log2, rand::RngCore, start_timer, vec::Vec, One, Zero};
14use poly_iop::IOPTranscript;
15
16#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
17/// commitment
18pub struct Commitment<E: PairingEngine> {
19 /// number of variables
20 pub nv: usize,
21 /// product of g as described by the vRAM paper
22 pub g_product: E::G1Affine,
23}
24
25#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
26/// proof of opening
27pub struct Proof<E: PairingEngine> {
28 /// Evaluation of quotients
29 pub proofs: Vec<E::G1Affine>,
30}
31
32#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
33/// proof of batch opening
34pub struct BatchProof<E: PairingEngine> {
35 /// The actual proof
36 pub proof: Proof<E>,
37 /// The value which is `w` evaluated at `p:= l(r)`, where
38 /// - `w` is the merged MLE
39 /// - `l` is the list of univariate polys that goes through all points
40 /// - `r` is sampled from the transcript.
41 pub value: E::Fr,
42 /// Commitment to q(x)
43 // This is currently set to the entire coefficient list of q(x)
44 // TODO: replace me with a KZG commit
45 pub q_x_com: Vec<E::Fr>,
46}
47
48impl<E: PairingEngine> MultilinearCommitmentScheme<E> for KZGMultilinearPC<E> {
49 type ProverParam = ProverParam<E>;
50 type VerifierParam = VerifierParam<E>;
51 type SRS = UniversalParams<E>;
52 type Commitment = Commitment<E>;
53 type Proof = Proof<E>;
54 type Transcript = IOPTranscript<E::Fr>;
55 type BatchProof = BatchProof<E>;
56
57 /// Generate SRS from RNG.
58 /// WARNING: THIS FUNCTION IS FOR TESTING PURPOSE ONLY.
59 /// THE OUTPUT SRS SHOULD NOT BE USED IN PRODUCTION.
60 fn setup<R: RngCore>(rng: &mut R, num_vars: usize) -> Result<Self::SRS, PCSErrors> {
61 let setup_timer = start_timer!(|| format!("SRS setup for dim {}", num_vars));
62 let res = Self::SRS::gen_srs_for_testing(rng, num_vars);
63 end_timer!(setup_timer);
64 res
65 }
66
67 /// Generate a commitment for a polynomial.
68 ///
69 /// This function takes `2^num_vars` number of scalar multiplications over
70 /// G1.
71 fn commit(
72 prover_param: &Self::ProverParam,
73 poly: &impl MultilinearExtension<E::Fr>,
74 ) -> Result<Self::Commitment, PCSErrors> {
75 let commit_timer = start_timer!(|| "commit");
76
77 let nv = poly.num_vars();
78 let scalars: Vec<_> = poly
79 .to_evaluations()
80 .into_iter()
81 .map(|x| x.into_repr())
82 .collect();
83 let g_product = VariableBaseMSM::multi_scalar_mul(
84 &prover_param.powers_of_g[0].evals,
85 scalars.as_slice(),
86 )
87 .into_affine();
88
89 end_timer!(commit_timer);
90 Ok(Commitment { nv, g_product })
91 }
92
93 /// Generate a commitment for a list of polynomials.
94 ///
95 /// This function takes `2^(num_vars + log(polys.len())` number of scalar
96 /// multiplications over G1.
97 fn multi_commit(
98 prover_param: &Self::ProverParam,
99 polys: &[impl MultilinearExtension<E::Fr>],
100 ) -> Result<Self::Commitment, PCSErrors> {
101 let commit_timer = start_timer!(|| "multi commit");
102 let poly = merge_polynomials(polys)?;
103
104 let scalars: Vec<_> = poly
105 .to_evaluations()
106 .iter()
107 .map(|x| x.into_repr())
108 .collect();
109
110 let g_product = VariableBaseMSM::multi_scalar_mul(
111 &prover_param.powers_of_g[0].evals,
112 scalars.as_slice(),
113 )
114 .into_affine();
115
116 end_timer!(commit_timer);
117 Ok(Commitment {
118 nv: poly.num_vars,
119 g_product,
120 })
121 }
122
123 /// On input a polynomial `p` and a point `point`, outputs a proof for the
124 /// same. This function does not need to take the evaluation value as an
125 /// input.
126 ///
127 /// This function takes 2^{num_var +1} number of scalar multiplications over
128 /// G1:
129 /// - it proceeds with `num_var` number of rounds,
130 /// - at round i, we compute an MSM for `2^{num_var - i + 1}` number of G2
131 /// elements.
132 fn open(
133 prover_param: &Self::ProverParam,
134 polynomial: &impl MultilinearExtension<E::Fr>,
135 point: &[E::Fr],
136 ) -> Result<Self::Proof, PCSErrors> {
137 let open_timer = start_timer!(|| "open");
138
139 assert_eq!(
140 polynomial.num_vars(),
141 prover_param.num_vars,
142 "Invalid size of polynomial"
143 );
144 let nv = polynomial.num_vars();
145 let mut r: Vec<Vec<E::Fr>> = (0..nv + 1).map(|_| Vec::new()).collect();
146 let mut q: Vec<Vec<E::Fr>> = (0..nv + 1).map(|_| Vec::new()).collect();
147
148 r[nv] = polynomial.to_evaluations();
149
150 let mut proofs = Vec::new();
151
152 for (i, (&point_at_k, gi)) in point
153 .iter()
154 .zip(prover_param.powers_of_g.iter())
155 .take(nv)
156 .enumerate()
157 {
158 let ith_round = start_timer!(|| format!("{}-th round", i));
159
160 let k = nv - i;
161 let cur_dim = 1 << (k - 1);
162 let mut cur_q = vec![E::Fr::zero(); cur_dim];
163 let mut cur_r = vec![E::Fr::zero(); cur_dim];
164
165 for b in 0..(1 << (k - 1)) {
166 // q_b = pre_r [2^b + 1] - pre_r [2^b]
167 cur_q[b] = r[k][(b << 1) + 1] - r[k][b << 1];
168
169 // r_b = pre_r [2^b]*(1-p) + pre_r [2^b + 1] * p
170 cur_r[b] =
171 r[k][b << 1] * (E::Fr::one() - point_at_k) + (r[k][(b << 1) + 1] * point_at_k);
172 }
173
174 let scalars: Vec<_> = (0..(1 << k)).map(|x| cur_q[x >> 1].into_repr()).collect();
175
176 q[k] = cur_q;
177 r[k - 1] = cur_r;
178
179 // this is a MSM over G1 and is likely to be the bottleneck
180 proofs.push(VariableBaseMSM::multi_scalar_mul(&gi.evals, &scalars).into_affine());
181 end_timer!(ith_round);
182 }
183
184 end_timer!(open_timer);
185 Ok(Proof { proofs })
186 }
187
188 /// Input
189 /// - the prover parameters,
190 /// - a list of MLEs,
191 /// - and a same number of points,
192 /// - and a transcript,
193 /// compute a multi-opening for all the polynomials.
194 ///
195 /// For simplicity, this API requires each MLE to have only one point. If
196 /// the caller wish to use more than one points per MLE, it should be
197 /// handled at the caller layer.
198 ///
199 /// Returns an error if the lengths do not match.
200 ///
201 /// Returns:
202 /// - the proof,
203 /// - q(x), which is a univariate polynomial `w circ l` where `w` is the
204 /// merged MLE, and `l` is a list of polynomials that go through all the
205 /// points. TODO: change this field to a commitment to `q(x)`
206 /// - and a value which is `w` evaluated at `p:= l(r)` from some `r` from
207 /// the transcript.
208 ///
209 /// Steps:
210 /// 1. build `l(points)` which is a list of univariate polynomials that goes
211 /// through the points
212 /// 2. build MLE `w` which is the merge of all MLEs.
213 /// 3. build `q(x)` which is a univariate polynomial `W circ l`
214 /// 4. output `q(x)`' and put it into transcript
215 /// 5. sample `r` from transcript
216 /// 6. get a point `p := l(r)`
217 /// 7. output an opening of `w` over point `p`
218 /// 8. output `w(p)`
219 fn multi_open(
220 prover_param: &Self::ProverParam,
221 polynomials: &[impl MultilinearExtension<E::Fr>],
222 points: &[&[E::Fr]],
223 transcript: &mut IOPTranscript<E::Fr>,
224 ) -> Result<Self::BatchProof, PCSErrors> {
225 let open_timer = start_timer!(|| "multi open");
226
227 if points.len() != polynomials.len() {
228 return Err(PCSErrors::InvalidParameters(
229 "polynomial length does not match point length".to_string(),
230 ));
231 }
232
233 let num_var = polynomials[0].num_vars();
234 for poly in polynomials.iter().skip(1) {
235 if poly.num_vars() != num_var {
236 return Err(PCSErrors::InvalidParameters(
237 "polynomials do not have same num_vars".to_string(),
238 ));
239 }
240 }
241 for &point in points.iter() {
242 if point.len() != num_var {
243 return Err(PCSErrors::InvalidParameters(
244 "points do not have same num_vars".to_string(),
245 ));
246 }
247 }
248
249 // 1. build `l(points)` which is a list of univariate polynomials that goes
250 // through the points
251 let uni_polys = build_l(num_var, points)?;
252
253 // 2. build MLE `w` which is the merge of all MLEs.
254 let merge_poly = merge_polynomials(polynomials)?;
255
256 // 3. build `q(x)` which is a univariate polynomial `W circ l`
257 let q_x = compute_w_circ_l(&merge_poly, &uni_polys)?;
258
259 // 4. output `q(x)`' and put it into transcript
260 //
261 // TODO: use KZG commit for q(x)
262 // TODO: unwrap
263 q_x.coeffs
264 .iter()
265 .for_each(|x| transcript.append_field_element(b"q(x)", x).unwrap());
266
267 // 5. sample `r` from transcript
268 let r = transcript.get_and_append_challenge(b"r")?;
269
270 // 6. get a point `p := l(r)`
271 let point: Vec<E::Fr> = uni_polys
272 .iter()
273 .rev()
274 .map(|poly| poly.evaluate(&r))
275 .collect();
276
277 // 7. output an opening of `w` over point `p`
278 let opening = Self::open(prover_param, &merge_poly, &point)?;
279
280 // 8. output value that is `w` evaluated at `p` (which should match `q(r)`)
281 let value = merge_poly.evaluate(&point).unwrap();
282 let value2 = q_x.evaluate(&r);
283
284 if value != value2 {
285 return Err(PCSErrors::InvalidProver(
286 "Q(r) does not match W(l(r))".to_string(),
287 ));
288 }
289
290 end_timer!(open_timer);
291
292 Ok(Self::BatchProof {
293 proof: opening,
294 q_x_com: q_x.coeffs,
295 value,
296 })
297 }
298
299 /// Verifies that `value` is the evaluation at `x` of the polynomial
300 /// committed inside `comm`.
301 ///
302 /// This function takes
303 /// - num_var number of pairing product.
304 /// - num_var number of MSM
305 fn verify(
306 verifier_param: &Self::VerifierParam,
307 commitment: &Self::Commitment,
308 point: &[E::Fr],
309 value: &E::Fr,
310 proof: &Self::Proof,
311 ) -> Result<bool, PCSErrors> {
312 let verify_timer = start_timer!(|| "verify");
313 let prepare_inputs_timer = start_timer!(|| "prepare pairing inputs");
314
315 let scalar_size = E::Fr::size_in_bits();
316 let window_size = FixedBaseMSM::get_mul_window_size(verifier_param.num_vars);
317
318 let h_table = FixedBaseMSM::get_window_table(
319 scalar_size,
320 window_size,
321 verifier_param.h.into_projective(),
322 );
323 let h_mul: Vec<E::G2Projective> =
324 FixedBaseMSM::multi_scalar_mul(scalar_size, window_size, &h_table, point);
325
326 let h_vec: Vec<_> = (0..verifier_param.num_vars)
327 .map(|i| verifier_param.h_mask[i].into_projective() - h_mul[i])
328 .collect();
329 let h_vec: Vec<E::G2Affine> = E::G2Projective::batch_normalization_into_affine(&h_vec);
330 end_timer!(prepare_inputs_timer);
331
332 let pairing_product_timer = start_timer!(|| "pairing product");
333
334 let mut pairings: Vec<_> = proof
335 .proofs
336 .iter()
337 .map(|&x| E::G1Prepared::from(x))
338 .zip(
339 h_vec
340 .into_iter()
341 .take(verifier_param.num_vars)
342 .map(E::G2Prepared::from),
343 )
344 .collect();
345
346 pairings.push((
347 E::G1Prepared::from(
348 (verifier_param.g.mul(*value) - commitment.g_product.into_projective())
349 .into_affine(),
350 ),
351 E::G2Prepared::from(verifier_param.h),
352 ));
353
354 let res = E::product_of_pairings(pairings.iter()) == E::Fqk::one();
355
356 end_timer!(pairing_product_timer);
357 end_timer!(verify_timer);
358 Ok(res)
359 }
360
361 /// Verifies that `value` is the evaluation at `x_i` of the polynomial
362 /// `poly_i` committed inside `comm`.
363 /// steps:
364 ///
365 /// 1. put `q(x)`'s evaluations over `(1, omega,...)` into transcript
366 /// 2. sample `r` from transcript
367 /// 3. check `q(r) == value`
368 /// 4. build `l(points)` which is a list of univariate polynomials that goes
369 /// through the points
370 /// 5. get a point `p := l(r)`
371 /// 6. verifies `p` is verifies against proof
372 fn batch_verify(
373 verifier_param: &Self::VerifierParam,
374 multi_commitment: &Self::Commitment,
375 points: &[&[E::Fr]],
376 batch_proof: &Self::BatchProof,
377 transcript: &mut IOPTranscript<E::Fr>,
378 ) -> Result<bool, PCSErrors> {
379 let verify_timer = start_timer!(|| "batch verify");
380 let num_var = points[0].len();
381
382 for &point in points.iter().skip(1) {
383 if point.len() != num_var {
384 return Err(PCSErrors::InvalidParameters(format!(
385 "points do not have same num_vars ({} vs {})",
386 point.len(),
387 num_var,
388 )));
389 }
390 }
391 if num_var + log2(points.len()) as usize != multi_commitment.nv {
392 return Err(PCSErrors::InvalidParameters(format!(
393 "points and multi_commitment do not have same num_vars ({} vs {})",
394 num_var + log2(points.len()) as usize,
395 num_var,
396 )));
397 }
398
399 // TODO: verify commitment of `q(x)` instead of receiving full `q(x)`
400
401 // 1. put `q(x)`'s evaluations over `(1, omega,...)` into transcript
402 // TODO: unwrap
403 batch_proof
404 .q_x_com
405 .iter()
406 .for_each(|x| transcript.append_field_element(b"q(x)", x).unwrap());
407
408 // 2. sample `r` from transcript
409 let r = transcript.get_and_append_challenge(b"r")?;
410
411 // 3. check `q(r) == value`
412 let q_x = DensePolynomial::from_coefficients_slice(&batch_proof.q_x_com);
413 let q_r = q_x.evaluate(&r);
414 if q_r != batch_proof.value {
415 return Ok(false);
416 }
417
418 // 4. build `l(points)` which is a list of univariate polynomials that goes
419 // through the points
420 let uni_polys = build_l(num_var, points)?;
421
422 // 5. get a point `p := l(r)`
423 let point: Vec<E::Fr> = uni_polys.iter().rev().map(|x| x.evaluate(&r)).collect();
424
425 // 6. verifies `p` is verifies against proof
426 let res = Self::verify(
427 verifier_param,
428 multi_commitment,
429 &point,
430 &batch_proof.value,
431 &batch_proof.proof,
432 );
433 end_timer!(verify_timer);
434
435 res
436 }
437}
438
439#[cfg(test)]
440mod tests {
441 use crate::util::get_batched_nv;
442
443 use super::*;
444 use ark_bls12_381::Bls12_381;
445 use ark_ec::PairingEngine;
446 use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
447 use ark_std::{rand::RngCore, test_rng, vec::Vec, UniformRand};
448 type E = Bls12_381;
449 type Fr = <E as PairingEngine>::Fr;
450
451 fn test_single_helper<R: RngCore>(
452 uni_params: &UniversalParams<E>,
453 poly: &impl MultilinearExtension<Fr>,
454 rng: &mut R,
455 ) -> Result<(), PCSErrors> {
456 let nv = poly.num_vars();
457 assert_ne!(nv, 0);
458 let (ck, vk) = uni_params.trim(nv)?;
459 let point: Vec<_> = (0..nv).map(|_| Fr::rand(rng)).collect();
460 let com = KZGMultilinearPC::commit(&ck, poly)?;
461 let proof = KZGMultilinearPC::open(&ck, poly, &point)?;
462
463 let value = poly.evaluate(&point).unwrap();
464 assert!(KZGMultilinearPC::verify(&vk, &com, &point, &value, &proof)?);
465
466 let value = Fr::rand(rng);
467 assert!(!KZGMultilinearPC::verify(
468 &vk, &com, &point, &value, &proof
469 )?);
470
471 Ok(())
472 }
473
474 #[test]
475 fn test_single_commit() -> Result<(), PCSErrors> {
476 let mut rng = test_rng();
477
478 let uni_params = KZGMultilinearPC::<E>::setup(&mut rng, 10)?;
479
480 // normal polynomials
481 let poly1 = DenseMultilinearExtension::rand(8, &mut rng);
482 test_single_helper(&uni_params, &poly1, &mut rng)?;
483
484 // single-variate polynomials
485 let poly2 = DenseMultilinearExtension::rand(1, &mut rng);
486 test_single_helper(&uni_params, &poly2, &mut rng)?;
487
488 Ok(())
489 }
490
491 fn test_multi_commit_helper<R: RngCore>(
492 uni_params: &UniversalParams<E>,
493 polys: &[impl MultilinearExtension<Fr>],
494 rng: &mut R,
495 ) -> Result<(), PCSErrors> {
496 let mut transcript = IOPTranscript::new(b"test");
497
498 let nv = get_batched_nv(polys[0].num_vars(), polys.len());
499 let (ck, vk) = uni_params.trim(nv)?;
500 let mut points = Vec::new();
501
502 for poly in polys.iter() {
503 let point = (0..poly.num_vars())
504 .map(|_| Fr::rand(rng))
505 .collect::<Vec<Fr>>();
506 points.push(point);
507 }
508 let points_ref: Vec<&[Fr]> = points.iter().map(|x| x.as_ref()).collect();
509
510 let com = KZGMultilinearPC::multi_commit(&ck, polys)?;
511 let batch_proof = KZGMultilinearPC::multi_open(&ck, polys, &points_ref, &mut transcript)?;
512
513 // good path
514 let mut transcript = IOPTranscript::new(b"test");
515 assert!(KZGMultilinearPC::batch_verify(
516 &vk,
517 &com,
518 &points_ref,
519 &batch_proof,
520 &mut transcript
521 )?);
522
523 // bad commitment
524 assert!(KZGMultilinearPC::batch_verify(
525 &vk,
526 &Commitment {
527 nv: 0,
528 g_product: <E as PairingEngine>::G1Affine::default()
529 },
530 &points_ref,
531 &batch_proof,
532 &mut transcript
533 )
534 .is_err());
535
536 // bad points
537 let points_ref: Vec<&[Fr]> = points.iter().skip(1).map(|x| x.as_ref()).collect();
538 assert!(KZGMultilinearPC::batch_verify(
539 &vk,
540 &com,
541 &points_ref,
542 &batch_proof,
543 &mut transcript
544 )
545 .is_err());
546
547 // bad proof
548 assert!(KZGMultilinearPC::batch_verify(
549 &vk,
550 &com,
551 &points_ref,
552 &BatchProof {
553 proof: Proof { proofs: Vec::new() },
554 value: batch_proof.value,
555 q_x_com: batch_proof.q_x_com.clone()
556 },
557 &mut transcript
558 )
559 .is_err());
560
561 // bad value
562 assert!(KZGMultilinearPC::batch_verify(
563 &vk,
564 &com,
565 &points_ref,
566 &BatchProof {
567 proof: batch_proof.proof.clone(),
568 value: Fr::one(),
569 q_x_com: batch_proof.q_x_com
570 },
571 &mut transcript
572 )
573 .is_err());
574
575 // bad q(x) commit
576 assert!(KZGMultilinearPC::batch_verify(
577 &vk,
578 &com,
579 &points_ref,
580 &BatchProof {
581 proof: batch_proof.proof,
582 value: batch_proof.value,
583 q_x_com: Vec::new()
584 },
585 &mut transcript
586 )
587 .is_err());
588
589 Ok(())
590 }
591
592 #[test]
593 fn test_multi_commit() -> Result<(), PCSErrors> {
594 let mut rng = test_rng();
595
596 let uni_params = KZGMultilinearPC::<E>::setup(&mut rng, 15)?;
597
598 // normal polynomials
599 let polys1: Vec<_> = (0..2)
600 .map(|_| DenseMultilinearExtension::rand(4, &mut rng))
601 .collect();
602 test_multi_commit_helper(&uni_params, &polys1, &mut rng)?;
603
604 // single-variate polynomials
605 let polys1: Vec<_> = (0..5)
606 .map(|_| DenseMultilinearExtension::rand(1, &mut rng))
607 .collect();
608 test_multi_commit_helper(&uni_params, &polys1, &mut rng)?;
609
610 Ok(())
611 }
612
613 #[test]
614 fn setup_commit_verify_constant_polynomial() {
615 let mut rng = test_rng();
616
617 // normal polynomials
618 assert!(KZGMultilinearPC::<E>::setup(&mut rng, 0).is_err());
619 }
620}