Struct winterfell::ConstraintDivisor
[−]pub struct ConstraintDivisor<B> where
B: StarkField, { /* private fields */ }
Expand description
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,
impl<B> ConstraintDivisor<B> where
B: StarkField,
pub fn from_transition(
trace_length: usize,
num_exemptions: usize
) -> ConstraintDivisor<B>
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>,
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 exemptions(&self) -> &[B]ⓘNotable traits for &'_ [u8]impl<'_> Read for &'_ [u8]impl<'_> Write for &'_ mut [u8]
pub fn exemptions(&self) -> &[B]ⓘNotable traits for &'_ [u8]impl<'_> Read for &'_ [u8]impl<'_> Write for &'_ mut [u8]
Returns exemption points (the denominator portion) of this constraints divisor.
pub fn evaluate_at<E>(&self, x: E) -> E where
E: FieldElement<BaseField = B>,
pub fn evaluate_at<E>(&self, x: E) -> E where
E: FieldElement<BaseField = B>,
Evaluates the divisor polynomial at the provided x
coordinate.
pub fn evaluate_exemptions_at<E>(&self, x: E) -> E where
E: FieldElement<BaseField = B>,
pub fn evaluate_exemptions_at<E>(&self, x: E) -> E where
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,
impl<B> Clone for ConstraintDivisor<B> where
B: Clone + StarkField,
fn clone(&self) -> ConstraintDivisor<B>
fn clone(&self) -> ConstraintDivisor<B>
Returns a copy of the value. Read more
1.0.0 · sourcefn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
impl<B> Debug for ConstraintDivisor<B> where
B: Debug + StarkField,
impl<B> Debug for ConstraintDivisor<B> where
B: Debug + StarkField,
impl<B> Display for ConstraintDivisor<B> where
B: StarkField,
impl<B> Display for ConstraintDivisor<B> where
B: StarkField,
impl<B> PartialEq<ConstraintDivisor<B>> for ConstraintDivisor<B> where
B: PartialEq<B> + StarkField,
impl<B> PartialEq<ConstraintDivisor<B>> for ConstraintDivisor<B> where
B: PartialEq<B> + StarkField,
fn eq(&self, other: &ConstraintDivisor<B>) -> bool
fn eq(&self, other: &ConstraintDivisor<B>) -> bool
This method tests for self
and other
values to be equal, and is used
by ==
. Read more
fn ne(&self, other: &ConstraintDivisor<B>) -> bool
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,
Auto Trait Implementations
impl<B> RefUnwindSafe for ConstraintDivisor<B> where
B: RefUnwindSafe,
impl<B> Send for ConstraintDivisor<B>
impl<B> Sync for ConstraintDivisor<B>
impl<B> Unpin for ConstraintDivisor<B> where
B: Unpin,
impl<B> UnwindSafe for ConstraintDivisor<B> where
B: UnwindSafe,
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more
sourceimpl<T> ToOwned for T where
T: Clone,
impl<T> ToOwned for T where
T: Clone,
type Owned = T
type Owned = T
The resulting type after obtaining ownership.
sourcefn clone_into(&self, target: &mut T)
fn clone_into(&self, target: &mut T)
toowned_clone_into
)Uses borrowed data to replace owned data, usually by cloning. Read more