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::PolynomialLabel;
 20  use crate::fft::{DensePolynomial, EvaluationDomain, Evaluations as EvaluationsOnDomain, Polynomial, SparsePolynomial};
 21  use alphavm_fields::{Field, PrimeField};
 22  use alphavm_utilities::{cfg_iter, cfg_iter_mut, CanonicalDeserialize, CanonicalSerialize};
 23  
 24  use anyhow::Result;
 25  use std::borrow::Cow;
 26  
 27  #[cfg(feature = "serial")]
 28  use itertools::Itertools;
 29  #[cfg(not(feature = "serial"))]
 30  use rayon::prelude::*;
 31  
 32  #[derive(Clone, Debug, CanonicalSerialize, CanonicalDeserialize, Eq, PartialEq)]
 33  pub struct PolynomialInfo {
 34      label: PolynomialLabel,
 35      degree_bound: Option<usize>,
 36      hiding_bound: Option<usize>,
 37  }
 38  
 39  impl PolynomialInfo {
 40      /// Construct a new labeled polynomial by consuming `polynomial`.
 41      pub fn new(label: PolynomialLabel, degree_bound: Option<usize>, hiding_bound: Option<usize>) -> Self {
 42          Self { label, degree_bound, hiding_bound }
 43      }
 44  
 45      /// Return the label for `self`.
 46      pub fn label(&self) -> &str {
 47          &self.label
 48      }
 49  
 50      /// Retrieve the degree bound in `self`.
 51      pub fn degree_bound(&self) -> Option<usize> {
 52          self.degree_bound
 53      }
 54  
 55      /// Retrieve whether the polynomial in `self` should be hidden.
 56      pub fn is_hiding(&self) -> bool {
 57          self.hiding_bound.is_some()
 58      }
 59  
 60      /// Retrieve the hiding bound for the polynomial in `self`.
 61      pub fn hiding_bound(&self) -> Option<usize> {
 62          self.hiding_bound
 63      }
 64  }
 65  
 66  /// A polynomial along with information about its degree bound (if any), and the
 67  /// maximum number of queries that will be made to it. This latter number
 68  /// determines the amount of protection that will be provided to a commitment
 69  /// for this polynomial.
 70  #[derive(Debug, Clone, CanonicalSerialize, CanonicalDeserialize, PartialEq, Eq)]
 71  pub struct LabeledPolynomial<F: Field> {
 72      pub info: PolynomialInfo,
 73      pub polynomial: Polynomial<'static, F>,
 74  }
 75  
 76  impl<F: Field> core::ops::Deref for LabeledPolynomial<F> {
 77      type Target = Polynomial<'static, F>;
 78  
 79      fn deref(&self) -> &Self::Target {
 80          &self.polynomial
 81      }
 82  }
 83  
 84  impl<F: Field> LabeledPolynomial<F> {
 85      /// Construct a new labeled polynomial by consuming `polynomial`.
 86      pub fn new(
 87          label: impl Into<PolynomialLabel>,
 88          polynomial: impl Into<Polynomial<'static, F>>,
 89          degree_bound: impl Into<Option<usize>>,
 90          hiding_bound: impl Into<Option<usize>>,
 91      ) -> Self {
 92          let info = PolynomialInfo::new(label.into(), degree_bound.into(), hiding_bound.into());
 93          Self { info, polynomial: polynomial.into() }
 94      }
 95  
 96      pub fn info(&self) -> &PolynomialInfo {
 97          &self.info
 98      }
 99  
100      /// Return the label for `self`.
101      pub fn label(&self) -> &str {
102          &self.info.label
103      }
104  
105      /// Return the label for `self`.
106      pub fn to_label(&self) -> String {
107          self.info.label.clone()
108      }
109  
110      /// Retrieve the polynomial from `self`.
111      pub fn polynomial(&self) -> &Polynomial<'_, F> {
112          &self.polynomial
113      }
114  
115      /// Retrieve a mutable reference to the enclosed polynomial.
116      pub fn polynomial_mut(&mut self) -> &mut Polynomial<'static, F> {
117          &mut self.polynomial
118      }
119  
120      /// Evaluate the polynomial in `self`.
121      pub fn evaluate(&self, point: F) -> F {
122          self.polynomial.evaluate(point)
123      }
124  
125      /// Retrieve the degree bound in `self`.
126      pub fn degree_bound(&self) -> Option<usize> {
127          self.info.degree_bound
128      }
129  
130      /// Retrieve whether the polynomial in `self` should be hidden.
131      pub fn is_hiding(&self) -> bool {
132          self.info.hiding_bound.is_some()
133      }
134  
135      /// Retrieve the hiding bound for the polynomial in `self`.
136      pub fn hiding_bound(&self) -> Option<usize> {
137          self.info.hiding_bound
138      }
139  }
140  
141  /////////////////////////////////////////////////////////////////////////////////////
142  
143  #[derive(Debug, Clone)]
144  pub struct LabeledPolynomialWithBasis<'a, F: PrimeField> {
145      pub info: PolynomialInfo,
146      pub polynomial: PolynomialWithBasis<'a, F>,
147  }
148  
149  impl<'a, F: PrimeField> LabeledPolynomialWithBasis<'a, F> {
150      /// Construct a new labeled polynomial by consuming `polynomial`.
151      pub fn new_monomial_basis(
152          label: PolynomialLabel,
153          polynomial: &'a Polynomial<F>,
154          degree_bound: Option<usize>,
155          hiding_bound: Option<usize>,
156      ) -> Self {
157          let polynomial = PolynomialWithBasis::new_monomial_basis_ref(polynomial, degree_bound);
158          let info = PolynomialInfo::new(label, degree_bound, hiding_bound);
159          Self { info, polynomial }
160      }
161  
162      pub fn new_lagrange_basis(
163          label: PolynomialLabel,
164          polynomial: EvaluationsOnDomain<F>,
165          hiding_bound: Option<usize>,
166      ) -> Self {
167          let polynomial = PolynomialWithBasis::new_lagrange_basis(polynomial);
168          let info = PolynomialInfo::new(label, None, hiding_bound);
169          Self { info, polynomial }
170      }
171  
172      pub fn new_lagrange_basis_ref(
173          label: PolynomialLabel,
174          polynomial: &'a EvaluationsOnDomain<F>,
175          hiding_bound: Option<usize>,
176      ) -> Self {
177          let polynomial = PolynomialWithBasis::new_lagrange_basis_ref(polynomial);
178          let info = PolynomialInfo::new(label, None, hiding_bound);
179          Self { info, polynomial }
180      }
181  
182      /// Return the label for `self`.
183      pub fn label(&self) -> &str {
184          &self.info.label
185      }
186  
187      /// Return the information about the label, degree bound, and hiding bound
188      /// of `self`.
189      pub fn info(&self) -> &PolynomialInfo {
190          &self.info
191      }
192  
193      pub fn degree(&self) -> usize {
194          match &self.polynomial {
195              PolynomialWithBasis::Lagrange { evaluations } => evaluations.domain().size() - 1,
196              PolynomialWithBasis::Monomial { polynomial, .. } => polynomial.degree(),
197          }
198      }
199  
200      /// Evaluate the polynomial in `self`.
201      pub fn evaluate(&self, point: F) -> F {
202          self.polynomial.evaluate(point)
203      }
204  
205      /// Retrieve the degree bound in `self`.
206      pub fn degree_bound(&self) -> Option<usize> {
207          match self.polynomial {
208              PolynomialWithBasis::Monomial { degree_bound, .. } => degree_bound,
209              _ => None,
210          }
211      }
212  
213      /// Retrieve whether the polynomial in `self` should be hidden.
214      pub fn is_hiding(&self) -> bool {
215          self.info.hiding_bound.is_some()
216      }
217  
218      /// Retrieve the hiding bound for the polynomial in `self`.
219      pub fn hiding_bound(&self) -> Option<usize> {
220          self.info.hiding_bound
221      }
222  }
223  
224  impl<'a, F: PrimeField> From<&'a LabeledPolynomial<F>> for LabeledPolynomialWithBasis<'a, F> {
225      fn from(other: &'a LabeledPolynomial<F>) -> Self {
226          let polynomial = PolynomialWithBasis::Monomial {
227              polynomial: Cow::Borrowed(other.polynomial()),
228              degree_bound: other.degree_bound(),
229          };
230          Self { info: other.info.clone(), polynomial }
231      }
232  }
233  
234  impl<F: PrimeField> From<LabeledPolynomial<F>> for LabeledPolynomialWithBasis<'_, F> {
235      fn from(other: LabeledPolynomial<F>) -> Self {
236          let polynomial = PolynomialWithBasis::Monomial {
237              polynomial: Cow::Owned(other.polynomial),
238              degree_bound: other.info.degree_bound,
239          };
240          Self { info: other.info.clone(), polynomial }
241      }
242  }
243  
244  #[derive(Debug, Clone)]
245  pub enum PolynomialWithBasis<'a, F: PrimeField> {
246      /// A polynomial in monomial basis, along with information about
247      /// its degree bound (if any).
248      Monomial { polynomial: Cow<'a, Polynomial<'a, F>>, degree_bound: Option<usize> },
249  
250      /// A polynomial in Lagrange basis, along with information about
251      /// its degree bound (if any).
252      Lagrange { evaluations: Cow<'a, EvaluationsOnDomain<F>> },
253  }
254  
255  impl<'a, F: PrimeField> PolynomialWithBasis<'a, F> {
256      pub fn new_monomial_basis_ref(polynomial: &'a Polynomial<F>, degree_bound: Option<usize>) -> Self {
257          Self::Monomial { polynomial: Cow::Borrowed(polynomial), degree_bound }
258      }
259  
260      pub fn new_monomial_basis(polynomial: Polynomial<'a, F>, degree_bound: Option<usize>) -> Self {
261          Self::Monomial { polynomial: Cow::Owned(polynomial), degree_bound }
262      }
263  
264      pub fn new_dense_monomial_basis_ref(polynomial: &'a DensePolynomial<F>, degree_bound: Option<usize>) -> Self {
265          let polynomial = Polynomial::Dense(Cow::Borrowed(polynomial));
266          Self::Monomial { polynomial: Cow::Owned(polynomial), degree_bound }
267      }
268  
269      pub fn new_dense_monomial_basis(polynomial: DensePolynomial<F>, degree_bound: Option<usize>) -> Self {
270          let polynomial = Polynomial::from(polynomial);
271          Self::Monomial { polynomial: Cow::Owned(polynomial), degree_bound }
272      }
273  
274      pub fn new_sparse_monomial_basis_ref(polynomial: &'a SparsePolynomial<F>, degree_bound: Option<usize>) -> Self {
275          let polynomial = Polynomial::Sparse(Cow::Borrowed(polynomial));
276          Self::Monomial { polynomial: Cow::Owned(polynomial), degree_bound }
277      }
278  
279      pub fn new_sparse_monomial_basis(polynomial: SparsePolynomial<F>, degree_bound: Option<usize>) -> Self {
280          let polynomial = Polynomial::from(polynomial);
281          Self::Monomial { polynomial: Cow::Owned(polynomial), degree_bound }
282      }
283  
284      pub fn new_lagrange_basis(evaluations: EvaluationsOnDomain<F>) -> Self {
285          Self::Lagrange { evaluations: Cow::Owned(evaluations) }
286      }
287  
288      pub fn new_lagrange_basis_ref(evaluations: &'a EvaluationsOnDomain<F>) -> Self {
289          Self::Lagrange { evaluations: Cow::Borrowed(evaluations) }
290      }
291  
292      pub fn is_in_monomial_basis(&self) -> bool {
293          matches!(self, Self::Monomial { .. })
294      }
295  
296      /// Retrieve the degree bound in `self`.
297      pub fn degree_bound(&self) -> Option<usize> {
298          match self {
299              Self::Monomial { degree_bound, .. } => *degree_bound,
300              _ => None,
301          }
302      }
303  
304      /// Retrieve the degree bound in `self`.
305      pub fn is_sparse(&self) -> bool {
306          match self {
307              Self::Monomial { polynomial, .. } => matches!(polynomial.as_ref(), Polynomial::Sparse(_)),
308              _ => false,
309          }
310      }
311  
312      pub fn is_in_lagrange_basis(&self) -> bool {
313          matches!(self, Self::Lagrange { .. })
314      }
315  
316      pub fn domain(&self) -> Option<EvaluationDomain<F>> {
317          match self {
318              Self::Lagrange { evaluations } => Some(evaluations.domain()),
319              _ => None,
320          }
321      }
322  
323      pub fn evaluate(&self, point: F) -> F {
324          match self {
325              Self::Monomial { polynomial, .. } => polynomial.evaluate(point),
326              Self::Lagrange { evaluations } => {
327                  let domain = evaluations.domain();
328                  let degree = domain.size() as u64;
329                  let multiplier = (point.pow([degree]) - F::one()) / F::from(degree);
330                  let powers: Vec<_> = domain.elements().collect();
331                  let mut denominators = cfg_iter!(powers).map(|pow| point - pow).collect::<Vec<_>>();
332                  alphavm_fields::batch_inversion(&mut denominators);
333                  cfg_iter_mut!(denominators)
334                      .zip_eq(powers)
335                      .zip_eq(&evaluations.evaluations)
336                      .map(|((denom, power), coeff)| *denom * power * coeff)
337                      .sum::<F>()
338                      * multiplier
339              }
340          }
341      }
342  }