snarkvm_algorithms/polycommit/sonic_pc/
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 super::{LabeledPolynomial, PolynomialInfo};
17use crate::{crypto_hash::sha256::sha256, fft::EvaluationDomain, polycommit::kzg10};
18use snarkvm_curves::PairingEngine;
19use snarkvm_fields::{ConstraintFieldError, Field, PrimeField, ToConstraintField};
20use snarkvm_utilities::{FromBytes, ToBytes, error, serialize::*};
21
22use hashbrown::HashMap;
23use std::{
24    borrow::{Borrow, Cow},
25    collections::{BTreeMap, BTreeSet},
26    fmt,
27    ops::{AddAssign, MulAssign, SubAssign},
28};
29
30/// `UniversalParams` are the universal parameters for the KZG10 scheme.
31pub type UniversalParams<E> = kzg10::UniversalParams<E>;
32
33/// `Randomness` is the randomness for the KZG10 scheme.
34pub type Randomness<E> = kzg10::KZGRandomness<E>;
35
36/// `Commitment` is the commitment for the KZG10 scheme.
37pub type Commitment<E> = kzg10::KZGCommitment<E>;
38
39/// `CommitterKey` is used to commit to, and create evaluation proofs for, a
40/// given polynomial.
41#[derive(Debug)]
42pub struct CommitterKey<E: PairingEngine> {
43    /// The key used to commit to polynomials.
44    pub powers_of_beta_g: Vec<E::G1Affine>,
45
46    /// The key used to commit to polynomials in Lagrange basis.
47    pub lagrange_bases_at_beta_g: BTreeMap<usize, Vec<E::G1Affine>>,
48
49    /// The key used to commit to hiding polynomials.
50    pub powers_of_beta_times_gamma_g: Vec<E::G1Affine>,
51
52    /// The powers used to commit to shifted polynomials.
53    /// This is `None` if `self` does not support enforcing any degree bounds.
54    pub shifted_powers_of_beta_g: Option<Vec<E::G1Affine>>,
55
56    /// The powers used to commit to shifted hiding polynomials.
57    /// This is `None` if `self` does not support enforcing any degree bounds.
58    pub shifted_powers_of_beta_times_gamma_g: Option<BTreeMap<usize, Vec<E::G1Affine>>>,
59
60    /// The degree bounds that are supported by `self`.
61    /// Sorted in ascending order from smallest bound to largest bound.
62    /// This is `None` if `self` does not support enforcing any degree bounds.
63    pub enforced_degree_bounds: Option<Vec<usize>>,
64}
65
66impl<E: PairingEngine> FromBytes for CommitterKey<E> {
67    fn read_le<R: Read>(mut reader: R) -> io::Result<Self> {
68        // Deserialize `powers`.
69        let powers_len: u32 = FromBytes::read_le(&mut reader)?;
70        let mut powers_of_beta_g = Vec::with_capacity(powers_len as usize);
71        for _ in 0..powers_len {
72            let power: E::G1Affine = FromBytes::read_le(&mut reader)?;
73            powers_of_beta_g.push(power);
74        }
75
76        // Deserialize `lagrange_basis_at_beta`.
77        let lagrange_bases_at_beta_len: u32 = FromBytes::read_le(&mut reader)?;
78        let mut lagrange_bases_at_beta_g = BTreeMap::new();
79        for _ in 0..lagrange_bases_at_beta_len {
80            let size: u32 = FromBytes::read_le(&mut reader)?;
81            let mut basis = Vec::with_capacity(size as usize);
82            for _ in 0..size {
83                let power: E::G1Affine = FromBytes::read_le(&mut reader)?;
84                basis.push(power);
85            }
86            lagrange_bases_at_beta_g.insert(size as usize, basis);
87        }
88
89        // Deserialize `powers_of_beta_times_gamma_g`.
90        let powers_of_beta_times_gamma_g_len: u32 = FromBytes::read_le(&mut reader)?;
91        let mut powers_of_beta_times_gamma_g = Vec::with_capacity(powers_of_beta_times_gamma_g_len as usize);
92        for _ in 0..powers_of_beta_times_gamma_g_len {
93            let powers_of_g: E::G1Affine = FromBytes::read_le(&mut reader)?;
94            powers_of_beta_times_gamma_g.push(powers_of_g);
95        }
96
97        // Deserialize `shifted_powers_of_beta_g`.
98        let has_shifted_powers_of_beta_g: bool = FromBytes::read_le(&mut reader)?;
99        let shifted_powers_of_beta_g = match has_shifted_powers_of_beta_g {
100            true => {
101                let shifted_powers_len: u32 = FromBytes::read_le(&mut reader)?;
102                let mut shifted_powers_of_beta_g = Vec::with_capacity(shifted_powers_len as usize);
103                for _ in 0..shifted_powers_len {
104                    let shifted_power: E::G1Affine = FromBytes::read_le(&mut reader)?;
105                    shifted_powers_of_beta_g.push(shifted_power);
106                }
107
108                Some(shifted_powers_of_beta_g)
109            }
110            false => None,
111        };
112
113        // Deserialize `shifted_powers_of_beta_times_gamma_g`.
114        let has_shifted_powers_of_beta_times_gamma_g: bool = FromBytes::read_le(&mut reader)?;
115        let shifted_powers_of_beta_times_gamma_g = match has_shifted_powers_of_beta_times_gamma_g {
116            true => {
117                let mut shifted_powers_of_beta_times_gamma_g = BTreeMap::new();
118                let shifted_powers_of_beta_times_gamma_g_num_elements: u32 = FromBytes::read_le(&mut reader)?;
119                for _ in 0..shifted_powers_of_beta_times_gamma_g_num_elements {
120                    let key: u32 = FromBytes::read_le(&mut reader)?;
121
122                    let value_len: u32 = FromBytes::read_le(&mut reader)?;
123                    let mut value = Vec::with_capacity(value_len as usize);
124                    for _ in 0..value_len {
125                        let val: E::G1Affine = FromBytes::read_le(&mut reader)?;
126                        value.push(val);
127                    }
128
129                    shifted_powers_of_beta_times_gamma_g.insert(key as usize, value);
130                }
131
132                Some(shifted_powers_of_beta_times_gamma_g)
133            }
134            false => None,
135        };
136
137        // Deserialize `enforced_degree_bounds`.
138        let has_enforced_degree_bounds: bool = FromBytes::read_le(&mut reader)?;
139        let enforced_degree_bounds = match has_enforced_degree_bounds {
140            true => {
141                let enforced_degree_bounds_len: u32 = FromBytes::read_le(&mut reader)?;
142                let mut enforced_degree_bounds = Vec::with_capacity(enforced_degree_bounds_len as usize);
143                for _ in 0..enforced_degree_bounds_len {
144                    let enforced_degree_bound: u32 = FromBytes::read_le(&mut reader)?;
145                    enforced_degree_bounds.push(enforced_degree_bound as usize);
146                }
147
148                Some(enforced_degree_bounds)
149            }
150            false => None,
151        };
152
153        // Construct the hash of the group elements.
154        let mut hash_input = powers_of_beta_g.to_bytes_le().map_err(|_| error("Could not serialize powers"))?;
155        powers_of_beta_times_gamma_g
156            .write_le(&mut hash_input)
157            .map_err(|_| error("Could not serialize powers_of_beta_times_gamma_g"))?;
158
159        if let Some(shifted_powers_of_beta_g) = &shifted_powers_of_beta_g {
160            shifted_powers_of_beta_g
161                .write_le(&mut hash_input)
162                .map_err(|_| error("Could not serialize shifted_powers_of_beta_g"))?;
163        }
164
165        if let Some(shifted_powers_of_beta_times_gamma_g) = &shifted_powers_of_beta_times_gamma_g {
166            for value in shifted_powers_of_beta_times_gamma_g.values() {
167                value.write_le(&mut hash_input).map_err(|_| error("Could not serialize shifted_power_of_gamma_g"))?;
168            }
169        }
170
171        // Deserialize `hash`.
172        let hash = sha256(&hash_input);
173        let expected_hash: [u8; 32] = FromBytes::read_le(&mut reader)?;
174
175        // Enforce the group elements construct the expected hash.
176        if expected_hash != hash {
177            return Err(error("Mismatching group elements"));
178        }
179
180        Ok(Self {
181            powers_of_beta_g,
182            lagrange_bases_at_beta_g,
183            powers_of_beta_times_gamma_g,
184            shifted_powers_of_beta_g,
185            shifted_powers_of_beta_times_gamma_g,
186            enforced_degree_bounds,
187        })
188    }
189}
190
191impl<E: PairingEngine> ToBytes for CommitterKey<E> {
192    fn write_le<W: Write>(&self, mut writer: W) -> io::Result<()> {
193        // Serialize `powers`.
194        (self.powers_of_beta_g.len() as u32).write_le(&mut writer)?;
195        for power in &self.powers_of_beta_g {
196            power.write_le(&mut writer)?;
197        }
198
199        // Serialize `powers`.
200        (self.lagrange_bases_at_beta_g.len() as u32).write_le(&mut writer)?;
201        for (size, powers) in &self.lagrange_bases_at_beta_g {
202            (*size as u32).write_le(&mut writer)?;
203            for power in powers {
204                power.write_le(&mut writer)?;
205            }
206        }
207
208        // Serialize `powers_of_beta_times_gamma_g`.
209        (self.powers_of_beta_times_gamma_g.len() as u32).write_le(&mut writer)?;
210        for power_of_gamma_g in &self.powers_of_beta_times_gamma_g {
211            power_of_gamma_g.write_le(&mut writer)?;
212        }
213
214        // Serialize `shifted_powers_of_beta_g`.
215        self.shifted_powers_of_beta_g.is_some().write_le(&mut writer)?;
216        if let Some(shifted_powers_of_beta_g) = &self.shifted_powers_of_beta_g {
217            (shifted_powers_of_beta_g.len() as u32).write_le(&mut writer)?;
218            for shifted_power in shifted_powers_of_beta_g {
219                shifted_power.write_le(&mut writer)?;
220            }
221        }
222
223        // Serialize `shifted_powers_of_beta_times_gamma_g`.
224        self.shifted_powers_of_beta_times_gamma_g.is_some().write_le(&mut writer)?;
225        if let Some(shifted_powers_of_beta_times_gamma_g) = &self.shifted_powers_of_beta_times_gamma_g {
226            (shifted_powers_of_beta_times_gamma_g.len() as u32).write_le(&mut writer)?;
227            for (key, shifted_powers_of_beta_g) in shifted_powers_of_beta_times_gamma_g {
228                (*key as u32).write_le(&mut writer)?;
229                (shifted_powers_of_beta_g.len() as u32).write_le(&mut writer)?;
230                for shifted_power in shifted_powers_of_beta_g {
231                    shifted_power.write_le(&mut writer)?;
232                }
233            }
234        }
235
236        // Serialize `enforced_degree_bounds`.
237        self.enforced_degree_bounds.is_some().write_le(&mut writer)?;
238        if let Some(enforced_degree_bounds) = &self.enforced_degree_bounds {
239            (enforced_degree_bounds.len() as u32).write_le(&mut writer)?;
240            for enforced_degree_bound in enforced_degree_bounds {
241                (*enforced_degree_bound as u32).write_le(&mut writer)?;
242            }
243        }
244
245        // Construct the hash of the group elements.
246        let mut hash_input = self.powers_of_beta_g.to_bytes_le().map_err(|_| error("Could not serialize powers"))?;
247        self.powers_of_beta_times_gamma_g
248            .write_le(&mut hash_input)
249            .map_err(|_| error("Could not serialize powers_of_beta_times_gamma_g"))?;
250
251        if let Some(shifted_powers_of_beta_g) = &self.shifted_powers_of_beta_g {
252            shifted_powers_of_beta_g
253                .write_le(&mut hash_input)
254                .map_err(|_| error("Could not serialize shifted_powers_of_beta_g"))?;
255        }
256
257        if let Some(shifted_powers_of_beta_times_gamma_g) = &self.shifted_powers_of_beta_times_gamma_g {
258            for value in shifted_powers_of_beta_times_gamma_g.values() {
259                value.write_le(&mut hash_input).map_err(|_| error("Could not serialize shifted_power_of_gamma_g"))?;
260            }
261        }
262
263        // Serialize `hash`
264        let hash = sha256(&hash_input);
265        hash.write_le(&mut writer)
266    }
267}
268
269impl<E: PairingEngine> CommitterKey<E> {
270    fn len(&self) -> usize {
271        if self.shifted_powers_of_beta_g.is_some() { self.shifted_powers_of_beta_g.as_ref().unwrap().len() } else { 0 }
272    }
273}
274
275/// `CommitterUnionKey` is a union of `CommitterKey`s, useful for multi-circuit
276/// batch proofs.
277#[derive(Debug)]
278pub struct CommitterUnionKey<'a, E: PairingEngine> {
279    /// The key used to commit to polynomials.
280    pub powers_of_beta_g: Option<&'a Vec<E::G1Affine>>,
281
282    /// The key used to commit to polynomials in Lagrange basis.
283    pub lagrange_bases_at_beta_g: BTreeMap<usize, &'a Vec<E::G1Affine>>,
284
285    /// The key used to commit to hiding polynomials.
286    pub powers_of_beta_times_gamma_g: Option<&'a Vec<E::G1Affine>>,
287
288    /// The powers used to commit to shifted polynomials.
289    /// This is `None` if `self` does not support enforcing any degree bounds.
290    pub shifted_powers_of_beta_g: Option<&'a Vec<E::G1Affine>>,
291
292    /// The powers used to commit to shifted hiding polynomials.
293    /// This is `None` if `self` does not support enforcing any degree bounds.
294    pub shifted_powers_of_beta_times_gamma_g: Option<BTreeMap<usize, &'a Vec<E::G1Affine>>>,
295
296    /// The degree bounds that are supported by `self`.
297    /// Sorted in ascending order from smallest bound to largest bound.
298    /// This is `None` if `self` does not support enforcing any degree bounds.
299    pub enforced_degree_bounds: Option<Vec<usize>>,
300}
301
302impl<'a, E: PairingEngine> CommitterUnionKey<'a, E> {
303    /// Obtain powers for the underlying KZG10 construction
304    pub fn powers(&self) -> kzg10::Powers<E> {
305        kzg10::Powers {
306            powers_of_beta_g: self.powers_of_beta_g.unwrap().as_slice().into(),
307            powers_of_beta_times_gamma_g: self.powers_of_beta_times_gamma_g.unwrap().as_slice().into(),
308        }
309    }
310
311    /// Obtain powers for committing to shifted polynomials.
312    pub fn shifted_powers_of_beta_g(&self, degree_bound: impl Into<Option<usize>>) -> Option<kzg10::Powers<E>> {
313        match (&self.shifted_powers_of_beta_g, &self.shifted_powers_of_beta_times_gamma_g) {
314            (Some(shifted_powers_of_beta_g), Some(shifted_powers_of_beta_times_gamma_g)) => {
315                let max_bound = self.enforced_degree_bounds.as_ref().unwrap().last().unwrap();
316                let (bound, powers_range) = if let Some(degree_bound) = degree_bound.into() {
317                    assert!(self.enforced_degree_bounds.as_ref().unwrap().contains(&degree_bound));
318                    (degree_bound, (max_bound - degree_bound)..)
319                } else {
320                    (*max_bound, 0..)
321                };
322
323                let ck = kzg10::Powers {
324                    powers_of_beta_g: shifted_powers_of_beta_g[powers_range].into(),
325                    powers_of_beta_times_gamma_g: shifted_powers_of_beta_times_gamma_g[&bound].clone().into(),
326                };
327
328                Some(ck)
329            }
330
331            (_, _) => None,
332        }
333    }
334
335    /// Obtain elements of the SRS in the lagrange basis powers, for use with
336    /// the underlying KZG10 construction.
337    pub fn lagrange_basis(&self, domain: EvaluationDomain<E::Fr>) -> Option<kzg10::LagrangeBasis<E>> {
338        self.lagrange_bases_at_beta_g.get(&domain.size()).map(|basis| kzg10::LagrangeBasis {
339            lagrange_basis_at_beta_g: Cow::Borrowed(basis),
340            powers_of_beta_times_gamma_g: Cow::Borrowed(self.powers_of_beta_times_gamma_g.unwrap()),
341            domain,
342        })
343    }
344
345    pub fn union<T: IntoIterator<Item = &'a CommitterKey<E>>>(committer_keys: T) -> Self {
346        let mut ck_union = CommitterUnionKey::<E> {
347            powers_of_beta_g: None,
348            lagrange_bases_at_beta_g: BTreeMap::new(),
349            powers_of_beta_times_gamma_g: None,
350            shifted_powers_of_beta_g: None,
351            shifted_powers_of_beta_times_gamma_g: None,
352            enforced_degree_bounds: None,
353        };
354        let mut enforced_degree_bounds = vec![];
355        let mut biggest_ck: Option<&CommitterKey<E>> = None;
356        let mut shifted_powers_of_beta_times_gamma_g = BTreeMap::new();
357        for ck in committer_keys {
358            if biggest_ck.is_none() || biggest_ck.unwrap().len() < ck.len() {
359                biggest_ck = Some(ck);
360            }
361            let lagrange_bases = &ck.lagrange_bases_at_beta_g;
362            for (bound_base, bases) in lagrange_bases.iter() {
363                ck_union.lagrange_bases_at_beta_g.entry(*bound_base).or_insert(bases);
364            }
365            if let Some(shifted_powers) = ck.shifted_powers_of_beta_times_gamma_g.as_ref() {
366                for (bound_power, powers) in shifted_powers.iter() {
367                    shifted_powers_of_beta_times_gamma_g.entry(*bound_power).or_insert(powers);
368                }
369            }
370            if let Some(degree_bounds) = &ck.enforced_degree_bounds {
371                enforced_degree_bounds.append(&mut degree_bounds.clone());
372            }
373        }
374
375        let biggest_ck = biggest_ck.unwrap();
376        ck_union.powers_of_beta_g = Some(&biggest_ck.powers_of_beta_g);
377        ck_union.powers_of_beta_times_gamma_g = Some(&biggest_ck.powers_of_beta_times_gamma_g);
378        ck_union.shifted_powers_of_beta_g = biggest_ck.shifted_powers_of_beta_g.as_ref();
379
380        if !enforced_degree_bounds.is_empty() {
381            enforced_degree_bounds.sort();
382            enforced_degree_bounds.dedup();
383            ck_union.enforced_degree_bounds = Some(enforced_degree_bounds);
384            ck_union.shifted_powers_of_beta_times_gamma_g = Some(shifted_powers_of_beta_times_gamma_g);
385        }
386
387        ck_union
388    }
389}
390
391/// Evaluation proof at a query set.
392#[derive(Clone, Debug, Default, PartialEq, Eq, Hash, CanonicalSerialize, CanonicalDeserialize)]
393pub struct BatchProof<E: PairingEngine>(pub(crate) Vec<kzg10::KZGProof<E>>);
394
395impl<E: PairingEngine> BatchProof<E> {
396    pub fn is_hiding(&self) -> bool {
397        self.0.iter().any(|c| c.is_hiding())
398    }
399}
400
401/// Labels a `LabeledPolynomial` or a `LabeledCommitment`.
402pub type PolynomialLabel = String;
403
404/// A commitment along with information about its degree bound (if any).
405#[derive(Clone, Debug, CanonicalSerialize, PartialEq, Eq)]
406pub struct LabeledCommitment<C: CanonicalSerialize + 'static> {
407    label: PolynomialLabel,
408    commitment: C,
409    degree_bound: Option<usize>,
410}
411
412impl<F: Field, C: CanonicalSerialize + ToConstraintField<F>> ToConstraintField<F> for LabeledCommitment<C> {
413    fn to_field_elements(&self) -> Result<Vec<F>, ConstraintFieldError> {
414        self.commitment.to_field_elements()
415    }
416}
417
418// NOTE: Serializing the LabeledCommitments struct is done by serializing
419// _WITHOUT_ the labels or the degree bound. Deserialization is _NOT_ supported,
420// and you should construct the struct via the `LabeledCommitment::new` method
421// after deserializing the Commitment.
422impl<C: CanonicalSerialize + ToBytes> ToBytes for LabeledCommitment<C> {
423    fn write_le<W: Write>(&self, mut writer: W) -> io::Result<()> {
424        CanonicalSerialize::serialize_compressed(&self.commitment, &mut writer)
425            .map_err(|_| error("could not serialize struct"))
426    }
427}
428
429impl<C: CanonicalSerialize> LabeledCommitment<C> {
430    /// Instantiate a new polynomial_context.
431    pub fn new(label: PolynomialLabel, commitment: C, degree_bound: Option<usize>) -> Self {
432        Self { label, commitment, degree_bound }
433    }
434
435    pub fn new_with_info(info: &PolynomialInfo, commitment: C) -> Self {
436        Self { label: info.label().to_string(), commitment, degree_bound: info.degree_bound() }
437    }
438
439    /// Return the label for `self`.
440    pub fn label(&self) -> &str {
441        &self.label
442    }
443
444    /// Retrieve the commitment from `self`.
445    pub fn commitment(&self) -> &C {
446        &self.commitment
447    }
448
449    /// Retrieve the degree bound in `self`.
450    pub fn degree_bound(&self) -> Option<usize> {
451        self.degree_bound
452    }
453}
454
455/// A term in a linear combination.
456#[derive(Hash, Ord, PartialOrd, Clone, Eq, PartialEq)]
457pub enum LCTerm {
458    /// The constant term representing `one`.
459    One,
460    /// Label for a polynomial.
461    PolyLabel(String),
462}
463
464impl fmt::Debug for LCTerm {
465    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
466        match self {
467            LCTerm::One => write!(f, "1"),
468            LCTerm::PolyLabel(label) => write!(f, "{label}"),
469        }
470    }
471}
472
473impl LCTerm {
474    /// Returns `true` if `self == LCTerm::One`
475    #[inline]
476    pub fn is_one(&self) -> bool {
477        matches!(self, LCTerm::One)
478    }
479}
480
481impl From<PolynomialLabel> for LCTerm {
482    fn from(other: PolynomialLabel) -> Self {
483        Self::PolyLabel(other)
484    }
485}
486
487impl From<&'_ str> for LCTerm {
488    fn from(other: &str) -> Self {
489        Self::PolyLabel(other.into())
490    }
491}
492
493impl core::convert::TryInto<PolynomialLabel> for LCTerm {
494    type Error = ();
495
496    fn try_into(self) -> Result<PolynomialLabel, ()> {
497        match self {
498            Self::One => Err(()),
499            Self::PolyLabel(l) => Ok(l),
500        }
501    }
502}
503
504impl<'a> core::convert::TryInto<&'a PolynomialLabel> for &'a LCTerm {
505    type Error = ();
506
507    fn try_into(self) -> Result<&'a PolynomialLabel, ()> {
508        match self {
509            LCTerm::One => Err(()),
510            LCTerm::PolyLabel(l) => Ok(l),
511        }
512    }
513}
514
515impl<B: Borrow<String>> PartialEq<B> for LCTerm {
516    fn eq(&self, other: &B) -> bool {
517        match self {
518            Self::One => false,
519            Self::PolyLabel(l) => l == other.borrow(),
520        }
521    }
522}
523
524/// A labeled linear combinations of polynomials.
525#[derive(Clone, Debug)]
526pub struct LinearCombination<F> {
527    /// The label.
528    pub label: String,
529    /// The linear combination of `(poly_label, coeff)` pairs.
530    pub terms: BTreeMap<LCTerm, F>,
531}
532
533#[allow(clippy::or_fun_call)]
534impl<F: Field> LinearCombination<F> {
535    /// Construct an empty labeled linear combination.
536    pub fn empty(label: impl Into<String>) -> Self {
537        Self { label: label.into(), terms: BTreeMap::new() }
538    }
539
540    /// Construct a new labeled linear combination.
541    /// with the terms specified in `term`.
542    pub fn new(label: impl Into<String>, _terms: impl IntoIterator<Item = (F, impl Into<LCTerm>)>) -> Self {
543        let mut terms = BTreeMap::new();
544        for (c, l) in _terms.into_iter().map(|(c, t)| (c, t.into())) {
545            *terms.entry(l).or_insert(F::zero()) += c;
546        }
547
548        Self { label: label.into(), terms }
549    }
550
551    /// Returns the label of the linear combination.
552    pub fn label(&self) -> &str {
553        &self.label
554    }
555
556    /// Returns `true` if the linear combination has no terms.
557    pub fn is_empty(&self) -> bool {
558        self.terms.is_empty()
559    }
560
561    /// Add a term to the linear combination.
562    pub fn add(&mut self, c: F, t: impl Into<LCTerm>) -> &mut Self {
563        let t = t.into();
564        *self.terms.entry(t.clone()).or_insert(F::zero()) += c;
565        if self.terms[&t].is_zero() {
566            self.terms.remove(&t);
567        }
568        self
569    }
570
571    pub fn len(&self) -> usize {
572        self.terms.len()
573    }
574
575    pub fn iter(&self) -> impl Iterator<Item = (&F, &LCTerm)> {
576        self.terms.iter().map(|(t, c)| (c, t))
577    }
578}
579
580impl<'a, F: Field> AddAssign<(F, &'a LinearCombination<F>)> for LinearCombination<F> {
581    #[allow(clippy::suspicious_op_assign_impl)]
582    fn add_assign(&mut self, (coeff, other): (F, &'a LinearCombination<F>)) {
583        for (t, c) in other.terms.iter() {
584            self.add(coeff * c, t.clone());
585        }
586    }
587}
588
589impl<'a, F: Field> SubAssign<(F, &'a LinearCombination<F>)> for LinearCombination<F> {
590    #[allow(clippy::suspicious_op_assign_impl)]
591    fn sub_assign(&mut self, (coeff, other): (F, &'a LinearCombination<F>)) {
592        for (t, c) in other.terms.iter() {
593            self.add(-coeff * c, t.clone());
594        }
595    }
596}
597
598impl<'a, F: Field> AddAssign<&'a LinearCombination<F>> for LinearCombination<F> {
599    fn add_assign(&mut self, other: &'a LinearCombination<F>) {
600        for (t, c) in other.terms.iter() {
601            self.add(*c, t.clone());
602        }
603    }
604}
605
606impl<'a, F: Field> SubAssign<&'a LinearCombination<F>> for LinearCombination<F> {
607    fn sub_assign(&mut self, other: &'a LinearCombination<F>) {
608        for (t, &c) in other.terms.iter() {
609            self.add(-c, t.clone());
610        }
611    }
612}
613
614impl<F: Field> AddAssign<F> for LinearCombination<F> {
615    fn add_assign(&mut self, coeff: F) {
616        self.add(coeff, LCTerm::One);
617    }
618}
619
620impl<F: Field> SubAssign<F> for LinearCombination<F> {
621    fn sub_assign(&mut self, coeff: F) {
622        self.add(-coeff, LCTerm::One);
623    }
624}
625
626impl<F: Field> MulAssign<F> for LinearCombination<F> {
627    fn mul_assign(&mut self, coeff: F) {
628        self.terms.values_mut().for_each(|c| *c *= &coeff);
629    }
630}
631
632/// `QuerySet` is the set of queries that are to be made to a set of labeled
633/// polynomials/equations `p` that have previously been committed to. Each
634/// element of a `QuerySet` is a `(label, query)` pair, where `label` is the
635/// label of a polynomial in `p`, and `query` is the field element
636/// that `p[label]` is to be queried at.
637///
638/// Added the third field: the point name.
639pub type QuerySet<T> = BTreeSet<(String, (String, T))>;
640
641/// `Evaluations` is the result of querying a set of labeled polynomials or
642/// equations `p` at a `QuerySet` `Q`. It maps each element of `Q` to the
643/// resulting evaluation. That is, if `(label, query)` is an element of `Q`,
644/// then `evaluation.get((label, query))` should equal
645/// `p[label].evaluate(query)`.
646pub type Evaluations<F> = BTreeMap<(String, F), F>;
647
648/// Evaluate the given polynomials at `query_set`.
649pub fn evaluate_query_set<'a, F: PrimeField>(
650    polys: impl IntoIterator<Item = &'a LabeledPolynomial<F>>,
651    query_set: &QuerySet<F>,
652) -> Evaluations<F> {
653    let polys: HashMap<_, _> = polys.into_iter().map(|p| (p.label(), p)).collect();
654    let mut evaluations = Evaluations::new();
655    for (label, (_point_name, point)) in query_set {
656        let poly = polys.get(label as &str).expect("polynomial in evaluated lc is not found");
657        let eval = poly.evaluate(*point);
658        evaluations.insert((label.clone(), *point), eval);
659    }
660    evaluations
661}
662
663/// A proof of satisfaction of linear combinations.
664#[derive(Clone, Debug, PartialEq, Eq, CanonicalSerialize, CanonicalDeserialize)]
665pub struct BatchLCProof<E: PairingEngine> {
666    /// Evaluation proof.
667    pub proof: BatchProof<E>,
668}
669
670impl<E: PairingEngine> BatchLCProof<E> {
671    pub fn is_hiding(&self) -> bool {
672        self.proof.is_hiding()
673    }
674}
675
676impl<E: PairingEngine> FromBytes for BatchLCProof<E> {
677    fn read_le<R: Read>(mut reader: R) -> io::Result<Self> {
678        CanonicalDeserialize::deserialize_compressed(&mut reader).map_err(|_| error("could not deserialize struct"))
679    }
680}
681
682impl<E: PairingEngine> ToBytes for BatchLCProof<E> {
683    fn write_le<W: Write>(&self, mut writer: W) -> io::Result<()> {
684        CanonicalSerialize::serialize_compressed(self, &mut writer).map_err(|_| error("could not serialize struct"))
685    }
686}
snarkvm_algorithms/polycommit/sonic_pc/data_structures.rs

snarkvm_algorithms/polycommit/sonic_pc/
data_structures.rs
