snarkvm_algorithms/polycommit/sonic_pc/
polynomial.rs

1// Copyright 2024 Aleo Network Foundation
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 determines
65/// the amount of protection that will be provided to a commitment for this polynomial.
66#[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    /// Construct a new labeled polynomial by consuming `polynomial`.
82    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    /// Return the label for `self`.
97    pub fn label(&self) -> &str {
98        &self.info.label
99    }
100
101    /// Return the label for `self`.
102    pub fn to_label(&self) -> String {
103        self.info.label.clone()
104    }
105
106    /// Retrieve the polynomial from `self`.
107    pub fn polynomial(&self) -> &Polynomial<F> {
108        &self.polynomial
109    }
110
111    /// Retrieve a mutable reference to the enclosed polynomial.
112    pub fn polynomial_mut(&mut self) -> &mut Polynomial<'static, F> {
113        &mut self.polynomial
114    }
115
116    /// Evaluate the polynomial in `self`.
117    pub fn evaluate(&self, point: F) -> F {
118        self.polynomial.evaluate(point)
119    }
120
121    /// Retrieve the degree bound in `self`.
122    pub fn degree_bound(&self) -> Option<usize> {
123        self.info.degree_bound
124    }
125
126    /// Retrieve whether the polynomial in `self` should be hidden.
127    pub fn is_hiding(&self) -> bool {
128        self.info.hiding_bound.is_some()
129    }
130
131    /// Retrieve the hiding bound for the polynomial in `self`.
132    pub fn hiding_bound(&self) -> Option<usize> {
133        self.info.hiding_bound
134    }
135}
136
137/////////////////////////////////////////////////////////////////////////////////////
138/////////////////////////////////////////////////////////////////////////////////////
139/////////////////////////////////////////////////////////////////////////////////////
140/////////////////////////////////////////////////////////////////////////////////////
141
142#[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    /// Construct a new labeled polynomial by consuming `polynomial`.
150    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    /// Return the label for `self`.
182    pub fn label(&self) -> &str {
183        &self.info.label
184    }
185
186    /// Return the information about the label, degree bound, and hiding bound of `self`.
187    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    /// Evaluate the polynomial in `self`.
199    pub fn evaluate(&self, point: F) -> F {
200        self.polynomial.evaluate(point)
201    }
202
203    /// Retrieve the degree bound in `self`.
204    pub fn degree_bound(&self) -> Option<usize> {
205        match self.polynomial {
206            PolynomialWithBasis::Monomial { degree_bound, .. } => degree_bound,
207            _ => None,
208        }
209    }
210
211    /// Retrieve whether the polynomial in `self` should be hidden.
212    pub fn is_hiding(&self) -> bool {
213        self.info.hiding_bound.is_some()
214    }
215
216    /// Retrieve the hiding bound for the polynomial in `self`.
217    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    /// A polynomial in monomial basis, along with information about
245    /// its degree bound (if any).
246    Monomial { polynomial: Cow<'a, Polynomial<'a, F>>, degree_bound: Option<usize> },
247
248    /// A polynomial in Lagrange basis, along with information about
249    /// its degree bound (if any).
250    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    /// Retrieve the degree bound in `self`.
295    pub fn degree_bound(&self) -> Option<usize> {
296        match self {
297            Self::Monomial { degree_bound, .. } => *degree_bound,
298            _ => None,
299        }
300    }
301
302    /// Retrieve the degree bound in `self`.
303    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}