hyperplonk/pcs/src/univariate_kzg/mod.rs
pcs/src/univariate_kzg/mod.rsRaw
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 univariate KZG commitment scheme
8
9use crate::{prelude::Commitment, PCSError, PolynomialCommitmentScheme, StructuredReferenceString};
10use ark_ec::{msm::VariableBaseMSM, AffineCurve, PairingEngine, ProjectiveCurve};
11use ark_ff::PrimeField;
12use ark_poly::{univariate::DensePolynomial, Polynomial, UVPolynomial};
13use ark_serialize::{CanonicalDeserialize, CanonicalSerialize, Read, SerializationError, Write};
14use ark_std::{
15 borrow::Borrow,
16 end_timer, format,
17 marker::PhantomData,
18 rand::{CryptoRng, RngCore},
19 start_timer,
20 string::ToString,
21 vec,
22 vec::Vec,
23 One, UniformRand, Zero,
24};
25#[cfg(feature = "parallel")]
26use rayon::prelude::*;
27use srs::{UnivariateProverParam, UnivariateUniversalParams, UnivariateVerifierParam};
28use util::parallelizable_slice_iter;
29
30pub(crate) mod srs;
31
32/// KZG Polynomial Commitment Scheme on univariate polynomial.
33pub struct UnivariateKzgPCS<E: PairingEngine> {
34 #[doc(hidden)]
35 phantom: PhantomData<E>,
36}
37
38#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug, PartialEq, Eq)]
39/// proof of opening
40pub struct UnivariateKzgProof<E: PairingEngine> {
41 /// Evaluation of quotients
42 pub proof: E::G1Affine,
43}
44/// batch proof
45pub type UnivariateKzgBatchProof<E> = Vec<UnivariateKzgProof<E>>;
46
47impl<E: PairingEngine> PolynomialCommitmentScheme<E> for UnivariateKzgPCS<E> {
48 // Parameters
49 type ProverParam = UnivariateProverParam<E::G1Affine>;
50 type VerifierParam = UnivariateVerifierParam<E>;
51 type SRS = UnivariateUniversalParams<E>;
52 // Polynomial and its associated types
53 type Polynomial = DensePolynomial<E::Fr>;
54 type Point = E::Fr;
55 type Evaluation = E::Fr;
56 // Polynomial and its associated types
57 type Commitment = Commitment<E>;
58 type BatchCommitment = Vec<Self::Commitment>;
59 type Proof = UnivariateKzgProof<E>;
60 type BatchProof = UnivariateKzgBatchProof<E>;
61
62 /// Build SRS for testing.
63 ///
64 /// - For univariate polynomials, `supported_size` is the maximum degree.
65 ///
66 /// WARNING: THIS FUNCTION IS FOR TESTING PURPOSE ONLY.
67 /// THE OUTPUT SRS SHOULD NOT BE USED IN PRODUCTION.
68 fn gen_srs_for_testing<R: RngCore + CryptoRng>(
69 rng: &mut R,
70 supported_size: usize,
71 ) -> Result<Self::SRS, PCSError> {
72 Self::SRS::gen_srs_for_testing(rng, supported_size)
73 }
74
75 /// Trim the universal parameters to specialize the public parameters.
76 /// Input `max_degree` for univariate.
77 /// `supported_num_vars` must be None or an error is returned.
78 fn trim(
79 srs: impl Borrow<Self::SRS>,
80 supported_degree: usize,
81 supported_num_vars: Option<usize>,
82 ) -> Result<(Self::ProverParam, Self::VerifierParam), PCSError> {
83 if supported_num_vars.is_some() {
84 return Err(PCSError::InvalidParameters(
85 "univariate should not receive a num_var param".to_string(),
86 ));
87 }
88 srs.borrow().trim(supported_degree)
89 }
90
91 /// Generate a commitment for a polynomial
92 /// Note that the scheme is not hidding
93 fn commit(
94 prover_param: impl Borrow<Self::ProverParam>,
95 poly: &Self::Polynomial,
96 ) -> Result<Self::Commitment, PCSError> {
97 let prover_param = prover_param.borrow();
98 let commit_time =
99 start_timer!(|| format!("Committing to polynomial of degree {} ", poly.degree()));
100
101 if poly.degree() >= prover_param.powers_of_g.len() {
102 return Err(PCSError::InvalidParameters(format!(
103 "uni poly degree {} is larger than allowed {}",
104 poly.degree(),
105 prover_param.powers_of_g.len()
106 )));
107 }
108
109 let (num_leading_zeros, plain_coeffs) = skip_leading_zeros_and_convert_to_bigints(poly);
110
111 let msm_time = start_timer!(|| "MSM to compute commitment to plaintext poly");
112 let commitment = VariableBaseMSM::multi_scalar_mul(
113 &prover_param.powers_of_g[num_leading_zeros..],
114 &plain_coeffs,
115 )
116 .into_affine();
117 end_timer!(msm_time);
118
119 end_timer!(commit_time);
120 Ok(Commitment(commitment))
121 }
122
123 /// Generate a commitment for a list of polynomials
124 fn multi_commit(
125 prover_param: impl Borrow<Self::ProverParam>,
126 polys: &[Self::Polynomial],
127 ) -> Result<Self::BatchCommitment, PCSError> {
128 let prover_param = prover_param.borrow();
129 let commit_time = start_timer!(|| format!("batch commit {} polynomials", polys.len()));
130 let res = parallelizable_slice_iter(polys)
131 .map(|poly| Self::commit(prover_param, poly))
132 .collect::<Result<Vec<Self::Commitment>, PCSError>>()?;
133
134 end_timer!(commit_time);
135 Ok(res)
136 }
137
138 /// On input a polynomial `p` and a point `point`, outputs a proof for the
139 /// same.
140 fn open(
141 prover_param: impl Borrow<Self::ProverParam>,
142 polynomial: &Self::Polynomial,
143 point: &Self::Point,
144 ) -> Result<(Self::Proof, Self::Evaluation), PCSError> {
145 let open_time =
146 start_timer!(|| format!("Opening polynomial of degree {}", polynomial.degree()));
147 let divisor = Self::Polynomial::from_coefficients_vec(vec![-*point, E::Fr::one()]);
148
149 let witness_time = start_timer!(|| "Computing witness polynomial");
150 let witness_polynomial = polynomial / &divisor;
151 end_timer!(witness_time);
152
153 let (num_leading_zeros, witness_coeffs) =
154 skip_leading_zeros_and_convert_to_bigints(&witness_polynomial);
155
156 let proof = VariableBaseMSM::multi_scalar_mul(
157 &prover_param.borrow().powers_of_g[num_leading_zeros..],
158 &witness_coeffs,
159 )
160 .into_affine();
161
162 let eval = polynomial.evaluate(point);
163
164 end_timer!(open_time);
165 Ok((Self::Proof { proof }, eval))
166 }
167
168 /// Input a list of polynomials, and a same number of points,
169 /// compute a multi-opening for all the polynomials.
170 // This is a naive approach
171 // TODO: to implement the more efficient batch opening algorithm
172 // (e.g., the appendix C.4 in https://eprint.iacr.org/2020/1536.pdf)
173 fn multi_open(
174 prover_param: impl Borrow<Self::ProverParam>,
175 _multi_commitment: &Self::BatchCommitment,
176 polynomials: &[Self::Polynomial],
177 points: &[Self::Point],
178 ) -> Result<(Self::BatchProof, Vec<Self::Evaluation>), PCSError> {
179 let open_time = start_timer!(|| format!("batch opening {} polynomials", polynomials.len()));
180 if polynomials.len() != points.len() {
181 return Err(PCSError::InvalidParameters(format!(
182 "poly length {} is different from points length {}",
183 polynomials.len(),
184 points.len()
185 )));
186 }
187 let mut batch_proof = vec![];
188 let mut evals = vec![];
189 for (poly, point) in polynomials.iter().zip(points.iter()) {
190 let (proof, eval) = Self::open(prover_param.borrow(), poly, point)?;
191 batch_proof.push(proof);
192 evals.push(eval);
193 }
194
195 end_timer!(open_time);
196 Ok((batch_proof, evals))
197 }
198
199 /// Input a multilinear extension, and a number of points, and
200 /// a transcript, compute a multi-opening for all the polynomials.
201 fn multi_open_single_poly(
202 _prover_param: impl Borrow<Self::ProverParam>,
203 _commitment: &Self::Commitment,
204 _polynomials: &Self::Polynomial,
205 _points: &[Self::Point],
206 ) -> Result<(Self::BatchProof, Vec<Self::Evaluation>), PCSError> {
207 unimplemented!()
208 }
209
210 /// Verifies that `value` is the evaluation at `x` of the polynomial
211 /// committed inside `comm`.
212 fn verify(
213 verifier_param: &Self::VerifierParam,
214 commitment: &Self::Commitment,
215 point: &Self::Point,
216 value: &E::Fr,
217 proof: &Self::Proof,
218 ) -> Result<bool, PCSError> {
219 let check_time = start_timer!(|| "Checking evaluation");
220 let pairing_inputs: Vec<(E::G1Prepared, E::G2Prepared)> = vec![
221 (
222 (verifier_param.g.mul(value.into_repr())
223 - proof.proof.mul(point.into_repr())
224 - commitment.0.into_projective())
225 .into_affine()
226 .into(),
227 verifier_param.h.into(),
228 ),
229 (proof.proof.into(), verifier_param.beta_h.into()),
230 ];
231
232 let res = E::product_of_pairings(pairing_inputs.iter()).is_one();
233
234 end_timer!(check_time, || format!("Result: {}", res));
235 Ok(res)
236 }
237
238 /// Verifies that `value_i` is the evaluation at `x_i` of the polynomial
239 /// `poly_i` committed inside `comm`.
240 // This is a naive approach
241 // TODO: to implement the more efficient batch verification algorithm
242 // (e.g., the appendix C.4 in https://eprint.iacr.org/2020/1536.pdf)
243 fn batch_verify<R: RngCore + CryptoRng>(
244 verifier_param: &Self::VerifierParam,
245 multi_commitment: &Self::BatchCommitment,
246 points: &[Self::Point],
247 values: &[E::Fr],
248 batch_proof: &Self::BatchProof,
249 rng: &mut R,
250 ) -> Result<bool, PCSError> {
251 let check_time =
252 start_timer!(|| format!("Checking {} evaluation proofs", multi_commitment.len()));
253
254 let mut total_c = <E::G1Projective>::zero();
255 let mut total_w = <E::G1Projective>::zero();
256
257 let combination_time = start_timer!(|| "Combining commitments and proofs");
258 let mut randomizer = E::Fr::one();
259 // Instead of multiplying g and gamma_g in each turn, we simply accumulate
260 // their coefficients and perform a final multiplication at the end.
261 let mut g_multiplier = E::Fr::zero();
262 for (((c, z), v), proof) in multi_commitment
263 .iter()
264 .zip(points)
265 .zip(values)
266 .zip(batch_proof)
267 {
268 let w = proof.proof;
269 let mut temp = w.mul(*z);
270 temp.add_assign_mixed(&c.0);
271 let c = temp;
272 g_multiplier += &(randomizer * v);
273 total_c += &c.mul(randomizer.into_repr());
274 total_w += &w.mul(randomizer.into_repr());
275 // We don't need to sample randomizers from the full field,
276 // only from 128-bit strings.
277 randomizer = u128::rand(rng).into();
278 }
279 total_c -= &verifier_param.g.mul(g_multiplier);
280 end_timer!(combination_time);
281
282 let to_affine_time = start_timer!(|| "Converting results to affine for pairing");
283 let affine_points = E::G1Projective::batch_normalization_into_affine(&[-total_w, total_c]);
284 let (total_w, total_c) = (affine_points[0], affine_points[1]);
285 end_timer!(to_affine_time);
286
287 let pairing_time = start_timer!(|| "Performing product of pairings");
288 let result = E::product_of_pairings(&[
289 (total_w.into(), verifier_param.beta_h.into()),
290 (total_c.into(), verifier_param.h.into()),
291 ])
292 .is_one();
293 end_timer!(pairing_time);
294 end_timer!(check_time, || format!("Result: {}", result));
295 Ok(result)
296 }
297
298 /// Verifies that `value_i` is the evaluation at `x_i` of the polynomial
299 /// `poly` committed inside `comm`.
300 fn batch_verify_single_poly(
301 _verifier_param: &Self::VerifierParam,
302 _commitment: &Self::Commitment,
303 _points: &[Self::Point],
304 _values: &[E::Fr],
305 _batch_proof: &Self::BatchProof,
306 ) -> Result<bool, PCSError> {
307 unimplemented!()
308 }
309}
310
311fn skip_leading_zeros_and_convert_to_bigints<F: PrimeField, P: UVPolynomial<F>>(
312 p: &P,
313) -> (usize, Vec<F::BigInt>) {
314 let mut num_leading_zeros = 0;
315 while num_leading_zeros < p.coeffs().len() && p.coeffs()[num_leading_zeros].is_zero() {
316 num_leading_zeros += 1;
317 }
318 let coeffs = convert_to_bigints(&p.coeffs()[num_leading_zeros..]);
319 (num_leading_zeros, coeffs)
320}
321
322fn convert_to_bigints<F: PrimeField>(p: &[F]) -> Vec<F::BigInt> {
323 let to_bigint_time = start_timer!(|| "Converting polynomial coeffs to bigints");
324 let coeffs = p.iter().map(|s| s.into_repr()).collect::<Vec<_>>();
325 end_timer!(to_bigint_time);
326 coeffs
327}
328
329#[cfg(test)]
330mod tests {
331 use super::*;
332 use crate::StructuredReferenceString;
333 use ark_bls12_381::Bls12_381;
334 use ark_ec::PairingEngine;
335 use ark_poly::univariate::DensePolynomial;
336 use ark_std::{test_rng, UniformRand};
337
338 fn end_to_end_test_template<E>() -> Result<(), PCSError>
339 where
340 E: PairingEngine,
341 {
342 let rng = &mut test_rng();
343 for _ in 0..100 {
344 let mut degree = 0;
345 while degree <= 1 {
346 degree = usize::rand(rng) % 20;
347 }
348 let pp = UnivariateKzgPCS::<E>::gen_srs_for_testing(rng, degree)?;
349 let (ck, vk) = pp.trim(degree)?;
350 let p = <DensePolynomial<E::Fr> as UVPolynomial<E::Fr>>::rand(degree, rng);
351 let comm = UnivariateKzgPCS::<E>::commit(&ck, &p)?;
352 let point = E::Fr::rand(rng);
353 let (proof, value) = UnivariateKzgPCS::<E>::open(&ck, &p, &point)?;
354 assert!(
355 UnivariateKzgPCS::<E>::verify(&vk, &comm, &point, &value, &proof)?,
356 "proof was incorrect for max_degree = {}, polynomial_degree = {}",
357 degree,
358 p.degree(),
359 );
360 }
361 Ok(())
362 }
363
364 fn linear_polynomial_test_template<E>() -> Result<(), PCSError>
365 where
366 E: PairingEngine,
367 {
368 let rng = &mut test_rng();
369 for _ in 0..100 {
370 let degree = 50;
371
372 let pp = UnivariateKzgPCS::<E>::gen_srs_for_testing(rng, degree)?;
373 let (ck, vk) = pp.trim(degree)?;
374 let p = <DensePolynomial<E::Fr> as UVPolynomial<E::Fr>>::rand(degree, rng);
375 let comm = UnivariateKzgPCS::<E>::commit(&ck, &p)?;
376 let point = E::Fr::rand(rng);
377 let (proof, value) = UnivariateKzgPCS::<E>::open(&ck, &p, &point)?;
378 assert!(
379 UnivariateKzgPCS::<E>::verify(&vk, &comm, &point, &value, &proof)?,
380 "proof was incorrect for max_degree = {}, polynomial_degree = {}",
381 degree,
382 p.degree(),
383 );
384 }
385 Ok(())
386 }
387
388 fn batch_check_test_template<E>() -> Result<(), PCSError>
389 where
390 E: PairingEngine,
391 {
392 let rng = &mut test_rng();
393 for _ in 0..10 {
394 let mut degree = 0;
395 while degree <= 1 {
396 degree = usize::rand(rng) % 20;
397 }
398 let pp = UnivariateKzgPCS::<E>::gen_srs_for_testing(rng, degree)?;
399 let (ck, vk) = UnivariateKzgPCS::<E>::trim(&pp, degree, None)?;
400 let mut comms = Vec::new();
401 let mut values = Vec::new();
402 let mut points = Vec::new();
403 let mut proofs = Vec::new();
404 for _ in 0..10 {
405 let p = <DensePolynomial<E::Fr> as UVPolynomial<E::Fr>>::rand(degree, rng);
406 let comm = UnivariateKzgPCS::<E>::commit(&ck, &p)?;
407 let point = E::Fr::rand(rng);
408 let (proof, value) = UnivariateKzgPCS::<E>::open(&ck, &p, &point)?;
409
410 assert!(UnivariateKzgPCS::<E>::verify(
411 &vk, &comm, &point, &value, &proof
412 )?);
413 comms.push(comm);
414 values.push(value);
415 points.push(point);
416 proofs.push(proof);
417 }
418 assert!(UnivariateKzgPCS::<E>::batch_verify(
419 &vk, &comms, &points, &values, &proofs, rng
420 )?);
421 }
422 Ok(())
423 }
424
425 #[test]
426 fn end_to_end_test() {
427 end_to_end_test_template::<Bls12_381>().expect("test failed for bls12-381");
428 }
429
430 #[test]
431 fn linear_polynomial_test() {
432 linear_polynomial_test_template::<Bls12_381>().expect("test failed for bls12-381");
433 }
434 #[test]
435 fn batch_check_test() {
436 batch_check_test_template::<Bls12_381>().expect("test failed for bls12-381");
437 }
438}