halo2_proofs/
poly.rs

Help
1//! Contains utilities for performing arithmetic over univariate polynomials in
2//! various forms, including computing commitments to them and provably opening
3//! the committed polynomials at arbitrary points.
4
5use crate::arithmetic::parallelize;
6use crate::plonk::Assigned;
7
8use group::ff::{BatchInvert, Field};
9use pasta_curves::arithmetic::FieldExt;
10use std::fmt::Debug;
11use std::marker::PhantomData;
12use std::ops::{Add, Deref, DerefMut, Index, IndexMut, Mul, RangeFrom, RangeFull};
13
14pub mod commitment;
15mod domain;
16mod evaluator;
17pub mod multiopen;
18
19pub use domain::*;
20pub use evaluator::*;
21
22/// This is an error that could occur during proving or circuit synthesis.
23// TODO: these errors need to be cleaned up
24#[derive(Debug)]
25pub enum Error {
26    /// OpeningProof is not well-formed
27    OpeningError,
28    /// Caller needs to re-sample a point
29    SamplingError,
30}
31
32/// The basis over which a polynomial is described.
33pub trait Basis: Copy + Debug + Send + Sync {}
34
35/// The polynomial is defined as coefficients
36#[derive(Clone, Copy, Debug)]
37pub struct Coeff;
38impl Basis for Coeff {}
39
40/// The polynomial is defined as coefficients of Lagrange basis polynomials
41#[derive(Clone, Copy, Debug)]
42pub struct LagrangeCoeff;
43impl Basis for LagrangeCoeff {}
44
45/// The polynomial is defined as coefficients of Lagrange basis polynomials in
46/// an extended size domain which supports multiplication
47#[derive(Clone, Copy, Debug)]
48pub struct ExtendedLagrangeCoeff;
49impl Basis for ExtendedLagrangeCoeff {}
50
51/// Represents a univariate polynomial defined over a field and a particular
52/// basis.
53#[derive(Clone, Debug)]
54pub struct Polynomial<F, B> {
55    values: Vec<F>,
56    _marker: PhantomData<B>,
57}
58
59impl<F, B> Index<usize> for Polynomial<F, B> {
60    type Output = F;
61
62    fn index(&self, index: usize) -> &F {
63        self.values.index(index)
64    }
65}
66
67impl<F, B> IndexMut<usize> for Polynomial<F, B> {
68    fn index_mut(&mut self, index: usize) -> &mut F {
69        self.values.index_mut(index)
70    }
71}
72
73impl<F, B> Index<RangeFrom<usize>> for Polynomial<F, B> {
74    type Output = [F];
75
76    fn index(&self, index: RangeFrom<usize>) -> &[F] {
77        self.values.index(index)
78    }
79}
80
81impl<F, B> IndexMut<RangeFrom<usize>> for Polynomial<F, B> {
82    fn index_mut(&mut self, index: RangeFrom<usize>) -> &mut [F] {
83        self.values.index_mut(index)
84    }
85}
86
87impl<F, B> Index<RangeFull> for Polynomial<F, B> {
88    type Output = [F];
89
90    fn index(&self, index: RangeFull) -> &[F] {
91        self.values.index(index)
92    }
93}
94
95impl<F, B> IndexMut<RangeFull> for Polynomial<F, B> {
96    fn index_mut(&mut self, index: RangeFull) -> &mut [F] {
97        self.values.index_mut(index)
98    }
99}
100
101impl<F, B> Deref for Polynomial<F, B> {
102    type Target = [F];
103
104    fn deref(&self) -> &[F] {
105        &self.values[..]
106    }
107}
108
109impl<F, B> DerefMut for Polynomial<F, B> {
110    fn deref_mut(&mut self) -> &mut [F] {
111        &mut self.values[..]
112    }
113}
114
115impl<F, B> Polynomial<F, B> {
116    /// Iterate over the values, which are either in coefficient or evaluation
117    /// form depending on the basis `B`.
118    pub fn iter(&self) -> impl Iterator<Item = &F> {
119        self.values.iter()
120    }
121
122    /// Iterate over the values mutably, which are either in coefficient or
123    /// evaluation form depending on the basis `B`.
124    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut F> {
125        self.values.iter_mut()
126    }
127
128    /// Gets the size of this polynomial in terms of the number of
129    /// coefficients used to describe it.
130    pub fn num_coeffs(&self) -> usize {
131        self.values.len()
132    }
133}
134
135pub(crate) fn batch_invert_assigned<F: FieldExt>(
136    assigned: Vec<Polynomial<Assigned<F>, LagrangeCoeff>>,
137) -> Vec<Polynomial<F, LagrangeCoeff>> {
138    let mut assigned_denominators: Vec<_> = assigned
139        .iter()
140        .map(|f| {
141            f.iter()
142                .map(|value| value.denominator())
143                .collect::<Vec<_>>()
144        })
145        .collect();
146
147    assigned_denominators
148        .iter_mut()
149        .flat_map(|f| {
150            f.iter_mut()
151                // If the denominator is trivial, we can skip it, reducing the
152                // size of the batch inversion.
153                .filter_map(|d| d.as_mut())
154        })
155        .batch_invert();
156
157    assigned
158        .iter()
159        .zip(assigned_denominators.into_iter())
160        .map(|(poly, inv_denoms)| {
161            poly.invert(inv_denoms.into_iter().map(|d| d.unwrap_or_else(F::one)))
162        })
163        .collect()
164}
165
166impl<F: Field> Polynomial<Assigned<F>, LagrangeCoeff> {
167    pub(crate) fn invert(
168        &self,
169        inv_denoms: impl Iterator<Item = F> + ExactSizeIterator,
170    ) -> Polynomial<F, LagrangeCoeff> {
171        assert_eq!(inv_denoms.len(), self.values.len());
172        Polynomial {
173            values: self
174                .values
175                .iter()
176                .zip(inv_denoms.into_iter())
177                .map(|(a, inv_den)| a.numerator() * inv_den)
178                .collect(),
179            _marker: self._marker,
180        }
181    }
182}
183
184impl<'a, F: Field, B: Basis> Add<&'a Polynomial<F, B>> for Polynomial<F, B> {
185    type Output = Polynomial<F, B>;
186
187    fn add(mut self, rhs: &'a Polynomial<F, B>) -> Polynomial<F, B> {
188        parallelize(&mut self.values, |lhs, start| {
189            for (lhs, rhs) in lhs.iter_mut().zip(rhs.values[start..].iter()) {
190                *lhs += *rhs;
191            }
192        });
193
194        self
195    }
196}
197
198impl<'a, F: Field> Polynomial<F, LagrangeCoeff> {
199    /// Rotates the values in a Lagrange basis polynomial by `Rotation`
200    pub fn rotate(&self, rotation: Rotation) -> Polynomial<F, LagrangeCoeff> {
201        let mut values = self.values.clone();
202        if rotation.0 < 0 {
203            values.rotate_right((-rotation.0) as usize);
204        } else {
205            values.rotate_left(rotation.0 as usize);
206        }
207        Polynomial {
208            values,
209            _marker: PhantomData,
210        }
211    }
212}
213
214impl<'a, F: Field, B: Basis> Mul<F> for Polynomial<F, B> {
215    type Output = Polynomial<F, B>;
216
217    fn mul(mut self, rhs: F) -> Polynomial<F, B> {
218        parallelize(&mut self.values, |lhs, _| {
219            for lhs in lhs.iter_mut() {
220                *lhs *= rhs;
221            }
222        });
223
224        self
225    }
226}
227
228/// Describes the relative rotation of a vector. Negative numbers represent
229/// reverse (leftmost) rotations and positive numbers represent forward (rightmost)
230/// rotations. Zero represents no rotation.
231#[derive(Copy, Clone, Debug, PartialEq)]
232pub struct Rotation(pub i32);
233
234impl Rotation {
235    /// The current location in the evaluation domain
236    pub fn cur() -> Rotation {
237        Rotation(0)
238    }
239
240    /// The previous location in the evaluation domain
241    pub fn prev() -> Rotation {
242        Rotation(-1)
243    }
244
245    /// The next location in the evaluation domain
246    pub fn next() -> Rotation {
247        Rotation(1)
248    }
249}
halo2_proofs/poly.rs

halo2_proofs/
poly.rs
