snarkvm_algorithms/polycommit/sonic_pc/
polynomial.rs

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

snarkvm_algorithms/polycommit/sonic_pc/
polynomial.rs
