snarkvm_algorithms/polycommit/kzg10/
data_structures.rs

1// Copyright 2024-2025 Aleo Network Foundation
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use crate::{
17    AlgebraicSponge,
18    fft::{DensePolynomial, EvaluationDomain},
19};
20use snarkvm_curves::{AffineCurve, PairingCurve, PairingEngine, ProjectiveCurve};
21use snarkvm_fields::{ConstraintFieldError, ToConstraintField, Zero};
22use snarkvm_parameters::mainnet::PowersOfG;
23use snarkvm_utilities::{
24    FromBytes,
25    ToBytes,
26    borrow::Cow,
27    error,
28    io::{Read, Write},
29    serialize::{CanonicalDeserialize, CanonicalSerialize, Compress, SerializationError, Valid, Validate},
30};
31
32use crate::srs::{UniversalProver, UniversalVerifier};
33use anyhow::Result;
34use core::ops::{Add, AddAssign};
35use rand_core::RngCore;
36use std::{collections::BTreeMap, io, ops::Range, sync::Arc};
37
38/// `UniversalParams` are the universal parameters for the KZG10 scheme.
39#[derive(Clone, Debug)]
40pub struct UniversalParams<E: PairingEngine> {
41    /// Group elements of the form `{ \beta^i G }`, where `i` ranges from 0 to
42    /// `degree`, and group elements of the form `{ \beta^i \gamma G }`,
43    /// where `i` ranges from 0 to `degree`. This struct provides an
44    /// abstraction over the powers which are located on-disk
45    /// to reduce memory usage.
46    powers: Arc<PowersOfG<E>>,
47    /// The generator of G2.
48    pub h: E::G2Affine,
49    /// The generator of G2, prepared for use in pairings.
50    pub prepared_h: <E::G2Affine as PairingCurve>::Prepared,
51    /// \beta times the above generator of G2, prepared for use in pairings.
52    pub prepared_beta_h: <E::G2Affine as PairingCurve>::Prepared,
53}
54
55impl<E: PairingEngine> UniversalParams<E> {
56    pub fn load() -> Result<Self> {
57        let powers = Arc::new(PowersOfG::<E>::load()?);
58        let h = E::G2Affine::prime_subgroup_generator();
59        let prepared_h = h.prepare();
60        let prepared_beta_h = powers.beta_h().prepare();
61
62        Ok(Self { powers, h, prepared_h, prepared_beta_h })
63    }
64
65    pub fn download_powers_for(&self, range: Range<usize>) -> Result<()> {
66        self.powers.download_powers_for(range)
67    }
68
69    pub fn lagrange_basis(&self, domain: EvaluationDomain<E::Fr>) -> Result<Vec<E::G1Affine>> {
70        let basis = domain
71            .ifft(&self.powers_of_beta_g(0, domain.size())?.iter().map(|e| (*e).to_projective()).collect::<Vec<_>>());
72        Ok(E::G1Projective::batch_normalization_into_affine(basis))
73    }
74
75    pub fn power_of_beta_g(&self, index: usize) -> Result<E::G1Affine> {
76        self.powers.power_of_beta_g(index)
77    }
78
79    pub fn powers_of_beta_g(&self, lower: usize, upper: usize) -> Result<Vec<E::G1Affine>> {
80        self.powers.powers_of_beta_g(lower..upper)
81    }
82
83    pub fn powers_of_beta_times_gamma_g(&self) -> &BTreeMap<usize, E::G1Affine> {
84        self.powers.powers_of_beta_gamma_g()
85    }
86
87    pub fn beta_h(&self) -> E::G2Affine {
88        self.powers.beta_h()
89    }
90
91    pub fn max_degree(&self) -> usize {
92        self.powers.max_num_powers() - 1
93    }
94
95    pub fn to_universal_prover(&self) -> Result<UniversalProver<E>> {
96        Ok(UniversalProver::<E> { max_degree: self.max_degree(), _unused: None })
97    }
98
99    pub fn to_universal_verifier(&self) -> Result<UniversalVerifier<E>> {
100        let g = self.power_of_beta_g(0)?;
101        let h = self.h;
102        let beta_h = self.beta_h();
103        let gamma_g = self.powers_of_beta_times_gamma_g()[&0];
104        let prepared_h = self.prepared_h.clone();
105        let prepared_beta_h = self.prepared_beta_h.clone();
106
107        Ok(UniversalVerifier {
108            vk: VerifierKey::<E> { g, gamma_g, h, beta_h, prepared_h, prepared_beta_h },
109            prepared_negative_powers_of_beta_h: self.powers.prepared_negative_powers_of_beta_h(),
110        })
111    }
112}
113
114impl<E: PairingEngine> FromBytes for UniversalParams<E> {
115    fn read_le<R: Read>(mut reader: R) -> io::Result<Self> {
116        // Deserialize `powers`.
117        let powers = Arc::new(PowersOfG::read_le(&mut reader)?);
118
119        // Deserialize `h`.
120        let h: E::G2Affine = FromBytes::read_le(&mut reader)?;
121
122        // Deserialize `prepared_h`.
123        let prepared_h: <E::G2Affine as PairingCurve>::Prepared = FromBytes::read_le(&mut reader)?;
124
125        // Deserialize `prepared_beta_h`.
126        let prepared_beta_h: <E::G2Affine as PairingCurve>::Prepared = FromBytes::read_le(&mut reader)?;
127
128        Ok(Self { powers, h, prepared_h, prepared_beta_h })
129    }
130}
131
132impl<E: PairingEngine> ToBytes for UniversalParams<E> {
133    fn write_le<W: Write>(&self, mut writer: W) -> io::Result<()> {
134        // Serialize powers.
135        self.powers.write_le(&mut writer)?;
136
137        // Serialize `h`.
138        self.h.write_le(&mut writer)?;
139
140        // Serialize `prepared_h`.
141        self.prepared_h.write_le(&mut writer)?;
142
143        // Serialize `prepared_beta_h`.
144        self.prepared_beta_h.write_le(&mut writer)?;
145
146        Ok(())
147    }
148}
149
150/// `Powers` is used to commit to and create evaluation proofs for a given
151/// polynomial.
152#[derive(Clone, Debug, Default, Hash)]
153pub struct Powers<'a, E: PairingEngine> {
154    /// Group elements of the form `β^i G`, for different values of `i`.
155    pub powers_of_beta_g: Cow<'a, [E::G1Affine]>,
156    /// Group elements of the form `β^i γG`, for different values of `i`.
157    pub powers_of_beta_times_gamma_g: Cow<'a, [E::G1Affine]>,
158}
159
160impl<E: PairingEngine> Powers<'_, E> {
161    /// The number of powers in `self`.
162    pub fn size(&self) -> usize {
163        self.powers_of_beta_g.len()
164    }
165}
166/// `LagrangeBasis` is used to commit to and create evaluation proofs for a
167/// given polynomial.
168#[derive(Clone, Debug, Hash)]
169pub struct LagrangeBasis<'a, E: PairingEngine> {
170    /// Group elements of the form `β^i G`, for different values of `i`.
171    pub lagrange_basis_at_beta_g: Cow<'a, [E::G1Affine]>,
172    /// Group elements of the form `β^i γG`, for different values of `i`.
173    pub powers_of_beta_times_gamma_g: Cow<'a, [E::G1Affine]>,
174    /// Domain representing the multiplicative subgroup the powers
175    /// in `self.lagrange_basis_at_beta_g` are defined over.
176    pub domain: EvaluationDomain<E::Fr>,
177}
178
179impl<E: PairingEngine> LagrangeBasis<'_, E> {
180    /// The number of powers in `self`.
181    pub fn size(&self) -> usize {
182        self.lagrange_basis_at_beta_g.len()
183    }
184}
185
186/// `VerifierKey` is used to check evaluation proofs for a given commitment.
187#[derive(Clone, Debug, Default, PartialEq, Eq)]
188pub struct VerifierKey<E: PairingEngine> {
189    /// The generator of G1.
190    pub g: E::G1Affine,
191    /// The generator of G1 that is used for making a commitment hiding.
192    pub gamma_g: E::G1Affine,
193    /// The generator of G2.
194    pub h: E::G2Affine,
195    /// \beta times the above generator of G2.
196    pub beta_h: E::G2Affine,
197    /// The generator of G2, prepared for use in pairings.
198    pub prepared_h: <E::G2Affine as PairingCurve>::Prepared,
199    /// \beta times the above generator of G2, prepared for use in pairings.
200    pub prepared_beta_h: <E::G2Affine as PairingCurve>::Prepared,
201}
202
203impl<E: PairingEngine> CanonicalSerialize for VerifierKey<E> {
204    fn serialize_with_mode<W: Write>(&self, mut writer: W, compress: Compress) -> Result<(), SerializationError> {
205        self.g.serialize_with_mode(&mut writer, compress)?;
206        self.gamma_g.serialize_with_mode(&mut writer, compress)?;
207        self.h.serialize_with_mode(&mut writer, compress)?;
208        self.beta_h.serialize_with_mode(&mut writer, compress)?;
209        Ok(())
210    }
211
212    fn serialized_size(&self, compress: Compress) -> usize {
213        self.g.serialized_size(compress)
214            + self.gamma_g.serialized_size(compress)
215            + self.h.serialized_size(compress)
216            + self.beta_h.serialized_size(compress)
217    }
218}
219
220impl<E: PairingEngine> CanonicalDeserialize for VerifierKey<E> {
221    fn deserialize_with_mode<R: Read>(
222        mut reader: R,
223        compress: Compress,
224        validate: Validate,
225    ) -> Result<Self, SerializationError> {
226        let g = CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?;
227        let gamma_g = CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?;
228        let h: E::G2Affine = CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?;
229        let beta_h: E::G2Affine = CanonicalDeserialize::deserialize_with_mode(&mut reader, compress, validate)?;
230        let prepared_h = h.prepare();
231        let prepared_beta_h = beta_h.prepare();
232        Ok(VerifierKey { g, gamma_g, h, beta_h, prepared_h, prepared_beta_h })
233    }
234}
235
236impl<E: PairingEngine> Valid for VerifierKey<E> {
237    fn check(&self) -> Result<(), SerializationError> {
238        Valid::check(&self.g)?;
239        Valid::check(&self.gamma_g)?;
240        Valid::check(&self.h)?;
241        Valid::check(&self.beta_h)?;
242        Ok(())
243    }
244
245    fn batch_check<'a>(batch: impl Iterator<Item = &'a Self> + Send) -> Result<(), SerializationError>
246    where
247        Self: 'a,
248    {
249        let batch: Vec<_> = batch.collect();
250        Valid::batch_check(batch.iter().map(|v| &v.g))?;
251        Valid::batch_check(batch.iter().map(|v| &v.gamma_g))?;
252        Valid::batch_check(batch.iter().map(|v| &v.h))?;
253        Valid::batch_check(batch.iter().map(|v| &v.beta_h))?;
254        Ok(())
255    }
256}
257
258impl<E: PairingEngine> FromBytes for VerifierKey<E> {
259    fn read_le<R: Read>(mut reader: R) -> io::Result<Self> {
260        CanonicalDeserialize::deserialize_compressed(&mut reader)
261            .map_err(|_| error("could not deserialize VerifierKey"))
262    }
263}
264
265impl<E: PairingEngine> ToBytes for VerifierKey<E> {
266    fn write_le<W: Write>(&self, mut writer: W) -> io::Result<()> {
267        CanonicalSerialize::serialize_compressed(self, &mut writer)
268            .map_err(|_| error("could not serialize VerifierKey"))
269    }
270}
271
272/// `KZGCommitment` commits to a polynomial. It is output by `KZG10::commit`.
273#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, Hash, CanonicalSerialize, CanonicalDeserialize)]
274pub struct KZGCommitment<E: PairingEngine>(
275    /// The commitment is a group element.
276    pub E::G1Affine,
277);
278
279impl<E: PairingEngine> FromBytes for KZGCommitment<E> {
280    fn read_le<R: Read>(mut reader: R) -> io::Result<Self> {
281        CanonicalDeserialize::deserialize_compressed(&mut reader)
282            .map_err(|_| error("could not deserialize KZGCommitment"))
283    }
284}
285
286impl<E: PairingEngine> ToBytes for KZGCommitment<E> {
287    fn write_le<W: Write>(&self, mut writer: W) -> io::Result<()> {
288        CanonicalSerialize::serialize_compressed(self, &mut writer)
289            .map_err(|_| error("could not serialize KZGCommitment"))
290    }
291}
292
293impl<E: PairingEngine> KZGCommitment<E> {
294    #[inline]
295    pub fn empty() -> Self {
296        KZGCommitment(E::G1Affine::zero())
297    }
298
299    pub fn has_degree_bound(&self) -> bool {
300        false
301    }
302
303    pub fn is_in_correct_subgroup_assuming_on_curve(&self) -> bool {
304        self.0.is_in_correct_subgroup_assuming_on_curve()
305    }
306}
307
308impl<E: PairingEngine> ToConstraintField<E::Fq> for KZGCommitment<E> {
309    fn to_field_elements(&self) -> Result<Vec<E::Fq>, ConstraintFieldError> {
310        self.0.to_field_elements()
311    }
312}
313
314/// `KZGRandomness` hides the polynomial inside a commitment. It is output by
315/// `KZG10::commit`.
316#[derive(Clone, Debug, Default, PartialEq, Eq, Hash, CanonicalSerialize, CanonicalDeserialize)]
317pub struct KZGRandomness<E: PairingEngine> {
318    /// For KZG10, the commitment randomness is a random polynomial.
319    pub blinding_polynomial: DensePolynomial<E::Fr>,
320}
321impl<E: PairingEngine> FromBytes for KZGRandomness<E> {
322    fn read_le<R: Read>(mut reader: R) -> io::Result<Self> {
323        CanonicalDeserialize::deserialize_compressed(&mut reader)
324            .map_err(|_| error("could not deserialize KZGRandomness"))
325    }
326}
327
328impl<E: PairingEngine> ToBytes for KZGRandomness<E> {
329    fn write_le<W: Write>(&self, mut writer: W) -> io::Result<()> {
330        CanonicalSerialize::serialize_compressed(self, &mut writer)
331            .map_err(|_| error("could not serialize KZGRandomness"))
332    }
333}
334
335impl<E: PairingEngine> KZGRandomness<E> {
336    /// Does `self` provide any hiding properties to the corresponding
337    /// commitment? `self.is_hiding() == true` only if the underlying
338    /// polynomial is non-zero.
339    #[inline]
340    pub fn is_hiding(&self) -> bool {
341        !self.blinding_polynomial.is_zero()
342    }
343
344    /// What is the degree of the hiding polynomial for a given hiding bound?
345    #[inline]
346    pub fn calculate_hiding_polynomial_degree(hiding_bound: usize) -> usize {
347        hiding_bound + 1
348    }
349}
350
351impl<E: PairingEngine> KZGRandomness<E> {
352    pub fn empty() -> Self {
353        Self { blinding_polynomial: DensePolynomial::zero() }
354    }
355
356    pub fn rand<R: RngCore>(hiding_bound: usize, _: bool, rng: &mut R) -> Self {
357        let mut randomness = KZGRandomness::empty();
358        let hiding_poly_degree = Self::calculate_hiding_polynomial_degree(hiding_bound);
359        randomness.blinding_polynomial = DensePolynomial::rand(hiding_poly_degree, rng);
360        randomness
361    }
362}
363
364impl<'a, E: PairingEngine> Add<&'a KZGRandomness<E>> for KZGRandomness<E> {
365    type Output = Self;
366
367    #[inline]
368    fn add(mut self, other: &'a Self) -> Self {
369        self.blinding_polynomial += &other.blinding_polynomial;
370        self
371    }
372}
373
374impl<'a, E: PairingEngine> Add<(E::Fr, &'a KZGRandomness<E>)> for KZGRandomness<E> {
375    type Output = Self;
376
377    #[inline]
378    fn add(mut self, other: (E::Fr, &'a KZGRandomness<E>)) -> Self {
379        self += other;
380        self
381    }
382}
383
384impl<'a, E: PairingEngine> AddAssign<&'a KZGRandomness<E>> for KZGRandomness<E> {
385    #[inline]
386    fn add_assign(&mut self, other: &'a Self) {
387        self.blinding_polynomial += &other.blinding_polynomial;
388    }
389}
390
391impl<'a, E: PairingEngine> AddAssign<(E::Fr, &'a KZGRandomness<E>)> for KZGRandomness<E> {
392    #[inline]
393    fn add_assign(&mut self, (f, other): (E::Fr, &'a KZGRandomness<E>)) {
394        self.blinding_polynomial += (f, &other.blinding_polynomial);
395    }
396}
397
398/// `KZGProof` is an evaluation proof that is output by `KZG10::open`.
399#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, Hash, CanonicalSerialize, CanonicalDeserialize)]
400pub struct KZGProof<E: PairingEngine> {
401    /// This is a commitment to the witness polynomial; see [\[KZG10\]][kzg] for
402    /// more details.
403    ///
404    /// [kzg]: http://cacr.uwaterloo.ca/techreports/2010/cacr2010-10.pdf
405    pub w: E::G1Affine,
406    /// This is the evaluation of the random polynomial at the point for which
407    /// the evaluation proof was produced.
408    pub random_v: Option<E::Fr>,
409}
410
411impl<E: PairingEngine> KZGProof<E> {
412    pub fn absorb_into_sponge(&self, sponge: &mut impl AlgebraicSponge<E::Fq, 2>) {
413        sponge.absorb_native_field_elements(&self.w.to_field_elements().unwrap());
414        if let Some(random_v) = self.random_v {
415            sponge.absorb_nonnative_field_elements([random_v]);
416        }
417    }
418}
419
420impl<E: PairingEngine> FromBytes for KZGProof<E> {
421    fn read_le<R: Read>(mut reader: R) -> io::Result<Self> {
422        CanonicalDeserialize::deserialize_compressed(&mut reader).map_err(|_| error("could not deserialize KZG proof"))
423    }
424}
425
426impl<E: PairingEngine> ToBytes for KZGProof<E> {
427    fn write_le<W: Write>(&self, mut writer: W) -> io::Result<()> {
428        CanonicalSerialize::serialize_compressed(self, &mut writer).map_err(|_| error("could not serialize KZG proof"))
429    }
430}
431
432impl<E: PairingEngine> KZGProof<E> {
433    pub fn is_hiding(&self) -> bool {
434        self.random_v.is_some()
435    }
436}
snarkvm_algorithms/polycommit/kzg10/data_structures.rs

snarkvm_algorithms/polycommit/kzg10/
data_structures.rs
