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

snarkvm_algorithms/polycommit/sonic_pc/
data_structures.rs
