1/// Adaptation of the prover methods and structs from arkworks/poly-commit's KZG10 implementation
  2/// into the CommitmentScheme trait.
  3///
  4/// The motivation to do so, is that we want to be able to use KZG / Pedersen for committing to
  5/// vectors indistinctly, and the arkworks KZG10 implementation contains all the methods under the
  6/// same trait, which requires the Pairing trait, where the prover does not need access to the
  7/// Pairing but only to G1.
  8use ark_ec::{pairing::Pairing, CurveGroup, VariableBaseMSM};
  9use ark_ff::PrimeField;
 10use ark_poly::{
 11    univariate::{DenseOrSparsePolynomial, DensePolynomial},
 12    DenseUVPolynomial, Polynomial,
 13};
 14use ark_poly_commit::kzg10::{
 15    Commitment as KZG10Commitment, Proof as KZG10Proof, VerifierKey, KZG10,
 16};
 17use ark_std::rand::RngCore;
 18use ark_std::{borrow::Cow, fmt::Debug};
 19use ark_std::{One, Zero};
 20use core::marker::PhantomData;
 21use rayon::iter::{IntoParallelRefIterator, ParallelIterator};
 22
 23use super::CommitmentScheme;
 24use crate::transcript::Transcript;
 25use crate::utils::vec::poly_from_vec;
 26use crate::Error;
 27
 28/// ProverKey defines a similar struct as in ark_poly_commit::kzg10::Powers, but instead of
 29/// depending on the Pairing trait it depends on the CurveGroup trait.
 30#[derive(Debug, Clone, Default, Eq, PartialEq)]
 31pub struct ProverKey<'a, C: CurveGroup> {
 32    /// Group elements of the form `β^i G`, for different values of `i`.
 33    pub powers_of_g: Cow<'a, [C::Affine]>,
 34}
 35
 36#[derive(Debug, Clone, Default, Eq, PartialEq)]
 37pub struct Proof<C: CurveGroup> {
 38    pub eval: C::ScalarField,
 39    pub proof: C,
 40}
 41
 42/// KZG implements the CommitmentScheme trait for the KZG commitment scheme.
 43#[derive(Debug, Clone, Default, Eq, PartialEq)]
 44pub struct KZG<'a, E: Pairing, const H: bool = false> {
 45    _a: PhantomData<&'a ()>,
 46    _e: PhantomData<E>,
 47}
 48impl<'a, E, const H: bool> CommitmentScheme<E::G1, H> for KZG<'a, E, H>
 49where
 50    E: Pairing,
 51{
 52    type ProverParams = ProverKey<'a, E::G1>;
 53    type VerifierParams = VerifierKey<E>;
 54    type Proof = Proof<E::G1>;
 55    type ProverChallenge = E::ScalarField;
 56    type Challenge = E::ScalarField;
 57
 58    /// setup returns the tuple (ProverKey, VerifierKey). For real world deployments the setup must
 59    /// be computed in the most trustless way possible, usually through a MPC ceremony.
 60    fn setup(
 61        mut rng: impl RngCore,
 62        len: usize,
 63    ) -> Result<(Self::ProverParams, Self::VerifierParams), Error> {
 64        let len = len.next_power_of_two();
 65        let universal_params =
 66            KZG10::<E, DensePolynomial<E::ScalarField>>::setup(len, false, &mut rng)
 67                .expect("Setup failed");
 68        let powers_of_g = universal_params.powers_of_g[..=len].to_vec();
 69        let powers = ProverKey::<E::G1> {
 70            powers_of_g: ark_std::borrow::Cow::Owned(powers_of_g),
 71        };
 72        let vk = VerifierKey {
 73            g: universal_params.powers_of_g[0],
 74            gamma_g: universal_params.powers_of_gamma_g[&0],
 75            h: universal_params.h,
 76            beta_h: universal_params.beta_h,
 77            prepared_h: universal_params.prepared_h.clone(),
 78            prepared_beta_h: universal_params.prepared_beta_h.clone(),
 79        };
 80        Ok((powers, vk))
 81    }
 82
 83    /// commit implements the CommitmentScheme commit interface, adapting the implementation from
 84    /// https://github.com/arkworks-rs/poly-commit/tree/c724fa666e935bbba8db5a1421603bab542e15ab/poly-commit/src/kzg10/mod.rs#L178
 85    /// with the main difference being the removal of the blinding factors and the no-dependency to
 86    /// the Pairing trait.
 87    fn commit(
 88        params: &Self::ProverParams,
 89        v: &[E::ScalarField],
 90        _blind: &E::ScalarField,
 91    ) -> Result<E::G1, Error> {
 92        if !_blind.is_zero() || H {
 93            return Err(Error::NotSupportedYet("hiding".to_string()));
 94        }
 95
 96        let polynomial = poly_from_vec(v.to_vec())?;
 97        check_degree_is_too_large(polynomial.degree(), params.powers_of_g.len())?;
 98
 99        let (num_leading_zeros, plain_coeffs) =
100            skip_first_zero_coeffs_and_convert_to_bigints(&polynomial);
101        let commitment = <E::G1 as VariableBaseMSM>::msm_bigint(
102            &params.powers_of_g[num_leading_zeros..],
103            &plain_coeffs,
104        );
105        Ok(commitment)
106    }
107
108    /// prove implements the CommitmentScheme prove interface, adapting the implementation from
109    /// https://github.com/arkworks-rs/poly-commit/tree/c724fa666e935bbba8db5a1421603bab542e15ab/poly-commit/src/kzg10/mod.rs#L307
110    /// with the main difference being the removal of the blinding factors and the no-dependency to
111    /// the Pairing trait.
112    fn prove(
113        params: &Self::ProverParams,
114        transcript: &mut impl Transcript<E::G1>,
115        cm: &E::G1,
116        v: &[E::ScalarField],
117        _blind: &E::ScalarField,
118        _rng: Option<&mut dyn RngCore>,
119    ) -> Result<Self::Proof, Error> {
120        transcript.absorb_point(cm)?;
121        let challenge = transcript.get_challenge();
122        Self::prove_with_challenge(params, challenge, v, _blind, _rng)
123    }
124
125    fn prove_with_challenge(
126        params: &Self::ProverParams,
127        challenge: Self::ProverChallenge,
128        v: &[E::ScalarField],
129        _blind: &E::ScalarField,
130        _rng: Option<&mut dyn RngCore>,
131    ) -> Result<Self::Proof, Error> {
132        if !_blind.is_zero() || H {
133            return Err(Error::NotSupportedYet("hiding".to_string()));
134        }
135
136        let polynomial = poly_from_vec(v.to_vec())?;
137        check_degree_is_too_large(polynomial.degree(), params.powers_of_g.len())?;
138
139        // Compute q(x) = (p(x) - p(z)) / (x-z). Observe that this quotient does not change with z
140        // because p(z) is the remainder term. We can therefore omit p(z) when computing the
141        // quotient.
142        let divisor = DensePolynomial::<E::ScalarField>::from_coefficients_vec(vec![
143            -challenge,
144            E::ScalarField::one(),
145        ]);
146        let (witness_poly, remainder_poly) = DenseOrSparsePolynomial::from(&polynomial)
147            .divide_with_q_and_r(&DenseOrSparsePolynomial::from(&divisor))
148            // the panic inside `divide_with_q_and_r` should never be reached, since the divisor
149            // polynomial is constructed right before and is set to not be zero. And the `.unwrap`
150            // should not give an error.
151            .unwrap();
152
153        let eval = if remainder_poly.is_zero() {
154            E::ScalarField::zero()
155        } else {
156            remainder_poly[0]
157        };
158
159        check_degree_is_too_large(witness_poly.degree(), params.powers_of_g.len())?;
160        let (num_leading_zeros, witness_coeffs) =
161            skip_first_zero_coeffs_and_convert_to_bigints(&witness_poly);
162        let proof = <E::G1 as VariableBaseMSM>::msm_bigint(
163            &params.powers_of_g[num_leading_zeros..],
164            &witness_coeffs,
165        );
166
167        Ok(Proof { eval, proof })
168    }
169
170    fn verify(
171        params: &Self::VerifierParams,
172        transcript: &mut impl Transcript<E::G1>,
173        cm: &E::G1,
174        proof: &Self::Proof,
175    ) -> Result<(), Error> {
176        transcript.absorb_point(cm)?;
177        let challenge = transcript.get_challenge();
178        Self::verify_with_challenge(params, challenge, cm, proof)
179    }
180
181    fn verify_with_challenge(
182        params: &Self::VerifierParams,
183        challenge: Self::Challenge,
184        cm: &E::G1,
185        proof: &Self::Proof,
186    ) -> Result<(), Error> {
187        if H {
188            return Err(Error::NotSupportedYet("hiding".to_string()));
189        }
190
191        // verify the KZG proof using arkworks method
192        let v = KZG10::<E, DensePolynomial<E::ScalarField>>::check(
193            params, // vk
194            &KZG10Commitment(cm.into_affine()),
195            challenge,
196            proof.eval,
197            &KZG10Proof::<E> {
198                w: proof.proof.into_affine(),
199                random_v: None,
200            },
201        )?;
202        if !v {
203            return Err(Error::CommitmentVerificationFail);
204        }
205        Ok(())
206    }
207}
208
209fn check_degree_is_too_large(
210    degree: usize,
211    num_powers: usize,
212) -> Result<(), ark_poly_commit::error::Error> {
213    let num_coefficients = degree + 1;
214    if num_coefficients > num_powers {
215        Err(ark_poly_commit::error::Error::TooManyCoefficients {
216            num_coefficients,
217            num_powers,
218        })
219    } else {
220        Ok(())
221    }
222}
223
224fn skip_first_zero_coeffs_and_convert_to_bigints<F: PrimeField, P: DenseUVPolynomial<F>>(
225    p: &P,
226) -> (usize, Vec<F::BigInt>) {
227    let mut num_leading_zeros = 0;
228    while num_leading_zeros < p.coeffs().len() && p.coeffs()[num_leading_zeros].is_zero() {
229        num_leading_zeros += 1;
230    }
231    let coeffs = convert_to_bigints(&p.coeffs()[num_leading_zeros..]);
232    (num_leading_zeros, coeffs)
233}
234
235fn convert_to_bigints<F: PrimeField>(p: &[F]) -> Vec<F::BigInt> {
236    ark_std::cfg_iter!(p)
237        .map(|s| s.into_bigint())
238        .collect::<Vec<_>>()
239}
240
241#[cfg(test)]
242mod tests {
243    use ark_bn254::{Bn254, Fr, G1Projective as G1};
244    use ark_std::{test_rng, UniformRand};
245
246    use super::*;
247    use crate::transcript::poseidon::{poseidon_canonical_config, PoseidonTranscript};
248
249    #[test]
250    fn test_kzg_commitment_scheme() {
251        let mut rng = &mut test_rng();
252        let poseidon_config = poseidon_canonical_config::<Fr>();
253        let transcript_p = &mut PoseidonTranscript::<G1>::new(&poseidon_config);
254        let transcript_v = &mut PoseidonTranscript::<G1>::new(&poseidon_config);
255
256        let n = 10;
257        let (pk, vk): (ProverKey<G1>, VerifierKey<Bn254>) =
258            KZG::<Bn254>::setup(&mut rng, n).unwrap();
259
260        let v: Vec<Fr> = std::iter::repeat_with(|| Fr::rand(rng)).take(n).collect();
261        let cm = KZG::<Bn254>::commit(&pk, &v, &Fr::zero()).unwrap();
262
263        let proof = KZG::<Bn254>::prove(&pk, transcript_p, &cm, &v, &Fr::zero(), None).unwrap();
264
265        // verify the proof:
266        KZG::<Bn254>::verify(&vk, transcript_v, &cm, &proof).unwrap();
267    }
268}