snarkvm_algorithms/polycommit/kzg10/
data_structures.rs

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

snarkvm_algorithms/polycommit/kzg10/
data_structures.rs
