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::pcs::{
 10    prelude::Commitment, PCSError, PolynomialCommitmentScheme, StructuredReferenceString,
 11};
 12use ark_ec::{msm::VariableBaseMSM, AffineCurve, PairingEngine, ProjectiveCurve};
 13use ark_ff::PrimeField;
 14use ark_poly::{univariate::DensePolynomial, Polynomial, UVPolynomial};
 15use ark_serialize::{CanonicalDeserialize, CanonicalSerialize, Read, SerializationError, Write};
 16use ark_std::{
 17    borrow::Borrow,
 18    end_timer, format,
 19    marker::PhantomData,
 20    rand::{CryptoRng, RngCore},
 21    start_timer,
 22    string::ToString,
 23    vec,
 24    vec::Vec,
 25    One,
 26};
 27use srs::{UnivariateProverParam, UnivariateUniversalParams, UnivariateVerifierParam};
 28
 29pub(crate) mod srs;
 30
 31/// KZG Polynomial Commitment Scheme on univariate polynomial.
 32pub struct UnivariateKzgPCS<E: PairingEngine> {
 33    #[doc(hidden)]
 34    phantom: PhantomData<E>,
 35}
 36
 37#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug, PartialEq, Eq)]
 38/// proof of opening
 39pub struct UnivariateKzgProof<E: PairingEngine> {
 40    /// Evaluation of quotients
 41    pub proof: E::G1Affine,
 42}
 43/// batch proof
 44pub type UnivariateKzgBatchProof<E> = Vec<UnivariateKzgProof<E>>;
 45
 46impl<E: PairingEngine> PolynomialCommitmentScheme<E> for UnivariateKzgPCS<E> {
 47    // Parameters
 48    type ProverParam = UnivariateProverParam<E::G1Affine>;
 49    type VerifierParam = UnivariateVerifierParam<E>;
 50    type SRS = UnivariateUniversalParams<E>;
 51    // Polynomial and its associated types
 52    type Polynomial = DensePolynomial<E::Fr>;
 53    type Point = E::Fr;
 54    type Evaluation = E::Fr;
 55    // Polynomial and its associated types
 56    type Commitment = Commitment<E>;
 57    type Proof = UnivariateKzgProof<E>;
 58
 59    // We do not implement batch univariate KZG at the current version.
 60    type BatchProof = ();
 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: Option<usize>,
 81        supported_num_vars: Option<usize>,
 82    ) -> Result<(Self::ProverParam, Self::VerifierParam), PCSError> {
 83        assert!(supported_num_vars.is_none());
 84        if supported_num_vars.is_some() {
 85            return Err(PCSError::InvalidParameters(
 86                "univariate should not receive a num_var param".to_string(),
 87            ));
 88        }
 89        srs.borrow().trim(supported_degree.unwrap())
 90    }
 91
 92    /// Generate a commitment for a polynomial
 93    /// Note that the scheme is not hidding
 94    fn commit(
 95        prover_param: impl Borrow<Self::ProverParam>,
 96        poly: &Self::Polynomial,
 97    ) -> Result<Self::Commitment, PCSError> {
 98        let prover_param = prover_param.borrow();
 99        let commit_time =
100            start_timer!(|| format!("Committing to polynomial of degree {} ", poly.degree()));
101
102        if poly.degree() >= prover_param.powers_of_g.len() {
103            return Err(PCSError::InvalidParameters(format!(
104                "uni poly degree {} is larger than allowed {}",
105                poly.degree(),
106                prover_param.powers_of_g.len()
107            )));
108        }
109
110        let (num_leading_zeros, plain_coeffs) = skip_leading_zeros_and_convert_to_bigints(poly);
111
112        let msm_time = start_timer!(|| "MSM to compute commitment to plaintext poly");
113        let commitment = VariableBaseMSM::multi_scalar_mul(
114            &prover_param.powers_of_g[num_leading_zeros..],
115            &plain_coeffs,
116        )
117        .into_affine();
118        end_timer!(msm_time);
119
120        end_timer!(commit_time);
121        Ok(Commitment(commitment))
122    }
123
124    /// On input a polynomial `p` and a point `point`, outputs a proof for the
125    /// same.
126    fn open(
127        prover_param: impl Borrow<Self::ProverParam>,
128        polynomial: &Self::Polynomial,
129        point: &Self::Point,
130    ) -> Result<(Self::Proof, Self::Evaluation), PCSError> {
131        let open_time =
132            start_timer!(|| format!("Opening polynomial of degree {}", polynomial.degree()));
133        let divisor = Self::Polynomial::from_coefficients_vec(vec![-*point, E::Fr::one()]);
134
135        let witness_time = start_timer!(|| "Computing witness polynomial");
136        let witness_polynomial = polynomial / &divisor;
137        end_timer!(witness_time);
138
139        let (num_leading_zeros, witness_coeffs) =
140            skip_leading_zeros_and_convert_to_bigints(&witness_polynomial);
141
142        let proof = VariableBaseMSM::multi_scalar_mul(
143            &prover_param.borrow().powers_of_g[num_leading_zeros..],
144            &witness_coeffs,
145        )
146        .into_affine();
147
148        let eval = polynomial.evaluate(point);
149
150        end_timer!(open_time);
151        Ok((Self::Proof { proof }, eval))
152    }
153
154    /// Verifies that `value` is the evaluation at `x` of the polynomial
155    /// committed inside `comm`.
156    fn verify(
157        verifier_param: &Self::VerifierParam,
158        commitment: &Self::Commitment,
159        point: &Self::Point,
160        value: &E::Fr,
161        proof: &Self::Proof,
162    ) -> Result<bool, PCSError> {
163        let check_time = start_timer!(|| "Checking evaluation");
164        let pairing_inputs: Vec<(E::G1Prepared, E::G2Prepared)> = vec![
165            (
166                (verifier_param.g.mul(value.into_repr())
167                    - proof.proof.mul(point.into_repr())
168                    - commitment.0.into_projective())
169                .into_affine()
170                .into(),
171                verifier_param.h.into(),
172            ),
173            (proof.proof.into(), verifier_param.beta_h.into()),
174        ];
175
176        let res = E::product_of_pairings(pairing_inputs.iter()).is_one();
177
178        end_timer!(check_time, || format!("Result: {}", res));
179        Ok(res)
180    }
181}
182
183fn skip_leading_zeros_and_convert_to_bigints<F: PrimeField, P: UVPolynomial<F>>(
184    p: &P,
185) -> (usize, Vec<F::BigInt>) {
186    let mut num_leading_zeros = 0;
187    while num_leading_zeros < p.coeffs().len() && p.coeffs()[num_leading_zeros].is_zero() {
188        num_leading_zeros += 1;
189    }
190    let coeffs = convert_to_bigints(&p.coeffs()[num_leading_zeros..]);
191    (num_leading_zeros, coeffs)
192}
193
194fn convert_to_bigints<F: PrimeField>(p: &[F]) -> Vec<F::BigInt> {
195    let to_bigint_time = start_timer!(|| "Converting polynomial coeffs to bigints");
196    let coeffs = p.iter().map(|s| s.into_repr()).collect::<Vec<_>>();
197    end_timer!(to_bigint_time);
198    coeffs
199}
200
201#[cfg(test)]
202mod tests {
203    use super::*;
204    use crate::StructuredReferenceString;
205    use ark_bls12_381::Bls12_381;
206    use ark_ec::PairingEngine;
207    use ark_poly::univariate::DensePolynomial;
208    use ark_std::{test_rng, UniformRand};
209
210    fn end_to_end_test_template<E>() -> Result<(), PCSError>
211    where
212        E: PairingEngine,
213    {
214        let rng = &mut test_rng();
215        for _ in 0..100 {
216            let mut degree = 0;
217            while degree <= 1 {
218                degree = usize::rand(rng) % 20;
219            }
220            let pp = UnivariateKzgPCS::<E>::gen_srs_for_testing(rng, degree)?;
221            let (ck, vk) = pp.trim(degree)?;
222            let p = <DensePolynomial<E::Fr> as UVPolynomial<E::Fr>>::rand(degree, rng);
223            let comm = UnivariateKzgPCS::<E>::commit(&ck, &p)?;
224            let point = E::Fr::rand(rng);
225            let (proof, value) = UnivariateKzgPCS::<E>::open(&ck, &p, &point)?;
226            assert!(
227                UnivariateKzgPCS::<E>::verify(&vk, &comm, &point, &value, &proof)?,
228                "proof was incorrect for max_degree = {}, polynomial_degree = {}",
229                degree,
230                p.degree(),
231            );
232        }
233        Ok(())
234    }
235
236    fn linear_polynomial_test_template<E>() -> Result<(), PCSError>
237    where
238        E: PairingEngine,
239    {
240        let rng = &mut test_rng();
241        for _ in 0..100 {
242            let degree = 50;
243
244            let pp = UnivariateKzgPCS::<E>::gen_srs_for_testing(rng, degree)?;
245            let (ck, vk) = pp.trim(degree)?;
246            let p = <DensePolynomial<E::Fr> as UVPolynomial<E::Fr>>::rand(degree, rng);
247            let comm = UnivariateKzgPCS::<E>::commit(&ck, &p)?;
248            let point = E::Fr::rand(rng);
249            let (proof, value) = UnivariateKzgPCS::<E>::open(&ck, &p, &point)?;
250            assert!(
251                UnivariateKzgPCS::<E>::verify(&vk, &comm, &point, &value, &proof)?,
252                "proof was incorrect for max_degree = {}, polynomial_degree = {}",
253                degree,
254                p.degree(),
255            );
256        }
257        Ok(())
258    }
259
260    #[test]
261    fn end_to_end_test() {
262        end_to_end_test_template::<Bls12_381>().expect("test failed for bls12-381");
263    }
264
265    #[test]
266    fn linear_polynomial_test() {
267        linear_polynomial_test_template::<Bls12_381>().expect("test failed for bls12-381");
268    }
269}