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 transition_degree_multiple(&self) -> usize { ... }
    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: PeriodicColumns<'_, 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 transition_degree_multiple(&self) -> usize

Degree multiple of the transition selector in units of a trace column.

The default is for two-adic domains, whose linear selector has degree independent of the trace length. Domains using a full trace-space selector, such as Circle, return one instead.

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 one periodic column polynomial at point.

The column lists one period of values, and row i of the trace reads position i mod p.

This is the per-column primitive behind the batched entry point. It assumes the length is a power of two that divides the domain size. Callers reach it through the batched entry point, which is where that is established.

Performance

The default expands the column to the full domain size, so it costs O(n) time and space. A domain with algebraic structure can fold onto a sub-coset instead and pay O(p). On a large trace with a small period that gap is many orders of magnitude of verifier time. Every new implementor should override this rather than rely on the default.

fn evaluate_periodic_columns_at<Ext: ExtensionField<Self::Val>>( &self, periodic_columns: PeriodicColumns<'_, Self::Val>, point: Ext, ) -> Vec<Ext>

Evaluate several periodic column polynomials at point.

Taking screened columns is what makes the shape rule unskippable. Every caller has to establish it before it can name this method at all.

The default evaluates one column at a time. Domains with algebraic structure can override to batch columns that share a period. That pays for one interpolation per period instead of one per column.

Panics

Debug builds panic when the columns were screened against a different number of rows. The rule is a relation between the lengths and the height, so the wrong height voids it.

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: PeriodicColumns<'_, Val>, point: Ext, ) -> Vec<Ext>

Evaluate several periodic column polynomials at point.

Columns sharing a period share one coset materialization and one batch inversion.

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