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