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