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

snarkvm_algorithms/polycommit/sonic_pc/
data_structures.rs
