Struct winter_prover::ConstraintDivisor

pub struct ConstraintDivisor<B> where
    B: StarkField,  { /* fields omitted */ }

The denominator portion of boundary and transition constraints.

A divisor is described by a combination of a sparse polynomial, which describes the numerator of the divisor and a set of exclusion points, which describe the denominator of the divisor. The numerator polynomial is described as multiplication of tuples where each tuple encodes an expression $(x^a - b)$. The exclusion points encode expressions $(x - a)$.

For example divisor $(x^a - 1) \cdot (x^b - 2) / (x - 3)$ can be represented as: numerator: [(a, 1), (b, 2)], exclude: [3].

A divisor cannot be instantiated directly, and instead must be created either for an Assertion or for a transition constraint.

Implementations

impl<B> ConstraintDivisor<B> where
    B: StarkField, 

pub fn from_transition(trace_length: usize) -> ConstraintDivisor<B>

Builds a divisor for transition constraints.

For transition constraints, the divisor polynomial $z(x)$ is always the same:

$$ z(x) = \frac{x^n - 1}{x - g^{n-1}} $$

where, $n$ is the length of the execution trace, and $g$ is the generator of the trace domain.

The above divisor specifies that transition constraints must hold on all steps of the execution trace except for the last one.

pub fn from_assertion(
    assertion: &Assertion<B>,
    trace_length: usize
) -> ConstraintDivisor<B>

Builds a divisor for a boundary constraint described by the assertion.

For boundary constraints, the divisor polynomial is defined as:

$$ z(x) = x^k - g^{a \cdot k} $$

where $g$ is the generator of the trace domain, $k$ is the number of asserted steps, and $a$ is the step offset in the trace domain. Specifically:

• For an assertion against a single step, the polynomial is $(x - g^a)$, where $a$ is the step on which the assertion should hold.
• For an assertion against a sequence of steps which fall on powers of two, it is $(x^k - 1)$ where $k$ is the number of asserted steps.
• For assertions against a sequence of steps which repeat with a period that is a power of two but don’t fall exactly on steps which are powers of two (e.g. 1, 9, 17, … ) it is $(x^k - g^{a \cdot k})$, where $a$ is the number of steps by which the assertion steps deviate from a power of two, and $k$ is the number of asserted steps. This is equivalent to $(x - g^a) \cdot (x - g^{a + j}) \cdot (x - g^{a + 2 \cdot j}) … (x - g^{a + (k - 1) \cdot j})$, where $j$ is the length of interval between asserted steps (e.g. 8).

Panics

Panics of the specified trace_length is inconsistent with the specified assertion.

pub fn numerator(&self) -> &[(usize, B)]

Returns the numerator portion of this constraint divisor.

pub fn exclude(&self) -> &[B]

Returns exclusion points (the denominator portion) of this constraints divisor.

pub fn degree(&self) -> usize

Returns the degree of the divisor polynomial

pub fn evaluate_at<E>(&self, x: E) -> E where
    E: FieldElement<BaseField = B>, 

Evaluates the divisor polynomial at the provided x coordinate.

Trait Implementations

impl<B> Clone for ConstraintDivisor<B> where
    B: Clone + StarkField, 

pub fn clone(&self) -> ConstraintDivisor<B>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<B> Debug for ConstraintDivisor<B> where
    B: Debug + StarkField, 

pub fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl<B> Display for ConstraintDivisor<B> where
    B: StarkField, 

pub fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl<B> PartialEq<ConstraintDivisor<B>> for ConstraintDivisor<B> where
    B: PartialEq<B> + StarkField, 

pub fn eq(&self, other: &ConstraintDivisor<B>) -> bool

This method tests for self and other values to be equal, and is used by ==.

pub fn ne(&self, other: &ConstraintDivisor<B>) -> bool

This method tests for !=.

impl<B> Eq for ConstraintDivisor<B> where
    B: Eq + StarkField, 

impl<B> StructuralEq for ConstraintDivisor<B> where
    B: StarkField, 

impl<B> StructuralPartialEq for ConstraintDivisor<B> where
    B: StarkField,