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