snarkvm_algorithms/polycommit/kzg10/
data_structures.rs

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

snarkvm_algorithms/polycommit/kzg10/
data_structures.rs
