Struct winter_verifier::Assertion
source · pub struct Assertion<E>where
E: FieldElement,{ /* private fields */ }
Expand description
An assertion made against an execution trace.
An assertion is always placed against a single column of an execution trace, but can cover multiple steps and multiple values. Specifically, there are three kinds of assertions:
- Single assertion - which requires that a value in a single cell of an execution trace is equal to the specified value.
- Periodic assertion - which requires that values in multiple cells of a single column are equal to the specified value. The cells must be evenly spaced at intervals with lengths equal to powers of two. For example, we can specify that values in a column must be equal to 0 at steps 0, 8, 16, 24, 32 etc. Steps can also start at some offset - e.g., 1, 9, 17, 25, 33 is also a valid sequence of steps.
- Sequence assertion - which requires that multiple cells in a single column are equal to the values from the provided list. The cells must be evenly spaced at intervals with lengths equal to powers of two. For example, we can specify that values in a column must be equal to a sequence 1, 2, 3, 4 at steps 0, 8, 16, 24. That is, value at step 0 should be equal to 1, value at step 8 should be equal to 2 etc.
Note that single and periodic assertions are succinct. That is, a verifier can evaluate them very efficiently. However, sequence assertions have liner complexity in the number of asserted values. Though, unless many thousands of values are asserted, practical impact of this linear complexity should be negligible.
Implementations
sourceimpl<E> Assertion<E>where
E: FieldElement,
impl<E> Assertion<E>where
E: FieldElement,
sourcepub fn single(column: usize, step: usize, value: E) -> Assertion<E>
pub fn single(column: usize, step: usize, value: E) -> Assertion<E>
Returns an assertion against a single cell of an execution trace.
The returned assertion requires that the value in the specified column
at the specified
step
is equal to the provided value
.
sourcepub fn periodic(
column: usize,
first_step: usize,
stride: usize,
value: E
) -> Assertion<E>
pub fn periodic(
column: usize,
first_step: usize,
stride: usize,
value: E
) -> Assertion<E>
Returns an single-value assertion against multiple cells of a single column.
The returned assertion requires that values in the specified column
must be equal to
the specified value
at steps which start at first_step
and repeat in equal intervals
specified by stride
.
Panics
Panics if:
stride
is not a power of two, or is smaller than 2.first_step
is greater thanstride
.
sourcepub fn sequence(
column: usize,
first_step: usize,
stride: usize,
values: Vec<E, Global>
) -> Assertion<E>
pub fn sequence(
column: usize,
first_step: usize,
stride: usize,
values: Vec<E, Global>
) -> Assertion<E>
Returns a multi-value assertion against multiple cells of a single column.
The returned assertion requires that values in the specified column
must be equal to
the provided values
at steps which start at first_step
and repeat in equal intervals
specified by stride
until all values have been consumed.
Panics
Panics if:
stride
is not a power of two, or is smaller than 2.first_step
is greater thanstride
.values
is empty or number of values in not a power of two.
sourcepub fn column(&self) -> usize
pub fn column(&self) -> usize
Returns index of the column against which this assertion is placed.
sourcepub fn first_step(&self) -> usize
pub fn first_step(&self) -> usize
Returns the first step of the execution trace against which this assertion is placed.
For single value assertions this is equivalent to the assertion step.
sourcepub fn stride(&self) -> usize
pub fn stride(&self) -> usize
Returns the interval at which the assertion repeats in the execution trace.
For single value assertions, this will be 0.
sourcepub fn values(&self) -> &[E] ⓘ
pub fn values(&self) -> &[E] ⓘ
Returns asserted values.
For single value and periodic assertions this will be a slice containing one value.
sourcepub fn is_single(&self) -> bool
pub fn is_single(&self) -> bool
Returns true if this is a single-value assertion (one value, one step).
sourcepub fn is_periodic(&self) -> bool
pub fn is_periodic(&self) -> bool
Returns true if this is a periodic assertion (one value, many steps).
sourcepub fn is_sequence(&self) -> bool
pub fn is_sequence(&self) -> bool
Returns true if this is a sequence assertion (many values, many steps).
sourcepub fn overlaps_with(&self, other: &Assertion<E>) -> bool
pub fn overlaps_with(&self, other: &Assertion<E>) -> bool
Checks if this assertion overlaps with the provided assertion.
Overlap is defined as asserting a value for the same step in the same column.
sourcepub fn validate_trace_width(
&self,
trace_width: usize
) -> Result<(), AssertionError>
pub fn validate_trace_width(
&self,
trace_width: usize
) -> Result<(), AssertionError>
Panics if the assertion cannot be placed against an execution trace of the specified width.
sourcepub fn validate_trace_length(
&self,
trace_length: usize
) -> Result<(), AssertionError>
pub fn validate_trace_length(
&self,
trace_length: usize
) -> Result<(), AssertionError>
Checks if the assertion is valid against an execution trace of the specified length.
Errors
Returns an error if:
trace_length
is not a power of two.- For single assertion,
first_step
>=trace_length
. - For periodic assertion,
stride
>trace_length
. - For sequence assertion,
num_values
*stride
!=trace_length
;
sourcepub fn apply<F>(&self, trace_length: usize, f: F)where
F: FnMut(usize, E),
pub fn apply<F>(&self, trace_length: usize, f: F)where
F: FnMut(usize, E),
Executes the provided closure for all possible instantiations of this assertions against a execution trace of the specified length.
Panics
Panics if the specified trace length is not valid for this assertion.
sourcepub fn get_num_steps(&self, trace_length: usize) -> usize
pub fn get_num_steps(&self, trace_length: usize) -> usize
Returns the number of steps against which this assertion will be applied given an execution trace of the specified length.
- For single-value assertions, this will always be one.
- For periodic assertions this will be equal to
trace_length
/stride
. - For sequence assertions this will be equal to the number of asserted values.
Panics
Panics if the specified trace length is not valid for this assertion.
Trait Implementations
sourceimpl<E> Clone for Assertion<E>where
E: Clone + FieldElement,
impl<E> Clone for Assertion<E>where
E: Clone + FieldElement,
sourceimpl<E> Debug for Assertion<E>where
E: Debug + FieldElement,
impl<E> Debug for Assertion<E>where
E: Debug + FieldElement,
sourceimpl<E> Display for Assertion<E>where
E: FieldElement,
impl<E> Display for Assertion<E>where
E: FieldElement,
sourceimpl<E> Ord for Assertion<E>where
E: FieldElement,
impl<E> Ord for Assertion<E>where
E: FieldElement,
We define ordering of assertions to be first by stride, then by first_step, and finally by column in ascending order.
1.21.0 · sourcefn max(self, other: Self) -> Selfwhere
Self: Sized,
fn max(self, other: Self) -> Selfwhere
Self: Sized,
1.21.0 · sourcefn min(self, other: Self) -> Selfwhere
Self: Sized,
fn min(self, other: Self) -> Selfwhere
Self: Sized,
1.50.0 · sourcefn clamp(self, min: Self, max: Self) -> Selfwhere
Self: Sized + PartialOrd<Self>,
fn clamp(self, min: Self, max: Self) -> Selfwhere
Self: Sized + PartialOrd<Self>,
sourceimpl<E> PartialEq<Assertion<E>> for Assertion<E>where
E: PartialEq<E> + FieldElement,
impl<E> PartialEq<Assertion<E>> for Assertion<E>where
E: PartialEq<E> + FieldElement,
sourceimpl<E> PartialOrd<Assertion<E>> for Assertion<E>where
E: FieldElement,
impl<E> PartialOrd<Assertion<E>> for Assertion<E>where
E: FieldElement,
sourcefn partial_cmp(&self, other: &Assertion<E>) -> Option<Ordering>
fn partial_cmp(&self, other: &Assertion<E>) -> Option<Ordering>
1.0.0 · sourcefn le(&self, other: &Rhs) -> bool
fn le(&self, other: &Rhs) -> bool
self
and other
) and is used by the <=
operator. Read more