1// Copyright (c) 2023 Espresso Systems (espressosys.com)
  2// This file is part of the HyperPlonk library.
  3
  4// You should have received a copy of the MIT License
  5// along with the HyperPlonk library. If not, see <https://mit-license.org/>.
  6
  7//! Main module for univariate KZG commitment scheme
  8
  9use crate::pcs::{
 10    prelude::Commitment, PCSError, PolynomialCommitmentScheme, StructuredReferenceString,
 11};
 12use ark_ec::{
 13    pairing::Pairing, scalar_mul::variable_base::VariableBaseMSM, AffineRepr, CurveGroup,
 14};
 15use ark_ff::PrimeField;
 16use ark_poly::{univariate::DensePolynomial, DenseUVPolynomial, Polynomial};
 17use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
 18use ark_std::{
 19    borrow::Borrow, end_timer, format, marker::PhantomData, rand::Rng, start_timer,
 20    string::ToString, vec, vec::Vec, One,
 21};
 22use srs::{UnivariateProverParam, UnivariateUniversalParams, UnivariateVerifierParam};
 23use std::ops::Mul;
 24
 25pub(crate) mod srs;
 26
 27/// KZG Polynomial Commitment Scheme on univariate polynomial.
 28pub struct UnivariateKzgPCS<E: Pairing> {
 29    #[doc(hidden)]
 30    phantom: PhantomData<E>,
 31}
 32
 33#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug, PartialEq, Eq)]
 34/// proof of opening
 35pub struct UnivariateKzgProof<E: Pairing> {
 36    /// Evaluation of quotients
 37    pub proof: E::G1Affine,
 38}
 39/// batch proof
 40pub type UnivariateKzgBatchProof<E> = Vec<UnivariateKzgProof<E>>;
 41
 42impl<E: Pairing> PolynomialCommitmentScheme<E> for UnivariateKzgPCS<E> {
 43    // Parameters
 44    type ProverParam = UnivariateProverParam<E::G1Affine>;
 45    type VerifierParam = UnivariateVerifierParam<E>;
 46    type SRS = UnivariateUniversalParams<E>;
 47    // Polynomial and its associated types
 48    type Polynomial = DensePolynomial<E::ScalarField>;
 49    type Point = E::ScalarField;
 50    type Evaluation = E::ScalarField;
 51    // Polynomial and its associated types
 52    type Commitment = Commitment<E>;
 53    type Proof = UnivariateKzgProof<E>;
 54
 55    // We do not implement batch univariate KZG at the current version.
 56    type BatchProof = ();
 57
 58    /// Build SRS for testing.
 59    ///
 60    /// - For univariate polynomials, `supported_size` is the maximum degree.
 61    ///
 62    /// WARNING: THIS FUNCTION IS FOR TESTING PURPOSE ONLY.
 63    /// THE OUTPUT SRS SHOULD NOT BE USED IN PRODUCTION.
 64    fn gen_srs_for_testing<R: Rng>(
 65        rng: &mut R,
 66        supported_size: usize,
 67    ) -> Result<Self::SRS, PCSError> {
 68        Self::SRS::gen_srs_for_testing(rng, supported_size)
 69    }
 70
 71    /// Trim the universal parameters to specialize the public parameters.
 72    /// Input `max_degree` for univariate.
 73    /// `supported_num_vars` must be None or an error is returned.
 74    fn trim(
 75        srs: impl Borrow<Self::SRS>,
 76        supported_degree: Option<usize>,
 77        supported_num_vars: Option<usize>,
 78    ) -> Result<(Self::ProverParam, Self::VerifierParam), PCSError> {
 79        assert!(supported_num_vars.is_none());
 80        if supported_num_vars.is_some() {
 81            return Err(PCSError::InvalidParameters(
 82                "univariate should not receive a num_var param".to_string(),
 83            ));
 84        }
 85        srs.borrow().trim(supported_degree.unwrap())
 86    }
 87
 88    /// Generate a commitment for a polynomial
 89    /// Note that the scheme is not hidding
 90    fn commit(
 91        prover_param: impl Borrow<Self::ProverParam>,
 92        poly: &Self::Polynomial,
 93    ) -> Result<Self::Commitment, PCSError> {
 94        let prover_param = prover_param.borrow();
 95        let commit_time =
 96            start_timer!(|| format!("Committing to polynomial of degree {} ", poly.degree()));
 97
 98        if poly.degree() >= prover_param.powers_of_g.len() {
 99            return Err(PCSError::InvalidParameters(format!(
100                "uni poly degree {} is larger than allowed {}",
101                poly.degree(),
102                prover_param.powers_of_g.len()
103            )));
104        }
105
106        let (num_leading_zeros, plain_coeffs) = skip_leading_zeros(poly);
107
108        let msm_time = start_timer!(|| "MSM to compute commitment to plaintext poly");
109        let commitment = E::G1::msm_unchecked(
110            &prover_param.powers_of_g[num_leading_zeros..],
111            &plain_coeffs,
112        )
113        .into_affine();
114        end_timer!(msm_time);
115
116        end_timer!(commit_time);
117        Ok(Commitment(commitment))
118    }
119
120    /// On input a polynomial `p` and a point `point`, outputs a proof for the
121    /// same.
122    fn open(
123        prover_param: impl Borrow<Self::ProverParam>,
124        polynomial: &Self::Polynomial,
125        point: &Self::Point,
126    ) -> Result<(Self::Proof, Self::Evaluation), PCSError> {
127        let open_time =
128            start_timer!(|| format!("Opening polynomial of degree {}", polynomial.degree()));
129        let divisor = Self::Polynomial::from_coefficients_vec(vec![-*point, E::ScalarField::one()]);
130
131        let witness_time = start_timer!(|| "Computing witness polynomial");
132        let witness_polynomial = polynomial / &divisor;
133        end_timer!(witness_time);
134
135        let (num_leading_zeros, witness_coeffs) = skip_leading_zeros(&witness_polynomial);
136
137        let proof = E::G1::msm_unchecked(
138            &prover_param.borrow().powers_of_g[num_leading_zeros..],
139            &witness_coeffs,
140        )
141        .into_affine();
142
143        let eval = polynomial.evaluate(point);
144
145        end_timer!(open_time);
146        Ok((Self::Proof { proof }, eval))
147    }
148
149    /// Verifies that `value` is the evaluation at `x` of the polynomial
150    /// committed inside `comm`.
151    fn verify(
152        verifier_param: &Self::VerifierParam,
153        commitment: &Self::Commitment,
154        point: &Self::Point,
155        value: &E::ScalarField,
156        proof: &Self::Proof,
157    ) -> Result<bool, PCSError> {
158        let check_time = start_timer!(|| "Checking evaluation");
159        let pairing_inputs: Vec<(E::G1Prepared, E::G2Prepared)> = vec![
160            (
161                (verifier_param.g.mul(value) - proof.proof.mul(point) - commitment.0.into_group())
162                    .into_affine()
163                    .into(),
164                verifier_param.h.into(),
165            ),
166            (proof.proof.into(), verifier_param.beta_h.into()),
167        ];
168
169        let p1 = pairing_inputs.iter().map(|(a, _)| a.clone());
170        let p2 = pairing_inputs.iter().map(|(_, a)| a.clone());
171
172        let res = E::multi_pairing(p1, p2).0.is_one();
173
174        end_timer!(check_time, || format!("Result: {}", res));
175        Ok(res)
176    }
177}
178
179fn skip_leading_zeros<F: PrimeField, P: DenseUVPolynomial<F>>(p: &P) -> (usize, &[F]) {
180    let mut num_leading_zeros = 0;
181    while num_leading_zeros < p.coeffs().len() && p.coeffs()[num_leading_zeros].is_zero() {
182        num_leading_zeros += 1;
183    }
184    (num_leading_zeros, &p.coeffs()[num_leading_zeros..])
185}
186
187#[cfg(test)]
188mod tests {
189    use super::*;
190    use crate::StructuredReferenceString;
191    use ark_bls12_381::Bls12_381;
192    use ark_ec::pairing::Pairing;
193    use ark_poly::univariate::DensePolynomial;
194    use ark_std::{test_rng, UniformRand};
195
196    fn end_to_end_test_template<E>() -> Result<(), PCSError>
197    where
198        E: Pairing,
199    {
200        let rng = &mut test_rng();
201        for _ in 0..100 {
202            let mut degree = 0;
203            while degree <= 1 {
204                degree = usize::rand(rng) % 20;
205            }
206            let pp = UnivariateKzgPCS::<E>::gen_srs_for_testing(rng, degree)?;
207            let (ck, vk) = pp.trim(degree)?;
208            let p = <DensePolynomial<E::ScalarField> as DenseUVPolynomial<E::ScalarField>>::rand(
209                degree, rng,
210            );
211            let comm = UnivariateKzgPCS::<E>::commit(&ck, &p)?;
212            let point = E::ScalarField::rand(rng);
213            let (proof, value) = UnivariateKzgPCS::<E>::open(&ck, &p, &point)?;
214            assert!(
215                UnivariateKzgPCS::<E>::verify(&vk, &comm, &point, &value, &proof)?,
216                "proof was incorrect for max_degree = {}, polynomial_degree = {}",
217                degree,
218                p.degree(),
219            );
220        }
221        Ok(())
222    }
223
224    fn linear_polynomial_test_template<E>() -> Result<(), PCSError>
225    where
226        E: Pairing,
227    {
228        let rng = &mut test_rng();
229        for _ in 0..100 {
230            let degree = 50;
231
232            let pp = UnivariateKzgPCS::<E>::gen_srs_for_testing(rng, degree)?;
233            let (ck, vk) = pp.trim(degree)?;
234            let p = <DensePolynomial<E::ScalarField> as DenseUVPolynomial<E::ScalarField>>::rand(
235                degree, rng,
236            );
237            let comm = UnivariateKzgPCS::<E>::commit(&ck, &p)?;
238            let point = E::ScalarField::rand(rng);
239            let (proof, value) = UnivariateKzgPCS::<E>::open(&ck, &p, &point)?;
240            assert!(
241                UnivariateKzgPCS::<E>::verify(&vk, &comm, &point, &value, &proof)?,
242                "proof was incorrect for max_degree = {}, polynomial_degree = {}",
243                degree,
244                p.degree(),
245            );
246        }
247        Ok(())
248    }
249
250    #[test]
251    fn end_to_end_test() {
252        end_to_end_test_template::<Bls12_381>().expect("test failed for bls12-381");
253    }
254
255    #[test]
256    fn linear_polynomial_test() {
257        linear_polynomial_test_template::<Bls12_381>().expect("test failed for bls12-381");
258    }
259}