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 Proof = KZGUnivariateOpening<E>;
42 type BatchProof = Vec<Self::Proof>;
43 type BatchCommitment = Vec<Self::Commitment>;
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 /// Generate a commitment for a polynomial
60 /// Note that the scheme is not hidding
61 fn commit(
62 prover_param: &Self::ProverParam,
63 poly: &Self::Polynomial,
64 ) -> Result<Self::Commitment, PCSErrors> {
65 let commit_time =
66 start_timer!(|| format!("Committing to polynomial of degree {} ", poly.degree()));
67
68 if poly.degree() > prover_param.powers_of_g.len() {
69 return Err(PCSErrors::InvalidParameters(format!(
70 "poly degree {} is larger than allowed {}",
71 poly.degree(),
72 prover_param.powers_of_g.len()
73 )));
74 }
75
76 let (num_leading_zeros, plain_coeffs) = skip_leading_zeros_and_convert_to_bigints(poly);
77
78 let msm_time = start_timer!(|| "MSM to compute commitment to plaintext poly");
79 let commitment = VariableBaseMSM::multi_scalar_mul(
80 &prover_param.powers_of_g[num_leading_zeros..],
81 &plain_coeffs,
82 )
83 .into_affine();
84 end_timer!(msm_time);
85
86 end_timer!(commit_time);
87 Ok(Commitment { commitment })
88 }
89
90 /// Generate a commitment for a list of polynomials
91 fn multi_commit(
92 prover_param: &Self::ProverParam,
93 polys: &[Self::Polynomial],
94 ) -> Result<Self::BatchCommitment, PCSErrors> {
95 let commit_time = start_timer!(|| format!("batch commit {} polynomials", polys.len()));
96 let res = polys
97 .iter()
98 .map(|poly| Self::commit(prover_param, poly))
99 .collect::<Result<Vec<Self::Commitment>, PCSErrors>>()?;
100
101 end_timer!(commit_time);
102 Ok(res)
103 }
104
105 /// On input a polynomial `p` and a point `point`, outputs a proof for the
106 /// same.
107 fn open(
108 prover_param: &Self::ProverParam,
109 polynomial: &Self::Polynomial,
110 point: &Self::Point,
111 ) -> Result<(Self::Proof, Self::Evaluation), PCSErrors> {
112 let open_time =
113 start_timer!(|| format!("Opening polynomial of degree {}", polynomial.degree()));
114 let divisor = Self::Polynomial::from_coefficients_vec(vec![-*point, E::Fr::one()]);
115
116 let witness_time = start_timer!(|| "Computing witness polynomial");
117 let witness_polynomial = polynomial / &divisor;
118 end_timer!(witness_time);
119
120 let (num_leading_zeros, witness_coeffs) =
121 skip_leading_zeros_and_convert_to_bigints(&witness_polynomial);
122
123 let proof = VariableBaseMSM::multi_scalar_mul(
124 &prover_param.powers_of_g[num_leading_zeros..],
125 &witness_coeffs,
126 )
127 .into_affine();
128
129 let eval = polynomial.evaluate(point);
130
131 end_timer!(open_time);
132 Ok((Self::Proof { proof }, eval))
133 }
134
135 /// Input a list of polynomials, and a same number of points,
136 /// compute a multi-opening for all the polynomials.
137 // This is a naive approach
138 // TODO: to implement the more efficient batch opening algorithm
139 // (e.g., the appendix C.4 in https://eprint.iacr.org/2020/1536.pdf)
140 fn multi_open(
141 prover_param: &Self::ProverParam,
142 _multi_commitment: &Self::Commitment,
143 polynomials: &[Self::Polynomial],
144 points: &[Self::Point],
145 ) -> Result<(Self::BatchProof, Vec<Self::Evaluation>), PCSErrors> {
146 let open_time = start_timer!(|| format!("batch opening {} polynomials", polynomials.len()));
147 if polynomials.len() != points.len() {
148 return Err(PCSErrors::InvalidParameters(format!(
149 "poly length {} is different from points length {}",
150 polynomials.len(),
151 points.len()
152 )));
153 }
154 let mut batch_proof = vec![];
155 let mut evals = vec![];
156 for (poly, point) in polynomials.iter().zip(points.iter()) {
157 let (proof, eval) = Self::open(prover_param, poly, point)?;
158 batch_proof.push(proof);
159 evals.push(eval);
160 }
161
162 end_timer!(open_time);
163 Ok((batch_proof, evals))
164 }
165 /// Verifies that `value` is the evaluation at `x` of the polynomial
166 /// committed inside `comm`.
167 fn verify(
168 verifier_param: &Self::VerifierParam,
169 commitment: &Self::Commitment,
170 point: &Self::Point,
171 value: &E::Fr,
172 proof: &Self::Proof,
173 ) -> Result<bool, PCSErrors> {
174 let check_time = start_timer!(|| "Checking evaluation");
175 let pairing_inputs: Vec<(E::G1Prepared, E::G2Prepared)> = vec![
176 (
177 (verifier_param.g.mul(value.into_repr())
178 - proof.proof.mul(point.into_repr())
179 - commitment.commitment.into_projective())
180 .into_affine()
181 .into(),
182 verifier_param.h.into(),
183 ),
184 (proof.proof.into(), verifier_param.beta_h.into()),
185 ];
186
187 let res = E::product_of_pairings(pairing_inputs.iter()).is_one();
188
189 end_timer!(check_time, || format!("Result: {}", res));
190 Ok(res)
191 }
192
193 /// Verifies that `value_i` is the evaluation at `x_i` of the polynomial
194 /// `poly_i` committed inside `comm`.
195 // This is a naive approach
196 // TODO: to implement the more efficient batch verification algorithm
197 // (e.g., the appendix C.4 in https://eprint.iacr.org/2020/1536.pdf)
198 fn batch_verify<R: RngCore>(
199 verifier_param: &Self::VerifierParam,
200 multi_commitment: &Self::BatchCommitment,
201 points: &[Self::Point],
202 values: &[E::Fr],
203 batch_proof: &Self::BatchProof,
204 rng: &mut R,
205 ) -> Result<bool, PCSErrors> {
206 let check_time =
207 start_timer!(|| format!("Checking {} evaluation proofs", multi_commitment.len()));
208
209 let mut total_c = <E::G1Projective>::zero();
210 let mut total_w = <E::G1Projective>::zero();
211
212 let combination_time = start_timer!(|| "Combining commitments and proofs");
213 let mut randomizer = E::Fr::one();
214 // Instead of multiplying g and gamma_g in each turn, we simply accumulate
215 // their coefficients and perform a final multiplication at the end.
216 let mut g_multiplier = E::Fr::zero();
217 for (((c, z), v), proof) in multi_commitment
218 .iter()
219 .zip(points)
220 .zip(values)
221 .zip(batch_proof)
222 {
223 let w = proof.proof;
224 let mut temp = w.mul(*z);
225 temp.add_assign_mixed(&c.commitment);
226 let c = temp;
227 g_multiplier += &(randomizer * v);
228 total_c += &c.mul(randomizer.into_repr());
229 total_w += &w.mul(randomizer.into_repr());
230 // We don't need to sample randomizers from the full field,
231 // only from 128-bit strings.
232 randomizer = u128::rand(rng).into();
233 }
234 total_c -= &verifier_param.g.mul(g_multiplier);
235 end_timer!(combination_time);
236
237 let to_affine_time = start_timer!(|| "Converting results to affine for pairing");
238 let affine_points = E::G1Projective::batch_normalization_into_affine(&[-total_w, total_c]);
239 let (total_w, total_c) = (affine_points[0], affine_points[1]);
240 end_timer!(to_affine_time);
241
242 let pairing_time = start_timer!(|| "Performing product of pairings");
243 let result = E::product_of_pairings(&[
244 (total_w.into(), verifier_param.beta_h.into()),
245 (total_c.into(), verifier_param.h.into()),
246 ])
247 .is_one();
248 end_timer!(pairing_time);
249 end_timer!(check_time, || format!("Result: {}", result));
250 Ok(result)
251 }
252}
253
254fn skip_leading_zeros_and_convert_to_bigints<F: PrimeField, P: UVPolynomial<F>>(
255 p: &P,
256) -> (usize, Vec<F::BigInt>) {
257 let mut num_leading_zeros = 0;
258 while num_leading_zeros < p.coeffs().len() && p.coeffs()[num_leading_zeros].is_zero() {
259 num_leading_zeros += 1;
260 }
261 let coeffs = convert_to_bigints(&p.coeffs()[num_leading_zeros..]);
262 (num_leading_zeros, coeffs)
263}
264
265fn convert_to_bigints<F: PrimeField>(p: &[F]) -> Vec<F::BigInt> {
266 let to_bigint_time = start_timer!(|| "Converting polynomial coeffs to bigints");
267 let coeffs = p.iter().map(|s| s.into_repr()).collect::<Vec<_>>();
268 end_timer!(to_bigint_time);
269 coeffs
270}
271
272#[cfg(test)]
273mod tests {
274 use super::*;
275 use crate::StructuredReferenceString;
276 use ark_bls12_381::Bls12_381;
277 use ark_ec::PairingEngine;
278 use ark_poly::univariate::DensePolynomial;
279 use ark_std::{log2, test_rng, UniformRand};
280
281 fn end_to_end_test_template<E>() -> Result<(), PCSErrors>
282 where
283 E: PairingEngine,
284 {
285 let rng = &mut test_rng();
286 for _ in 0..100 {
287 let mut degree = 0;
288 while degree <= 1 {
289 degree = usize::rand(rng) % 20;
290 }
291 let log_degree = log2(degree) as usize;
292 let pp = KZGUnivariatePCS::<E>::gen_srs_for_testing(rng, log_degree)?;
293 let (ck, vk) = pp.trim(log_degree)?;
294 let p = <DensePolynomial<E::Fr> as UVPolynomial<E::Fr>>::rand(degree, rng);
295 let comm = KZGUnivariatePCS::<E>::commit(&ck, &p)?;
296 let point = E::Fr::rand(rng);
297 let (proof, value) = KZGUnivariatePCS::<E>::open(&ck, &p, &point)?;
298 assert!(
299 KZGUnivariatePCS::<E>::verify(&vk, &comm, &point, &value, &proof)?,
300 "proof was incorrect for max_degree = {}, polynomial_degree = {}",
301 degree,
302 p.degree(),
303 );
304 }
305 Ok(())
306 }
307
308 fn linear_polynomial_test_template<E>() -> Result<(), PCSErrors>
309 where
310 E: PairingEngine,
311 {
312 let rng = &mut test_rng();
313 for _ in 0..100 {
314 let degree = 50;
315 let log_degree = log2(degree) as usize;
316
317 let pp = KZGUnivariatePCS::<E>::gen_srs_for_testing(rng, log_degree)?;
318 let (ck, vk) = pp.trim(log_degree)?;
319 let p = <DensePolynomial<E::Fr> as UVPolynomial<E::Fr>>::rand(degree, rng);
320 let comm = KZGUnivariatePCS::<E>::commit(&ck, &p)?;
321 let point = E::Fr::rand(rng);
322 let (proof, value) = KZGUnivariatePCS::<E>::open(&ck, &p, &point)?;
323 assert!(
324 KZGUnivariatePCS::<E>::verify(&vk, &comm, &point, &value, &proof)?,
325 "proof was incorrect for max_degree = {}, polynomial_degree = {}",
326 degree,
327 p.degree(),
328 );
329 }
330 Ok(())
331 }
332
333 fn batch_check_test_template<E>() -> Result<(), PCSErrors>
334 where
335 E: PairingEngine,
336 {
337 let rng = &mut test_rng();
338 for _ in 0..10 {
339 let mut degree = 0;
340 while degree <= 1 {
341 degree = usize::rand(rng) % 20;
342 }
343 let log_degree = log2(degree) as usize;
344 let pp = KZGUnivariatePCS::<E>::gen_srs_for_testing(rng, log_degree)?;
345 let (ck, vk) = pp.trim(log_degree)?;
346 let mut comms = Vec::new();
347 let mut values = Vec::new();
348 let mut points = Vec::new();
349 let mut proofs = Vec::new();
350 for _ in 0..10 {
351 let p = <DensePolynomial<E::Fr> as UVPolynomial<E::Fr>>::rand(degree, rng);
352 let comm = KZGUnivariatePCS::<E>::commit(&ck, &p)?;
353 let point = E::Fr::rand(rng);
354 let (proof, value) = KZGUnivariatePCS::<E>::open(&ck, &p, &point)?;
355
356 assert!(KZGUnivariatePCS::<E>::verify(
357 &vk, &comm, &point, &value, &proof
358 )?);
359 comms.push(comm);
360 values.push(value);
361 points.push(point);
362 proofs.push(proof);
363 }
364 assert!(KZGUnivariatePCS::<E>::batch_verify(
365 &vk, &comms, &points, &values, &proofs, rng
366 )?);
367 }
368 Ok(())
369 }
370
371 #[test]
372 fn end_to_end_test() {
373 end_to_end_test_template::<Bls12_381>().expect("test failed for bls12-381");
374 }
375
376 #[test]
377 fn linear_polynomial_test() {
378 linear_polynomial_test_template::<Bls12_381>().expect("test failed for bls12-381");
379 }
380 #[test]
381 fn batch_check_test() {
382 batch_check_test_template::<Bls12_381>().expect("test failed for bls12-381");
383 }
384}