1  // Copyright (c) 2025-2026 ACDC Network
  2  // This file is part of the alphavm library.
  3  //
  4  // Alpha Chain | Delta Chain Protocol
  5  // International Monetary Graphite.
  6  //
  7  // Derived from Aleo (https://aleo.org) and ProvableHQ (https://provable.com).
  8  // They built world-class ZK infrastructure. We installed the EASY button.
  9  // Their cryptography: elegant. Our modifications: bureaucracy-compatible.
 10  // Original brilliance: theirs. Robert's Rules: ours. Bugs: definitely ours.
 11  //
 12  // Original Aleo/ProvableHQ code subject to Apache 2.0 https://www.apache.org/licenses/LICENSE-2.0
 13  // All modifications and new work: CC0 1.0 Universal Public Domain Dedication.
 14  // No rights reserved. No permission required. No warranty. No refunds.
 15  //
 16  // https://creativecommons.org/publicdomain/zero/1.0/
 17  // SPDX-License-Identifier: CC0-1.0
 18  
 19  //! Here we construct a polynomial commitment that enables users to commit to a
 20  //! single polynomial `p`, and then later provide an evaluation proof that
 21  //! convinces verifiers that a claimed value `v` is the true evaluation of `p`
 22  //! at a chosen point `x`. Our construction follows the template of the
 23  //! construction proposed by Kate, Zaverucha, and Goldberg ([KZG11](http://cacr.uwaterloo.ca/techreports/2010/cacr2010-10.pdf)).
 24  //! This construction achieves extractability in the algebraic group model
 25  //! (AGM).
 26  
 27  use crate::{
 28      fft::{DensePolynomial, Polynomial},
 29      msm::VariableBase,
 30      polycommit::PCError,
 31  };
 32  use alphavm_curves::traits::{AffineCurve, PairingCurve, PairingEngine, ProjectiveCurve};
 33  use alphavm_fields::{One, PrimeField, Zero};
 34  use alphavm_utilities::{cfg_iter, cfg_iter_mut, rand::Uniform, BitIteratorBE};
 35  
 36  use anyhow::{anyhow, ensure, Result};
 37  use core::{marker::PhantomData, ops::Mul};
 38  use itertools::Itertools;
 39  use rand::RngCore;
 40  
 41  #[cfg(not(feature = "serial"))]
 42  use rayon::prelude::*;
 43  
 44  mod data_structures;
 45  pub use data_structures::*;
 46  
 47  use super::sonic_pc::LabeledPolynomialWithBasis;
 48  
 49  #[derive(Debug, PartialEq, Eq)]
 50  pub enum KZGDegreeBounds {
 51      All,
 52      Varuna,
 53      List(Vec<usize>),
 54      None,
 55  }
 56  
 57  impl KZGDegreeBounds {
 58      pub fn get_list<F: PrimeField>(&self, max_degree: usize) -> Vec<usize> {
 59          match self {
 60              KZGDegreeBounds::All => (0..max_degree).collect(),
 61              KZGDegreeBounds::Varuna => {
 62                  // In Varuna, the degree bounds are all of the forms `domain_size - 2`.
 63                  // Consider that we are using radix-2 FFT,
 64                  // there are only a few possible domain sizes and therefore degree bounds.
 65                  //
 66                  // We do not consider mixed-radix FFT for simplicity, as the curves that we
 67                  // are using have very high two-arity.
 68  
 69                  let mut radix_2_possible_domain_sizes = vec![];
 70  
 71                  let mut cur = 2usize;
 72                  while cur - 2 <= max_degree {
 73                      radix_2_possible_domain_sizes.push(cur - 2);
 74                      cur *= 2;
 75                  }
 76  
 77                  radix_2_possible_domain_sizes
 78              }
 79              KZGDegreeBounds::List(v) => v.clone(),
 80              KZGDegreeBounds::None => vec![],
 81          }
 82      }
 83  }
 84  
 85  /// `KZG10` is an implementation of the polynomial commitment scheme of
 86  /// [Kate, Zaverucha and Goldbgerg][kzg10]
 87  ///
 88  /// [kzg10]: http://cacr.uwaterloo.ca/techreports/2010/cacr2010-10.pdf
 89  #[derive(Clone, Debug)]
 90  pub struct KZG10<E: PairingEngine>(PhantomData<E>);
 91  
 92  impl<E: PairingEngine> KZG10<E> {
 93      /// Constructs public parameters when given as input the maximum degree
 94      /// `degree` for the polynomial commitment scheme.
 95      pub fn load_srs(max_degree: usize) -> Result<UniversalParams<E>, PCError> {
 96          let params = UniversalParams::load()?;
 97          params.download_powers_for(0..(max_degree + 1))?;
 98          Ok(params)
 99      }
100  
101      /// Outputs a commitment to `polynomial`.
102      pub fn commit(
103          powers: &Powers<E>,
104          polynomial: &Polynomial<'_, E::Fr>,
105          hiding_bound: Option<usize>,
106          rng: Option<&mut dyn RngCore>,
107      ) -> Result<(KZGCommitment<E>, KZGRandomness<E>), PCError> {
108          Self::check_degree_is_too_large(polynomial.degree(), powers.size())?;
109  
110          let commit_time = start_timer!(|| format!(
111              "Committing to polynomial of degree {} with hiding_bound: {:?}",
112              polynomial.degree(),
113              hiding_bound,
114          ));
115  
116          let mut commitment = match polynomial {
117              Polynomial::Dense(polynomial) => {
118                  let (num_leading_zeros, plain_coeffs) = skip_leading_zeros_and_convert_to_bigints(polynomial);
119  
120                  let bases = &powers.powers_of_beta_g[num_leading_zeros..(num_leading_zeros + plain_coeffs.len())];
121  
122                  let msm_time = start_timer!(|| "MSM to compute commitment to plaintext poly");
123                  let commitment = VariableBase::msm(bases, &plain_coeffs);
124                  end_timer!(msm_time);
125  
126                  commitment
127              }
128              Polynomial::Sparse(polynomial) => polynomial
129                  .coeffs()
130                  .map(|(i, coeff)| {
131                      powers.powers_of_beta_g[*i].mul_bits(BitIteratorBE::new_without_leading_zeros(coeff.to_bigint()))
132                  })
133                  .sum(),
134          };
135  
136          let mut randomness = KZGRandomness::empty();
137          if let Some(hiding_degree) = hiding_bound {
138              let mut rng = rng.ok_or(PCError::MissingRng)?;
139              let sample_random_poly_time =
140                  start_timer!(|| format!("Sampling a random polynomial of degree {hiding_degree}"));
141  
142              randomness = KZGRandomness::rand(hiding_degree, false, &mut rng);
143              Self::check_hiding_bound(
144                  randomness.blinding_polynomial.degree(),
145                  powers.powers_of_beta_times_gamma_g.len(),
146              )?;
147              end_timer!(sample_random_poly_time);
148          }
149  
150          let random_ints = convert_to_bigints(&randomness.blinding_polynomial.coeffs);
151          let msm_time = start_timer!(|| "MSM to compute commitment to random poly");
152          let random_commitment =
153              VariableBase::msm(&powers.powers_of_beta_times_gamma_g, random_ints.as_slice()).to_affine();
154          end_timer!(msm_time);
155  
156          commitment.add_assign_mixed(&random_commitment);
157  
158          end_timer!(commit_time);
159          Ok((KZGCommitment(commitment.into()), randomness))
160      }
161  
162      /// Outputs a commitment to `polynomial`.
163      pub fn commit_lagrange(
164          lagrange_basis: &LagrangeBasis<E>,
165          evaluations: &[E::Fr],
166          hiding_bound: Option<usize>,
167          rng: Option<&mut dyn RngCore>,
168      ) -> Result<(KZGCommitment<E>, KZGRandomness<E>), PCError> {
169          Self::check_degree_is_too_large(evaluations.len() - 1, lagrange_basis.size())?;
170          assert_eq!(
171              evaluations.len().checked_next_power_of_two().ok_or(PCError::LagrangeBasisSizeIsTooLarge)?,
172              lagrange_basis.size()
173          );
174  
175          let commit_time = start_timer!(|| format!(
176              "Committing to polynomial of degree {} with hiding_bound: {:?}",
177              evaluations.len() - 1,
178              hiding_bound,
179          ));
180  
181          let evaluations = evaluations.iter().map(|e| e.to_bigint()).collect::<Vec<_>>();
182          let msm_time = start_timer!(|| "MSM to compute commitment to plaintext poly");
183          let mut commitment = VariableBase::msm(&lagrange_basis.lagrange_basis_at_beta_g, &evaluations);
184          end_timer!(msm_time);
185  
186          let mut randomness = KZGRandomness::empty();
187          if let Some(hiding_degree) = hiding_bound {
188              let mut rng = rng.ok_or(PCError::MissingRng)?;
189              let sample_random_poly_time =
190                  start_timer!(|| format!("Sampling a random polynomial of degree {hiding_degree}"));
191  
192              randomness = KZGRandomness::rand(hiding_degree, false, &mut rng);
193              Self::check_hiding_bound(
194                  randomness.blinding_polynomial.degree(),
195                  lagrange_basis.powers_of_beta_times_gamma_g.len(),
196              )?;
197              end_timer!(sample_random_poly_time);
198          }
199  
200          let random_ints = convert_to_bigints(&randomness.blinding_polynomial.coeffs);
201          let msm_time = start_timer!(|| "MSM to compute commitment to random poly");
202          let random_commitment =
203              VariableBase::msm(&lagrange_basis.powers_of_beta_times_gamma_g, random_ints.as_slice()).to_affine();
204          end_timer!(msm_time);
205  
206          commitment.add_assign_mixed(&random_commitment);
207  
208          end_timer!(commit_time);
209          Ok((KZGCommitment(commitment.into()), randomness))
210      }
211  
212      /// Compute witness polynomial.
213      ///
214      /// The witness polynomial w(x) the quotient of the division (p(x) - p(z)) /
215      /// (x - z) Observe that this quotient does not change with z because
216      /// p(z) is the remainder term. We can therefore omit p(z) when computing
217      /// the quotient.
218      pub fn compute_witness_polynomial(
219          polynomial: &DensePolynomial<E::Fr>,
220          point: E::Fr,
221          randomness: &KZGRandomness<E>,
222      ) -> Result<(DensePolynomial<E::Fr>, Option<DensePolynomial<E::Fr>>), PCError> {
223          let divisor = DensePolynomial::from_coefficients_vec(vec![-point, E::Fr::one()]);
224  
225          let witness_time = start_timer!(|| "Computing witness polynomial");
226          let witness_polynomial = polynomial / &divisor;
227          end_timer!(witness_time);
228  
229          let random_witness_polynomial = if randomness.is_hiding() {
230              let random_p = &randomness.blinding_polynomial;
231  
232              let witness_time = start_timer!(|| "Computing random witness polynomial");
233              let random_witness_polynomial = random_p / &divisor;
234              end_timer!(witness_time);
235              Some(random_witness_polynomial)
236          } else {
237              None
238          };
239  
240          Ok((witness_polynomial, random_witness_polynomial))
241      }
242  
243      pub(crate) fn open_with_witness_polynomial(
244          powers: &Powers<E>,
245          point: E::Fr,
246          randomness: &KZGRandomness<E>,
247          witness_polynomial: &DensePolynomial<E::Fr>,
248          hiding_witness_polynomial: Option<&DensePolynomial<E::Fr>>,
249      ) -> Result<KZGProof<E>, PCError> {
250          Self::check_degree_is_too_large(witness_polynomial.degree(), powers.size())?;
251          let (num_leading_zeros, witness_coeffs) = skip_leading_zeros_and_convert_to_bigints(witness_polynomial);
252  
253          let bases = &powers.powers_of_beta_g[num_leading_zeros..(num_leading_zeros + witness_coeffs.len())];
254  
255          let witness_comm_time = start_timer!(|| "Computing commitment to witness polynomial");
256          let mut w = VariableBase::msm(bases, &witness_coeffs);
257          end_timer!(witness_comm_time);
258  
259          let random_v = if let Some(hiding_witness_polynomial) = hiding_witness_polynomial {
260              let blinding_p = &randomness.blinding_polynomial;
261              let blinding_eval_time = start_timer!(|| "Evaluating random polynomial");
262              let blinding_evaluation = blinding_p.evaluate(point);
263              end_timer!(blinding_eval_time);
264  
265              let random_witness_coeffs = convert_to_bigints(&hiding_witness_polynomial.coeffs);
266              let witness_comm_time = start_timer!(|| "Computing commitment to random witness polynomial");
267              w += &VariableBase::msm(&powers.powers_of_beta_times_gamma_g, &random_witness_coeffs);
268              end_timer!(witness_comm_time);
269              Some(blinding_evaluation)
270          } else {
271              None
272          };
273  
274          Ok(KZGProof { w: w.to_affine(), random_v })
275      }
276  
277      /// On input a polynomial `p` in Lagrange basis, and a point `point`,
278      /// outputs an evaluation proof for the same.
279      pub fn open_lagrange(
280          lagrange_basis: &LagrangeBasis<E>,
281          domain_elements: &[E::Fr],
282          evaluations: &[E::Fr],
283          point: E::Fr,
284          evaluation_at_point: E::Fr,
285      ) -> Result<KZGProof<E>> {
286          Self::check_degree_is_too_large(evaluations.len() - 1, lagrange_basis.size())?;
287          // Ensure that the point is not in the domain
288          if lagrange_basis.domain.evaluate_vanishing_polynomial(point).is_zero() {
289              Err(anyhow!("Point cannot be in the domain"))?;
290          }
291          if evaluations.len().checked_next_power_of_two().ok_or_else(|| anyhow!("Evaluations length is too large"))?
292              != lagrange_basis.size()
293          {
294              Err(anyhow!("`evaluations.len()` must equal `domain.size()`"))?;
295          }
296  
297          let mut divisor_evals = cfg_iter!(domain_elements).map(|&e| e - point).collect::<Vec<_>>();
298          alphavm_fields::batch_inversion(&mut divisor_evals);
299          ensure!(divisor_evals.len() == evaluations.len());
300          cfg_iter_mut!(divisor_evals).zip_eq(evaluations).for_each(|(divisor_eval, &eval)| {
301              *divisor_eval *= eval - evaluation_at_point;
302          });
303          let (witness_comm, _) = Self::commit_lagrange(lagrange_basis, &divisor_evals, None, None)?;
304  
305          Ok(KZGProof { w: witness_comm.0, random_v: None })
306      }
307  
308      /// On input a polynomial `p` and a point `point`, outputs a proof for the
309      /// same.
310      pub fn open(
311          powers: &Powers<E>,
312          polynomial: &DensePolynomial<E::Fr>,
313          point: E::Fr,
314          rand: &KZGRandomness<E>,
315      ) -> Result<KZGProof<E>, PCError> {
316          Self::check_degree_is_too_large(polynomial.degree(), powers.size())?;
317          let open_time = start_timer!(|| format!("Opening polynomial of degree {}", polynomial.degree()));
318  
319          let witness_time = start_timer!(|| "Computing witness polynomials");
320          let (witness_poly, hiding_witness_poly) = Self::compute_witness_polynomial(polynomial, point, rand)?;
321          end_timer!(witness_time);
322  
323          let proof =
324              Self::open_with_witness_polynomial(powers, point, rand, &witness_poly, hiding_witness_poly.as_ref());
325  
326          end_timer!(open_time);
327          proof
328      }
329  
330      /// Verifies that `value` is the evaluation at `point` of the polynomial
331      /// committed inside `commitment`.
332      pub fn check(
333          vk: &VerifierKey<E>,
334          commitment: &KZGCommitment<E>,
335          point: E::Fr,
336          value: E::Fr,
337          proof: &KZGProof<E>,
338      ) -> Result<bool, PCError> {
339          let check_time = start_timer!(|| "Checking evaluation");
340          let mut inner = commitment.0.to_projective() - vk.g.to_projective().mul(value);
341          if let Some(random_v) = proof.random_v {
342              inner -= &vk.gamma_g.mul(random_v);
343          }
344          let lhs = E::pairing(inner, vk.h);
345  
346          let inner = vk.beta_h.to_projective() - vk.h.mul(point);
347          let rhs = E::pairing(proof.w, inner);
348  
349          end_timer!(check_time, || format!("Result: {}", lhs == rhs));
350          Ok(lhs == rhs)
351      }
352  
353      /// Check that each `proof_i` in `proofs` is a valid proof of evaluation for
354      /// `commitment_i` at `point_i`.
355      pub fn batch_check<R: RngCore>(
356          vk: &VerifierKey<E>,
357          commitments: &[KZGCommitment<E>],
358          points: &[E::Fr],
359          values: &[E::Fr],
360          proofs: &[KZGProof<E>],
361          rng: &mut R,
362      ) -> Result<bool> {
363          let check_time = start_timer!(|| format!("Checking {} evaluation proofs", commitments.len()));
364          let g = vk.g.to_projective();
365          let gamma_g = vk.gamma_g.to_projective();
366  
367          let mut total_c = <E::G1Projective>::zero();
368          let mut total_w = <E::G1Projective>::zero();
369  
370          let combination_time = start_timer!(|| "Combining commitments and proofs");
371          let mut randomizer = E::Fr::one();
372          // Instead of multiplying g and gamma_g in each turn, we simply accumulate
373          // their coefficients and perform a final multiplication at the end.
374          let mut g_multiplier = E::Fr::zero();
375          let mut gamma_g_multiplier = E::Fr::zero();
376          ensure!(commitments.len() == points.len());
377          ensure!(commitments.len() == values.len());
378          ensure!(commitments.len() == proofs.len());
379          for (((c, z), v), proof) in commitments.iter().zip_eq(points).zip_eq(values).zip_eq(proofs) {
380              let w = proof.w;
381              let mut temp = w.mul(*z);
382              temp.add_assign_mixed(&c.0);
383              let c = temp;
384              g_multiplier += &(randomizer * v);
385              if let Some(random_v) = proof.random_v {
386                  gamma_g_multiplier += &(randomizer * random_v);
387              }
388              total_c += &c.mul(randomizer);
389              total_w += &w.mul(randomizer);
390              // We don't need to sample randomizers from the full field,
391              // only from 128-bit strings.
392              randomizer = u128::rand(rng).into();
393          }
394          total_c -= &g.mul(g_multiplier);
395          total_c -= &gamma_g.mul(gamma_g_multiplier);
396          end_timer!(combination_time);
397  
398          let to_affine_time = start_timer!(|| "Converting results to affine for pairing");
399          let affine_points = E::G1Projective::batch_normalization_into_affine(vec![-total_w, total_c]);
400          let (total_w, total_c) = (affine_points[0], affine_points[1]);
401          end_timer!(to_affine_time);
402  
403          let pairing_time = start_timer!(|| "Performing product of pairings");
404          let result = E::product_of_pairings(
405              [(&total_w.prepare(), &vk.prepared_beta_h), (&total_c.prepare(), &vk.prepared_h)].iter().copied(),
406          )
407          .is_one();
408          end_timer!(pairing_time);
409          end_timer!(check_time, || format!("Result: {result}"));
410          Ok(result)
411      }
412  
413      pub(crate) fn check_degree_is_too_large(degree: usize, num_powers: usize) -> Result<(), PCError> {
414          let num_coefficients = degree + 1;
415          if num_coefficients > num_powers {
416              Err(PCError::TooManyCoefficients { num_coefficients, num_powers })
417          } else {
418              Ok(())
419          }
420      }
421  
422      pub(crate) fn check_hiding_bound(hiding_poly_degree: usize, num_powers: usize) -> Result<(), PCError> {
423          if hiding_poly_degree == 0 {
424              Err(PCError::HidingBoundIsZero)
425          } else if hiding_poly_degree >= num_powers {
426              // The above check uses `>=` because committing to a hiding poly with
427              // degree `hiding_poly_degree` requires `hiding_poly_degree + 1` powers.
428              Err(PCError::HidingBoundToolarge { hiding_poly_degree, num_powers })
429          } else {
430              Ok(())
431          }
432      }
433  
434      pub(crate) fn check_degrees_and_bounds<'a>(
435          max_degree: usize,
436          enforced_degree_bounds: Option<&[usize]>,
437          p: impl Into<LabeledPolynomialWithBasis<'a, E::Fr>>,
438      ) -> Result<(), PCError> {
439          let p = p.into();
440          if let Some(bound) = p.degree_bound() {
441              let enforced_degree_bounds = enforced_degree_bounds.ok_or(PCError::UnsupportedDegreeBound(bound))?;
442  
443              if enforced_degree_bounds.binary_search(&bound).is_err() {
444                  Err(PCError::UnsupportedDegreeBound(bound))
445              } else if bound < p.degree() || bound > max_degree {
446                  Err(PCError::IncorrectDegreeBound {
447                      poly_degree: p.degree(),
448                      degree_bound: p.degree_bound().unwrap(),
449                      max_degree,
450                      label: p.label().to_string(),
451                  })
452              } else {
453                  Ok(())
454              }
455          } else {
456              Ok(())
457          }
458      }
459  }
460  
461  fn skip_leading_zeros_and_convert_to_bigints<F: PrimeField>(p: &DensePolynomial<F>) -> (usize, Vec<F::BigInteger>) {
462      if p.coeffs.is_empty() {
463          (0, vec![])
464      } else {
465          let num_leading_zeros = p.coeffs.iter().take_while(|c| c.is_zero()).count();
466          let coeffs = if num_leading_zeros == p.coeffs.len() {
467              vec![]
468          } else {
469              convert_to_bigints(&p.coeffs[num_leading_zeros..])
470          };
471          (num_leading_zeros, coeffs)
472      }
473  }
474  
475  fn convert_to_bigints<F: PrimeField>(p: &[F]) -> Vec<F::BigInteger> {
476      let to_bigint_time = start_timer!(|| "Converting polynomial coeffs to bigints");
477      let coeffs = cfg_iter!(p).map(|s| s.to_bigint()).collect::<Vec<_>>();
478      end_timer!(to_bigint_time);
479      coeffs
480  }
481  
482  #[cfg(test)]
483  mod tests {
484      #![allow(non_camel_case_types)]
485      #![allow(clippy::needless_borrow)]
486      use super::*;
487      use alphavm_curves::bls12_377::{Bls12_377, Fr};
488      use alphavm_utilities::{rand::TestRng, FromBytes, ToBytes};
489  
490      use std::borrow::Cow;
491  
492      type KZG_Bls12_377 = KZG10<Bls12_377>;
493  
494      impl<E: PairingEngine> KZG10<E> {
495          /// Specializes the public parameters for a given maximum degree `d` for
496          /// polynomials `d` should be less that `pp.max_degree()`.
497          pub(crate) fn trim(
498              pp: &UniversalParams<E>,
499              mut supported_degree: usize,
500              hiding_bound: Option<usize>,
501          ) -> (Powers<'_, E>, VerifierKey<E>) {
502              if supported_degree == 1 {
503                  supported_degree += 1;
504              }
505              let powers_of_beta_g = pp.powers_of_beta_g(0, supported_degree + 1).unwrap().to_vec();
506  
507              let powers_of_beta_times_gamma_g = if let Some(hiding_bound) = hiding_bound {
508                  (0..=(hiding_bound + 1)).map(|i| pp.powers_of_beta_times_gamma_g()[&i]).collect()
509              } else {
510                  vec![]
511              };
512  
513              let powers = Powers {
514                  powers_of_beta_g: Cow::Owned(powers_of_beta_g),
515                  powers_of_beta_times_gamma_g: Cow::Owned(powers_of_beta_times_gamma_g),
516              };
517              let vk = VerifierKey {
518                  g: pp.power_of_beta_g(0).unwrap(),
519                  gamma_g: pp.powers_of_beta_times_gamma_g()[&0],
520                  h: pp.h,
521                  beta_h: pp.beta_h(),
522                  prepared_h: pp.prepared_h.clone(),
523                  prepared_beta_h: pp.prepared_beta_h.clone(),
524              };
525              (powers, vk)
526          }
527      }
528  
529      #[test]
530      fn test_kzg10_universal_params_serialization() {
531          let degree = 4;
532          let pp = KZG_Bls12_377::load_srs(degree).unwrap();
533  
534          let pp_bytes = pp.to_bytes_le().unwrap();
535          let pp_recovered: UniversalParams<Bls12_377> = FromBytes::read_le(&pp_bytes[..]).unwrap();
536          let pp_recovered_bytes = pp_recovered.to_bytes_le().unwrap();
537  
538          assert_eq!(&pp_bytes, &pp_recovered_bytes);
539      }
540  
541      fn end_to_end_test_template<E: PairingEngine>() -> Result<(), PCError> {
542          let rng = &mut TestRng::default();
543          for _ in 0..100 {
544              let mut degree = 0;
545              while degree <= 1 {
546                  degree = usize::rand(rng) % 20;
547              }
548              let pp = KZG10::<E>::load_srs(degree)?;
549              let hiding_bound = Some(1);
550              let (ck, vk) = KZG10::trim(&pp, degree, hiding_bound);
551              let p = DensePolynomial::rand(degree, rng);
552              let (comm, rand) = KZG10::<E>::commit(&ck, &(&p).into(), hiding_bound, Some(rng))?;
553              let point = E::Fr::rand(rng);
554              let value = p.evaluate(point);
555              let proof = KZG10::<E>::open(&ck, &p, point, &rand)?;
556              assert!(
557                  KZG10::<E>::check(&vk, &comm, point, value, &proof)?,
558                  "proof was incorrect for max_degree = {}, polynomial_degree = {}, hiding_bound = {:?}",
559                  degree,
560                  p.degree(),
561                  hiding_bound,
562              );
563          }
564          Ok(())
565      }
566  
567      fn linear_polynomial_test_template<E: PairingEngine>() -> Result<(), PCError> {
568          let rng = &mut TestRng::default();
569          for _ in 0..100 {
570              let degree = 50;
571              let pp = KZG10::<E>::load_srs(degree)?;
572              let hiding_bound = Some(1);
573              let (ck, vk) = KZG10::trim(&pp, 2, hiding_bound);
574              let p = DensePolynomial::rand(1, rng);
575              let (comm, rand) = KZG10::<E>::commit(&ck, &(&p).into(), hiding_bound, Some(rng))?;
576              let point = E::Fr::rand(rng);
577              let value = p.evaluate(point);
578              let proof = KZG10::<E>::open(&ck, &p, point, &rand)?;
579              assert!(
580                  KZG10::<E>::check(&vk, &comm, point, value, &proof)?,
581                  "proof was incorrect for max_degree = {}, polynomial_degree = {}, hiding_bound = {:?}",
582                  degree,
583                  p.degree(),
584                  hiding_bound,
585              );
586          }
587          Ok(())
588      }
589  
590      fn batch_check_test_template<E: PairingEngine>() -> Result<(), PCError> {
591          let rng = &mut TestRng::default();
592          for _ in 0..10 {
593              let hiding_bound = Some(1);
594              let mut degree = 0;
595              while degree <= 1 {
596                  degree = usize::rand(rng) % 20;
597              }
598              let pp = KZG10::<E>::load_srs(degree)?;
599              let (ck, vk) = KZG10::trim(&pp, degree, hiding_bound);
600  
601              let mut comms = Vec::new();
602              let mut values = Vec::new();
603              let mut points = Vec::new();
604              let mut proofs = Vec::new();
605  
606              for _ in 0..10 {
607                  let p = DensePolynomial::rand(degree, rng);
608                  let (comm, rand) = KZG10::<E>::commit(&ck, &(&p).into(), hiding_bound, Some(rng))?;
609                  let point = E::Fr::rand(rng);
610                  let value = p.evaluate(point);
611                  let proof = KZG10::<E>::open(&ck, &p, point, &rand)?;
612  
613                  assert!(KZG10::<E>::check(&vk, &comm, point, value, &proof)?);
614                  comms.push(comm);
615                  values.push(value);
616                  points.push(point);
617                  proofs.push(proof);
618              }
619              assert!(KZG10::<E>::batch_check(&vk, &comms, &points, &values, &proofs, rng)?);
620          }
621          Ok(())
622      }
623  
624      #[test]
625      fn test_end_to_end() {
626          end_to_end_test_template::<Bls12_377>().expect("test failed for bls12-377");
627      }
628  
629      #[test]
630      fn test_linear_polynomial() {
631          linear_polynomial_test_template::<Bls12_377>().expect("test failed for bls12-377");
632      }
633  
634      #[test]
635      fn test_batch_check() {
636          batch_check_test_template::<Bls12_377>().expect("test failed for bls12-377");
637      }
638  
639      #[test]
640      fn test_degree_is_too_large() {
641          let rng = &mut TestRng::default();
642  
643          let max_degree = 123;
644          let pp = KZG_Bls12_377::load_srs(max_degree).unwrap();
645          let (powers, _) = KZG_Bls12_377::trim(&pp, max_degree, None);
646  
647          let p = DensePolynomial::<Fr>::rand(max_degree + 1, rng);
648          assert!(p.degree() > max_degree);
649          assert!(KZG_Bls12_377::check_degree_is_too_large(p.degree(), powers.size()).is_err());
650      }
651  }