snarkvm_algorithms/polycommit/kzg10/
data_structures.rs

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

snarkvm_algorithms/polycommit/kzg10/
data_structures.rs
