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  //! A sparse polynomial represented in coefficient form.
 20  
 21  use crate::fft::{EvaluationDomain, Evaluations, Polynomial};
 22  use alphavm_fields::{Field, PrimeField};
 23  use alphavm_utilities::serialize::*;
 24  
 25  use std::{collections::BTreeMap, fmt};
 26  
 27  /// Stores a sparse polynomial in coefficient form.
 28  #[derive(Clone, PartialEq, Eq, Hash, Default, CanonicalSerialize, CanonicalDeserialize)]
 29  #[must_use]
 30  pub struct SparsePolynomial<F: Field> {
 31      /// The coefficient a_i of `x^i` is stored as (i, a_i) in `self.coeffs`.
 32      /// the entries in `self.coeffs` are sorted in increasing order of `i`.
 33      coeffs: BTreeMap<usize, F>,
 34  }
 35  
 36  impl<F: Field> fmt::Debug for SparsePolynomial<F> {
 37      fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
 38          for (i, coeff) in self.coeffs.iter().filter(|(_, c)| !c.is_zero()) {
 39              if *i == 0 {
 40                  write!(f, "\n{coeff:?}")?;
 41              } else if *i == 1 {
 42                  write!(f, " + \n{coeff:?} * x")?;
 43              } else {
 44                  write!(f, " + \n{coeff:?} * x^{i}")?;
 45              }
 46          }
 47          Ok(())
 48      }
 49  }
 50  
 51  impl<F: Field> SparsePolynomial<F> {
 52      /// Returns the zero polynomial.
 53      pub fn zero() -> Self {
 54          Self { coeffs: BTreeMap::new() }
 55      }
 56  
 57      /// Checks if the given polynomial is zero.
 58      pub fn is_zero(&self) -> bool {
 59          self.coeffs.is_empty() || self.coeffs.iter().all(|(_, c)| c.is_zero())
 60      }
 61  
 62      /// Constructs a new polynomial from a list of coefficients.
 63      pub fn from_coefficients_slice(coeffs: &[(usize, F)]) -> Self {
 64          Self::from_coefficients(coeffs.iter().copied())
 65      }
 66  
 67      /// Constructs a new polynomial from a list of coefficients.
 68      pub fn from_coefficients(coeffs: impl IntoIterator<Item = (usize, F)>) -> Self {
 69          let coeffs: BTreeMap<_, _> = coeffs.into_iter().filter(|(_, c)| !c.is_zero()).collect();
 70          Self { coeffs }
 71      }
 72  
 73      pub fn coeffs(&self) -> impl Iterator<Item = (&usize, &F)> {
 74          self.coeffs.iter()
 75      }
 76  
 77      /// Returns the degree of the polynomial.
 78      pub fn degree(&self) -> usize {
 79          if self.is_zero() {
 80              0
 81          } else {
 82              let last = self.coeffs.iter().max();
 83              assert!(last.is_some_and(|(_, c)| !c.is_zero()));
 84              *last.unwrap().0
 85          }
 86      }
 87  
 88      /// Evaluates `self` at the given `point` in the field.
 89      pub fn evaluate(&self, point: F) -> F {
 90          if self.is_zero() {
 91              return F::zero();
 92          }
 93          let mut total = F::zero();
 94          for (i, c) in &self.coeffs {
 95              total += *c * point.pow([*i as u64]);
 96          }
 97          total
 98      }
 99  
100      /// Perform a naive n^2 multiplication of `self` by `other`.
101      pub fn mul(&self, other: &Self) -> Self {
102          if self.is_zero() || other.is_zero() {
103              SparsePolynomial::zero()
104          } else {
105              let mut result = std::collections::BTreeMap::new();
106              for (i, self_coeff) in self.coeffs.iter() {
107                  for (j, other_coeff) in other.coeffs.iter() {
108                      let cur_coeff = result.entry(i + j).or_insert_with(F::zero);
109                      *cur_coeff += *self_coeff * other_coeff;
110                  }
111              }
112              SparsePolynomial::from_coefficients(result)
113          }
114      }
115  }
116  
117  impl<F: PrimeField> SparsePolynomial<F> {
118      /// Evaluate `self` over `domain`.
119      pub fn evaluate_over_domain_by_ref(&self, domain: EvaluationDomain<F>) -> Evaluations<F> {
120          let poly: Polynomial<'_, F> = self.into();
121          Polynomial::<F>::evaluate_over_domain(poly, domain)
122          // unimplemented!("current implementation does not produce evals in
123          // correct order")
124      }
125  
126      /// Evaluate `self` over `domain`.
127      pub fn evaluate_over_domain(self, domain: EvaluationDomain<F>) -> Evaluations<F> {
128          let poly: Polynomial<'_, F> = self.into();
129          Polynomial::<F>::evaluate_over_domain(poly, domain)
130          // unimplemented!("current implementation does not produce evals in
131          // correct order")
132      }
133  }
134  impl<F: PrimeField> core::ops::MulAssign<F> for SparsePolynomial<F> {
135      fn mul_assign(&mut self, other: F) {
136          if other.is_zero() {
137              *self = Self::zero()
138          } else {
139              for coeff in self.coeffs.values_mut() {
140                  *coeff *= other;
141              }
142          }
143      }
144  }
145  
146  impl<F: PrimeField> core::ops::Mul<F> for &'_ SparsePolynomial<F> {
147      type Output = SparsePolynomial<F>;
148  
149      fn mul(self, other: F) -> Self::Output {
150          let mut result = self.clone();
151          result *= other;
152          result
153      }
154  }
155  
156  impl<'a, F: PrimeField> core::ops::AddAssign<&'a Self> for SparsePolynomial<F> {
157      fn add_assign(&mut self, other: &'a Self) {
158          let mut result = other.clone();
159          for (i, coeff) in self.coeffs.iter() {
160              let cur_coeff = result.coeffs.entry(*i).or_insert_with(F::zero);
161              *cur_coeff += coeff;
162          }
163          *self = Self::from_coefficients(result.coeffs.into_iter().filter(|(_, f)| !f.is_zero()));
164      }
165  }
166  
167  impl<'a, F: PrimeField> core::ops::AddAssign<(F, &'a Self)> for SparsePolynomial<F> {
168      fn add_assign(&mut self, (f, other): (F, &'a Self)) {
169          let mut result = other.clone();
170          for (i, coeff) in self.coeffs.iter() {
171              let cur_coeff = result.coeffs.entry(*i).or_insert_with(F::zero);
172              *cur_coeff += f * coeff;
173          }
174          *self = Self::from_coefficients(result.coeffs.into_iter().filter(|(_, f)| !f.is_zero()))
175      }
176  }
177  
178  #[cfg(test)]
179  mod tests {
180      use crate::fft::{DensePolynomial, EvaluationDomain, SparsePolynomial};
181      use alphavm_curves::bls12_377::Fr;
182      use alphavm_fields::One;
183  
184      #[test]
185      fn evaluate_over_domain() {
186          for size in 2..10 {
187              let domain_size = 1 << size;
188              let domain = EvaluationDomain::new(domain_size).unwrap();
189              let two = Fr::one() + Fr::one();
190              let sparse_poly = SparsePolynomial::from_coefficients(vec![(0, two), (1, two)]);
191              let evals1 = sparse_poly.evaluate_over_domain_by_ref(domain);
192  
193              let dense_poly: DensePolynomial<Fr> = sparse_poly.into();
194              let evals2 = dense_poly.clone().evaluate_over_domain(domain);
195              assert_eq!(evals1.clone().interpolate(), evals2.clone().interpolate());
196              assert_eq!(evals1.interpolate(), dense_poly);
197              assert_eq!(evals2.interpolate(), dense_poly);
198          }
199      }
200  }