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