Trait PolynomialSpace 

pub trait PolynomialSpace: Copy {
    type Val: Field;

    // Required methods
    fn size(&self) -> usize;
    fn first_point(&self) -> Self::Val;
    fn next_point<Ext: ExtensionField<Self::Val>>(&self, x: Ext) -> Option<Ext>;
    fn try_create_disjoint_domain(&self, min_size: usize) -> Option<Self>;
    fn split_domains(&self, num_chunks: usize) -> Vec<Self>;
    fn split_evals(
        &self,
        num_chunks: usize,
        evals: RowMajorMatrix<Self::Val>,
    ) -> Vec<RowMajorMatrix<Self::Val>> ;
    fn vanishing_poly_at_point<Ext: ExtensionField<Self::Val>>(
        &self,
        point: Ext,
    ) -> Ext;
    fn selectors_at_point<Ext: ExtensionField<Self::Val>>(
        &self,
        point: Ext,
    ) -> LagrangeSelectors<Ext>;
    fn selectors_on_coset(
        &self,
        coset: Self,
    ) -> LagrangeSelectors<Vec<Self::Val>>;
    fn evaluate_polynomial_at<Ext: ExtensionField<Self::Val>>(
        &self,
        evals: &[Self::Val],
        point: Ext,
    ) -> Ext;

    // Provided methods
    fn create_disjoint_domain(&self, min_size: usize) -> Self { ... }
    fn evaluate_periodic_column_at<Ext: ExtensionField<Self::Val>>(
        &self,
        col: &[Self::Val],
        point: Ext,
    ) -> Ext { ... }
    fn evaluate_periodic_columns_at<Ext: ExtensionField<Self::Val>>(
        &self,
        periodic_columns: &[Vec<Self::Val>],
        point: Ext,
    ) -> Vec<Ext> { ... }
}

Fixing a field, F, PolynomialSpace<Val = F> denotes an indexed subset of F^n with some additional algebraic structure.

We do not expect PolynomialSpace to store this subset, instead it usually contains some associated data which allows it to generate the subset or pieces of it.

Each PolynomialSpace should be part of a family of similar spaces for some collection of sizes (usually powers of two). Any space other than at the smallest size should be decomposable into a disjoint collection of smaller spaces. Additionally, the set of all PolynomialSpace of a given size should form a disjoint partition of some subset of F^n which supports a group structure.

The canonical example of a PolynomialSpace is a coset gH of a two-adic subgroup H of the multiplicative group F*. This satisfies the properties above as cosets partition the group and decompose as gH = g(H^2) u gh(H^2) for h any generator of H.

The other example in this code base is twin cosets which are sets of the form gH u g^{-1}H. The decomposition above extends easily to this case as h is a generator if and only if h^{-1} is and so gH u g^{-1}H = (g(H^2) u g^{-1}(H^2)) u (gh(H^2) u (gh)^{-1}(H^2)).

Required Associated Types

type Val: Field

The base field F.

Required Methods

fn size(&self) -> usize

The number of elements of the space.

fn first_point(&self) -> Self::Val

The first point in the space.

fn next_point<Ext: ExtensionField<Self::Val>>(&self, x: Ext) -> Option<Ext>

An algebraic function which takes the i’th element of the space and returns the (i+1)’th evaluated on the given point.

When PolynomialSpace corresponds to a coset, gH this function is multiplication by h for a chosen generator h of H.

This function may not exist for other classes of PolynomialSpace in which case this will return None.

fn try_create_disjoint_domain(&self, min_size: usize) -> Option<Self>

The non-panicking counterpart to Self::create_disjoint_domain.

Returns None instead of panicking when min_size is too large for a disjoint domain to be constructed (for two-adic domains, this happens when log_2(min_size) is not smaller than the field’s 2-adicity). Intended for verifier-side code, which must reject malformed or adversarial input rather than panic on it.

fn split_domains(&self, num_chunks: usize) -> Vec<Self>

Split the PolynomialSpace into num_chunks smaller PolynomialSpaces of equal size.

num_chunks must divide self.size() (which usually forces it to be a power of 2.) or this function will panic.

fn split_evals( &self, num_chunks: usize, evals: RowMajorMatrix<Self::Val>, ) -> Vec<RowMajorMatrix<Self::Val>>

Split a set of polynomial evaluations over this PolynomialSpace into a vector of polynomial evaluations over each PolynomialSpace generated from split_domains.

evals.height() must equal self.size() and num_chunks must divide self.size(). evals are assumed to be in standard (not bit-reversed) order.

fn vanishing_poly_at_point<Ext: ExtensionField<Self::Val>>( &self, point: Ext, ) -> Ext

Compute the vanishing polynomial of the space, evaluated at the given point.

This is a polynomial which evaluates to 0 on every point of the space self and has degree equal to self.size(). In other words it is a choice of element of the defining ideal of the given set with this extra degree property.

In the univariate case, it is equal, up to a linear factor, to the product over all elements x, of (X - x). In particular this implies it will not evaluate to 0 at any point not in self.

fn selectors_at_point<Ext: ExtensionField<Self::Val>>( &self, point: Ext, ) -> LagrangeSelectors<Ext>

Compute several Lagrange selectors at a given point.

• The Lagrange selector of the first point.
• The Lagrange selector of the last point.
• The Lagrange selector of everything but the last point.
• The inverse of the vanishing polynomial.

Note that these may not be normalized.

fn selectors_on_coset(&self, coset: Self) -> LagrangeSelectors<Vec<Self::Val>>

Compute several Lagrange selectors at all points of the given disjoint PolynomialSpace.

• The Lagrange selector of the first point.
• The Lagrange selector of the last point.
• The Lagrange selector of everything but the last point.
• The inverse of the vanishing polynomial.

Note that these may not be normalized.

fn evaluate_polynomial_at<Ext: ExtensionField<Self::Val>>( &self, evals: &[Self::Val], point: Ext, ) -> Ext

Evaluate the polynomial defined by evals (evaluations over self) at point.

Provided Methods

fn create_disjoint_domain(&self, min_size: usize) -> Self

Return another PolynomialSpace with size at least min_size disjoint from this space.

When working with spaces of power of two size, this will return a space of size 2^ceil(log_2(min_size)). This will fail if min_size is too large. In particular, log_2(min_size) should be smaller than the 2-adicity of the field.

This fixes a canonical choice for prover/verifier determinism and LDE caching.

Panics

Panics if min_size is too large for a disjoint domain to be constructed. Verifier-side code processing untrusted input should prefer Self::try_create_disjoint_domain, which reports this condition as None instead of panicking.

fn evaluate_periodic_column_at<Ext: ExtensionField<Self::Val>>( &self, col: &[Self::Val], point: Ext, ) -> Ext

Evaluate a periodic column polynomial at point.

col contains the period-length evaluations: row i of the full trace gets value col[i % col.len()]. The default expands to trace size and delegates to Self::evaluate_polynomial_at; domains with algebraic structure (e.g. two-adic cosets) can override for O(period) work.

Performance

This default is O(self.size()) time and allocates a self.size()-length vector, versus O(col.len()) for an override that exploits the domain’s algebraic structure (e.g. two-adic cosets folding onto a sub-coset). For a small period on a large trace this is a large (potentially many-orders-of- magnitude) verifier slowdown. Any new PolynomialSpace implementor should override this method rather than rely on the default.

fn evaluate_periodic_columns_at<Ext: ExtensionField<Self::Val>>( &self, periodic_columns: &[Vec<Self::Val>], point: Ext, ) -> Vec<Ext>

Evaluate several periodic column polynomials at point.

The default expands to one call to Self::evaluate_periodic_column_at per column. Domains with algebraic structure (e.g. two-adic cosets) can override to batch columns that share a period, paying for one interpolation instead of one per column.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementations on Foreign Types

impl<Val: TwoAdicField> PolynomialSpace for TwoAdicMultiplicativeCoset<Val>

fn next_point<Ext: ExtensionField<Val>>(&self, x: Ext) -> Option<Ext>

Getting the next point corresponds to multiplication by the generator.

fn try_create_disjoint_domain(&self, min_size: usize) -> Option<Self>

Given the coset gH, return the disjoint coset gfK where f is a fixed generator of F^* and K is the unique two-adic subgroup of with size 2^(ceil(log_2(min_size))).

Returns None if min_size > 1 << Val::TWO_ADICITY.

fn split_domains(&self, num_chunks: usize) -> Vec<Self>

Given the coset gH and generator h of H, let K = H^{num_chunks} be the unique group of order |H|/num_chunks.

Then we decompose gH into gK, ghK, gh^2K, ..., gh^{num_chunks}K.

fn vanishing_poly_at_point<Ext: ExtensionField<Val>>(&self, point: Ext) -> Ext

Compute the vanishing polynomial at the given point:

Z_{gH}(X) = g^{-|H|}\prod_{h \in H} (X - gh) = (g^{-1}X)^|H| - 1

fn selectors_at_point<Ext: ExtensionField<Val>>( &self, point: Ext, ) -> LagrangeSelectors<Ext>

Compute several Lagrange selectors at the given point:

Defining the vanishing polynomial by Z_{gH}(X) = g^{-|H|}\prod_{h \in H} (X - gh) = (g^{-1}X)^|H| - 1 return:

• Z_{gH}(X)/(g^{-1}X - 1): The Lagrange selector of the point g.
• Z_{gH}(X)/(g^{-1}X - h^{-1}): The Lagrange selector of the point gh^{-1} where h is the generator of H.
• (g^{-1}X - h^{-1}): The Lagrange selector of the subset consisting of everything but the point gh^{-1}.
• 1/Z_{gH}(X): The inverse of the vanishing polynomial.

fn selectors_on_coset(&self, coset: Self) -> LagrangeSelectors<Vec<Val>>

Compute the Lagrange selectors of our space at every point in the coset.

This will error if our space is not the group H and if the given coset is not disjoint from H.

fn evaluate_periodic_columns_at<Ext: ExtensionField<Val>>( &self, periodic_columns: &[Vec<Val>], point: Ext, ) -> Vec<Ext>

Evaluate several periodic column polynomials at point, sharing one coset materialization and batch inversion (via Interpolate::interpolate_coset) across all columns of a given period.

type Val = Val

fn size(&self) -> usize

fn first_point(&self) -> Self::Val

fn split_evals( &self, num_chunks: usize, evals: RowMajorMatrix<Self::Val>, ) -> Vec<RowMajorMatrix<Self::Val>>

fn evaluate_polynomial_at<Ext: ExtensionField<Val>>( &self, evals: &[Val], point: Ext, ) -> Ext

fn evaluate_periodic_column_at<Ext: ExtensionField<Val>>( &self, col: &[Val], point: Ext, ) -> Ext

Implementors