halo2_axiom/
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 std::fmt::Debug;
6use std::io;
7use std::marker::PhantomData;
8use std::ops::{Add, Deref, DerefMut, Index, IndexMut, Mul, Range, RangeFrom, RangeFull, Sub};
9
10use crate::arithmetic::parallelize;
11use crate::helpers::SerdePrimeField;
12use crate::plonk::Assigned;
13use crate::SerdeFormat;
14
15#[cfg(feature = "multicore")]
16use crate::multicore::{
17    IndexedParallelIterator, IntoParallelRefIterator, ParallelIterator, ParallelSlice,
18};
19use group::ff::{BatchInvert, Field};
20
21/// Generic commitment scheme structures
22pub mod commitment;
23mod domain;
24mod query;
25mod strategy;
26
27/// Inner product argument commitment scheme
28pub mod ipa;
29
30/// KZG commitment scheme
31pub mod kzg;
32
33#[cfg(test)]
34mod multiopen_test;
35
36pub use domain::*;
37pub use query::{ProverQuery, VerifierQuery};
38pub use strategy::{Guard, VerificationStrategy};
39
40/// This is an error that could occur during proving or circuit synthesis.
41// TODO: these errors need to be cleaned up
42#[derive(Debug)]
43pub enum Error {
44    /// OpeningProof is not well-formed
45    OpeningError,
46    /// Caller needs to re-sample a point
47    SamplingError,
48}
49
50/// The basis over which a polynomial is described.
51pub trait Basis: Copy + Debug + Send + Sync {}
52
53/// The polynomial is defined as coefficients
54#[derive(Clone, Copy, Debug)]
55pub struct Coeff;
56impl Basis for Coeff {}
57
58/// The polynomial is defined as coefficients of Lagrange basis polynomials
59#[derive(Clone, Copy, Debug)]
60pub struct LagrangeCoeff;
61impl Basis for LagrangeCoeff {}
62
63/// The polynomial is defined as coefficients of Lagrange basis polynomials in
64/// an extended size domain which supports multiplication
65#[derive(Clone, Copy, Debug)]
66pub struct ExtendedLagrangeCoeff;
67impl Basis for ExtendedLagrangeCoeff {}
68
69/// Represents a univariate polynomial defined over a field and a particular
70/// basis.
71#[derive(Clone, Debug)]
72pub struct Polynomial<F, B> {
73    pub(crate) values: Vec<F>,
74    _marker: PhantomData<B>,
75}
76
77impl<F, B> Index<usize> for Polynomial<F, B> {
78    type Output = F;
79
80    fn index(&self, index: usize) -> &F {
81        self.values.index(index)
82    }
83}
84
85impl<F, B> IndexMut<usize> for Polynomial<F, B> {
86    fn index_mut(&mut self, index: usize) -> &mut F {
87        self.values.index_mut(index)
88    }
89}
90
91impl<F, B> Index<Range<usize>> for Polynomial<F, B> {
92    type Output = [F];
93
94    fn index(&self, index: Range<usize>) -> &[F] {
95        self.values.index(index)
96    }
97}
98
99impl<F, B> Index<RangeFrom<usize>> for Polynomial<F, B> {
100    type Output = [F];
101
102    fn index(&self, index: RangeFrom<usize>) -> &[F] {
103        self.values.index(index)
104    }
105}
106
107impl<F, B> IndexMut<Range<usize>> for Polynomial<F, B> {
108    fn index_mut(&mut self, index: Range<usize>) -> &mut [F] {
109        self.values.index_mut(index)
110    }
111}
112
113impl<F, B> IndexMut<RangeFrom<usize>> for Polynomial<F, B> {
114    fn index_mut(&mut self, index: RangeFrom<usize>) -> &mut [F] {
115        self.values.index_mut(index)
116    }
117}
118
119impl<F, B> Index<RangeFull> for Polynomial<F, B> {
120    type Output = [F];
121
122    fn index(&self, index: RangeFull) -> &[F] {
123        self.values.index(index)
124    }
125}
126
127impl<F, B> IndexMut<RangeFull> for Polynomial<F, B> {
128    fn index_mut(&mut self, index: RangeFull) -> &mut [F] {
129        self.values.index_mut(index)
130    }
131}
132
133impl<F, B> Deref for Polynomial<F, B> {
134    type Target = [F];
135
136    fn deref(&self) -> &[F] {
137        &self.values[..]
138    }
139}
140
141impl<F, B> DerefMut for Polynomial<F, B> {
142    fn deref_mut(&mut self) -> &mut [F] {
143        &mut self.values[..]
144    }
145}
146
147impl<F, B> Polynomial<F, B> {
148    /// Iterate over the values, which are either in coefficient or evaluation
149    /// form depending on the basis `B`.
150    pub fn iter(&self) -> impl Iterator<Item = &F> {
151        self.values.iter()
152    }
153
154    /// Iterate over the values mutably, which are either in coefficient or
155    /// evaluation form depending on the basis `B`.
156    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut F> {
157        self.values.iter_mut()
158    }
159
160    /// Gets the size of this polynomial in terms of the number of
161    /// coefficients used to describe it.
162    pub fn num_coeffs(&self) -> usize {
163        self.values.len()
164    }
165}
166
167impl<F: SerdePrimeField, B> Polynomial<F, B> {
168    /// Reads polynomial from buffer using `SerdePrimeField::read`.
169    pub(crate) fn read<R: io::Read>(reader: &mut R, format: SerdeFormat) -> Self {
170        let mut poly_len = [0u8; 4];
171        reader.read_exact(&mut poly_len).unwrap();
172        let poly_len = u32::from_be_bytes(poly_len);
173        Self {
174            values: (0..poly_len)
175                .map(|_| F::read(reader, format).unwrap())
176                .collect(),
177            _marker: PhantomData,
178        }
179    }
180
181    /// Writes polynomial to buffer using `SerdePrimeField::write`.
182    pub(crate) fn write<W: io::Write>(&self, writer: &mut W, format: SerdeFormat) {
183        writer
184            .write_all(&(self.values.len() as u32).to_be_bytes())
185            .unwrap();
186        for value in self.values.iter() {
187            value.write(writer, format).unwrap();
188        }
189    }
190}
191
192/// Invert each polynomial in place for memory efficiency
193pub(crate) fn batch_invert_assigned<F: Field, PA>(
194    assigned: Vec<PA>,
195) -> Vec<Polynomial<F, LagrangeCoeff>>
196where
197    PA: Deref<Target = [Assigned<F>]> + Sync,
198{
199    if assigned.is_empty() {
200        return vec![];
201    }
202    let n = assigned[0].as_ref().len();
203    // 1d vector better for memory allocation
204    let mut assigned_denominators: Vec<_> = assigned
205        .iter()
206        .flat_map(|f| f.as_ref().iter().map(|value| value.denominator()))
207        .collect();
208
209    assigned_denominators
210        .iter_mut()
211        // If the denominator is trivial, we can skip it, reducing the
212        // size of the batch inversion.
213        .filter_map(|d| d.as_mut())
214        .batch_invert();
215
216    #[cfg(feature = "multicore")]
217    return assigned
218        .par_iter()
219        .zip(assigned_denominators.par_chunks(n))
220        .map(|(poly, inv_denoms)| {
221            debug_assert_eq!(inv_denoms.len(), poly.as_ref().len());
222            Polynomial {
223                values: poly
224                    .as_ref()
225                    .iter()
226                    .zip(inv_denoms.iter())
227                    .map(|(a, inv_den)| a.numerator() * inv_den.unwrap_or(F::ONE))
228                    .collect(),
229                _marker: PhantomData,
230            }
231        })
232        .collect();
233
234    #[cfg(not(feature = "multicore"))]
235    return assigned
236        .iter()
237        .zip(assigned_denominators.chunks(n))
238        .map(|(poly, inv_denoms)| {
239            debug_assert_eq!(inv_denoms.len(), poly.as_ref().len());
240            Polynomial {
241                values: poly
242                    .as_ref()
243                    .iter()
244                    .zip(inv_denoms.iter())
245                    .map(|(a, inv_den)| a.numerator() * inv_den.unwrap_or(F::ONE))
246                    .collect(),
247                _marker: PhantomData,
248            }
249        })
250        .collect();
251}
252
253impl<F: Field> Polynomial<Assigned<F>, LagrangeCoeff> {
254    pub fn invert(
255        &self,
256        inv_denoms: impl Iterator<Item = F> + ExactSizeIterator,
257    ) -> Polynomial<F, LagrangeCoeff> {
258        assert_eq!(inv_denoms.len(), self.values.len());
259        Polynomial {
260            values: self
261                .values
262                .iter()
263                .zip(inv_denoms)
264                .map(|(a, inv_den)| a.numerator() * inv_den)
265                .collect(),
266            _marker: self._marker,
267        }
268    }
269}
270
271impl<'a, F: Field, B: Basis> Add<&'a Polynomial<F, B>> for Polynomial<F, B> {
272    type Output = Polynomial<F, B>;
273
274    fn add(mut self, rhs: &'a Polynomial<F, B>) -> Polynomial<F, B> {
275        parallelize(&mut self.values, |lhs, start| {
276            for (lhs, rhs) in lhs.iter_mut().zip(rhs.values[start..].iter()) {
277                *lhs += *rhs;
278            }
279        });
280
281        self
282    }
283}
284
285impl<'a, F: Field, B: Basis> Sub<&'a Polynomial<F, B>> for Polynomial<F, B> {
286    type Output = Polynomial<F, B>;
287
288    fn sub(mut self, rhs: &'a Polynomial<F, B>) -> Polynomial<F, B> {
289        parallelize(&mut self.values, |lhs, start| {
290            for (lhs, rhs) in lhs.iter_mut().zip(rhs.values[start..].iter()) {
291                *lhs -= *rhs;
292            }
293        });
294
295        self
296    }
297}
298
299impl<F: Field> Polynomial<F, LagrangeCoeff> {
300    /// Rotates the values in a Lagrange basis polynomial by `Rotation`
301    pub fn rotate(&self, rotation: Rotation) -> Polynomial<F, LagrangeCoeff> {
302        let mut values = self.values.clone();
303        if rotation.0 < 0 {
304            values.rotate_right((-rotation.0) as usize);
305        } else {
306            values.rotate_left(rotation.0 as usize);
307        }
308        Polynomial {
309            values,
310            _marker: PhantomData,
311        }
312    }
313}
314
315impl<F: Field, B: Basis> Mul<F> for Polynomial<F, B> {
316    type Output = Polynomial<F, B>;
317
318    fn mul(mut self, rhs: F) -> Polynomial<F, B> {
319        if rhs == F::ZERO {
320            return Polynomial {
321                values: vec![F::ZERO; self.len()],
322                _marker: PhantomData,
323            };
324        }
325        if rhs == F::ONE {
326            return self;
327        }
328
329        parallelize(&mut self.values, |lhs, _| {
330            for lhs in lhs.iter_mut() {
331                *lhs *= rhs;
332            }
333        });
334
335        self
336    }
337}
338
339impl<'a, F: Field, B: Basis> Sub<F> for &'a Polynomial<F, B> {
340    type Output = Polynomial<F, B>;
341
342    fn sub(self, rhs: F) -> Polynomial<F, B> {
343        let mut res = self.clone();
344        res.values[0] -= rhs;
345        res
346    }
347}
348
349/// Describes the relative rotation of a vector. Negative numbers represent
350/// reverse (leftmost) rotations and positive numbers represent forward (rightmost)
351/// rotations. Zero represents no rotation.
352#[derive(Copy, Clone, Debug, PartialEq, Eq)]
353pub struct Rotation(pub i32);
354
355impl Rotation {
356    /// The current location in the evaluation domain
357    pub fn cur() -> Rotation {
358        Rotation(0)
359    }
360
361    /// The previous location in the evaluation domain
362    pub fn prev() -> Rotation {
363        Rotation(-1)
364    }
365
366    /// The next location in the evaluation domain
367    pub fn next() -> Rotation {
368        Rotation(1)
369    }
370}
halo2_axiom/poly.rs

halo2_axiom/
poly.rs
