Struct winter_verifier::ConstraintDivisor

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

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 exemption 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 exemption 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)], exemptions: [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,
    num_exemptions: 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}{ \prod_{i=1}^k (x - g^{n-i})} $$

where, $n$ is the length of the execution trace, $g$ is the generator of the trace domain, and $k$ is the number of exemption points. The default value for $k$ is $1$.

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

pub fn from_assertion<E>(
    assertion: &Assertion<E>,
    trace_length: usize
) -> ConstraintDivisor<B>where
    E: FieldElement<BaseField = 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 exemptions(&self) -> &[B]

Returns exemption 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) -> Ewhere
    E: FieldElement<BaseField = B>,

Evaluates the divisor polynomial at the provided x coordinate.

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

Evaluates the denominator of this divisor (the exemption points) at the provided x coordinate.

Trait Implementations

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

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,

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

Formats the value using the given formatter.

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

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,

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

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

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

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,