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