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, CanonicalSerialize, CanonicalDeserialize)]
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 fn is_hiding() -> bool {
97 if H {
98 return true;
99 }
100 false
101 }
102
103 /// setup returns the tuple (ProverKey, VerifierKey). For real world deployments the setup must
104 /// be computed in the most trustless way possible, usually through a MPC ceremony.
105 fn setup(
106 mut rng: impl RngCore,
107 len: usize,
108 ) -> Result<(Self::ProverParams, Self::VerifierParams), Error> {
109 let len = len.next_power_of_two();
110 let universal_params =
111 KZG10::<E, DensePolynomial<E::ScalarField>>::setup(len, false, &mut rng)
112 .expect("Setup failed");
113 let powers_of_g = universal_params.powers_of_g[..=len].to_vec();
114 let powers = ProverKey::<E::G1> {
115 powers_of_g: ark_std::borrow::Cow::Owned(powers_of_g),
116 };
117 let vk = VerifierKey {
118 g: universal_params.powers_of_g[0],
119 gamma_g: universal_params.powers_of_gamma_g[&0],
120 h: universal_params.h,
121 beta_h: universal_params.beta_h,
122 prepared_h: universal_params.prepared_h.clone(),
123 prepared_beta_h: universal_params.prepared_beta_h.clone(),
124 };
125 Ok((powers, vk))
126 }
127
128 /// commit implements the CommitmentScheme commit interface, adapting the implementation from
129 /// https://github.com/arkworks-rs/poly-commit/tree/c724fa666e935bbba8db5a1421603bab542e15ab/poly-commit/src/kzg10/mod.rs#L178
130 /// with the main difference being the removal of the blinding factors and the no-dependency to
131 /// the Pairing trait.
132 fn commit(
133 params: &Self::ProverParams,
134 v: &[E::ScalarField],
135 _blind: &E::ScalarField,
136 ) -> Result<E::G1, Error> {
137 if !_blind.is_zero() || H {
138 return Err(Error::NotSupportedYet("hiding".to_string()));
139 }
140
141 let polynomial = poly_from_vec(v.to_vec())?;
142 check_degree_is_too_large(polynomial.degree(), params.powers_of_g.len())?;
143
144 let (num_leading_zeros, plain_coeffs) =
145 skip_first_zero_coeffs_and_convert_to_bigints(&polynomial);
146 let commitment = <E::G1 as VariableBaseMSM>::msm_bigint(
147 ¶ms.powers_of_g[num_leading_zeros..],
148 &plain_coeffs,
149 );
150 Ok(commitment)
151 }
152
153 /// prove implements the CommitmentScheme prove interface, adapting the implementation from
154 /// https://github.com/arkworks-rs/poly-commit/tree/c724fa666e935bbba8db5a1421603bab542e15ab/poly-commit/src/kzg10/mod.rs#L307
155 /// with the main difference being the removal of the blinding factors and the no-dependency to
156 /// the Pairing trait.
157 fn prove(
158 params: &Self::ProverParams,
159 transcript: &mut impl Transcript<E::ScalarField>,
160 cm: &E::G1,
161 v: &[E::ScalarField],
162 _blind: &E::ScalarField,
163 _rng: Option<&mut dyn RngCore>,
164 ) -> Result<Self::Proof, Error> {
165 transcript.absorb_nonnative(cm);
166 let challenge = transcript.get_challenge();
167 Self::prove_with_challenge(params, challenge, v, _blind, _rng)
168 }
169
170 fn prove_with_challenge(
171 params: &Self::ProverParams,
172 challenge: Self::ProverChallenge,
173 v: &[E::ScalarField],
174 _blind: &E::ScalarField,
175 _rng: Option<&mut dyn RngCore>,
176 ) -> Result<Self::Proof, Error> {
177 if !_blind.is_zero() || H {
178 return Err(Error::NotSupportedYet("hiding".to_string()));
179 }
180
181 let polynomial = poly_from_vec(v.to_vec())?;
182 check_degree_is_too_large(polynomial.degree(), params.powers_of_g.len())?;
183
184 // Compute q(x) = (p(x) - p(z)) / (x-z). Observe that this quotient does not change with z
185 // because p(z) is the remainder term. We can therefore omit p(z) when computing the
186 // quotient.
187 let divisor = DensePolynomial::<E::ScalarField>::from_coefficients_vec(vec![
188 -challenge,
189 E::ScalarField::one(),
190 ]);
191 let (witness_poly, remainder_poly) = DenseOrSparsePolynomial::from(&polynomial)
192 .divide_with_q_and_r(&DenseOrSparsePolynomial::from(&divisor))
193 // the panic inside `divide_with_q_and_r` should never be reached, since the divisor
194 // polynomial is constructed right before and is set to not be zero. And the `.unwrap`
195 // should not give an error.
196 .unwrap();
197
198 let eval = if remainder_poly.is_zero() {
199 E::ScalarField::zero()
200 } else {
201 remainder_poly[0]
202 };
203
204 check_degree_is_too_large(witness_poly.degree(), params.powers_of_g.len())?;
205 let (num_leading_zeros, witness_coeffs) =
206 skip_first_zero_coeffs_and_convert_to_bigints(&witness_poly);
207 let proof = <E::G1 as VariableBaseMSM>::msm_bigint(
208 ¶ms.powers_of_g[num_leading_zeros..],
209 &witness_coeffs,
210 );
211
212 Ok(Proof { eval, proof })
213 }
214
215 fn verify(
216 params: &Self::VerifierParams,
217 transcript: &mut impl Transcript<E::ScalarField>,
218 cm: &E::G1,
219 proof: &Self::Proof,
220 ) -> Result<(), Error> {
221 transcript.absorb_nonnative(cm);
222 let challenge = transcript.get_challenge();
223 Self::verify_with_challenge(params, challenge, cm, proof)
224 }
225
226 fn verify_with_challenge(
227 params: &Self::VerifierParams,
228 challenge: Self::Challenge,
229 cm: &E::G1,
230 proof: &Self::Proof,
231 ) -> Result<(), Error> {
232 if H {
233 return Err(Error::NotSupportedYet("hiding".to_string()));
234 }
235
236 // verify the KZG proof using arkworks method
237 let v = KZG10::<E, DensePolynomial<E::ScalarField>>::check(
238 params, // vk
239 &KZG10Commitment(cm.into_affine()),
240 challenge,
241 proof.eval,
242 &KZG10Proof::<E> {
243 w: proof.proof.into_affine(),
244 random_v: None,
245 },
246 )?;
247 if !v {
248 return Err(Error::CommitmentVerificationFail);
249 }
250 Ok(())
251 }
252}
253
254fn check_degree_is_too_large(
255 degree: usize,
256 num_powers: usize,
257) -> Result<(), ark_poly_commit::error::Error> {
258 let num_coefficients = degree + 1;
259 if num_coefficients > num_powers {
260 Err(ark_poly_commit::error::Error::TooManyCoefficients {
261 num_coefficients,
262 num_powers,
263 })
264 } else {
265 Ok(())
266 }
267}
268
269fn skip_first_zero_coeffs_and_convert_to_bigints<F: PrimeField, P: DenseUVPolynomial<F>>(
270 p: &P,
271) -> (usize, Vec<F::BigInt>) {
272 let mut num_leading_zeros = 0;
273 while num_leading_zeros < p.coeffs().len() && p.coeffs()[num_leading_zeros].is_zero() {
274 num_leading_zeros += 1;
275 }
276 let coeffs = convert_to_bigints(&p.coeffs()[num_leading_zeros..]);
277 (num_leading_zeros, coeffs)
278}
279
280fn convert_to_bigints<F: PrimeField>(p: &[F]) -> Vec<F::BigInt> {
281 ark_std::cfg_iter!(p)
282 .map(|s| s.into_bigint())
283 .collect::<Vec<_>>()
284}
285
286#[cfg(test)]
287mod tests {
288 use ark_bn254::{Bn254, Fr, G1Projective as G1};
289 use ark_crypto_primitives::sponge::{poseidon::PoseidonSponge, CryptographicSponge};
290 use ark_std::{test_rng, UniformRand};
291
292 use super::*;
293 use crate::transcript::poseidon::poseidon_canonical_config;
294
295 #[test]
296 fn test_kzg_commitment_scheme() {
297 let mut rng = &mut test_rng();
298 let poseidon_config = poseidon_canonical_config::<Fr>();
299 let transcript_p = &mut PoseidonSponge::<Fr>::new(&poseidon_config);
300 let transcript_v = &mut PoseidonSponge::<Fr>::new(&poseidon_config);
301
302 let n = 10;
303 let (pk, vk): (ProverKey<G1>, VerifierKey<Bn254>) =
304 KZG::<Bn254>::setup(&mut rng, n).unwrap();
305
306 let v: Vec<Fr> = std::iter::repeat_with(|| Fr::rand(rng)).take(n).collect();
307 let cm = KZG::<Bn254>::commit(&pk, &v, &Fr::zero()).unwrap();
308
309 let proof = KZG::<Bn254>::prove(&pk, transcript_p, &cm, &v, &Fr::zero(), None).unwrap();
310
311 // verify the proof:
312 KZG::<Bn254>::verify(&vk, transcript_v, &cm, &proof).unwrap();
313 }
314}