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

snarkvm_algorithms/polycommit/sonic_pc/
data_structures.rs
