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