Struct winter_verifier::TransitionConstraintDegree

pub struct TransitionConstraintDegree { /* private fields */ }

Degree descriptor of a transition constraint.

Describes constraint degree as a combination of multiplications of periodic and trace columns. For example, degree of a constraint which requires multiplication of two trace columns can be described as: base: 2, cycles: []. A constraint which requires multiplication of 3 trace columns and a periodic column with a period of 32 steps can be described as: base: 3, cycles: [32].

Implementations

impl TransitionConstraintDegree

pub fn new(degree: usize) -> TransitionConstraintDegree

Creates a new transition constraint degree descriptor for constraints which involve multiplications of trace columns only.

For example, if a constraint involves multiplication of two trace columns, degree should be set to 2. If a constraint involves multiplication of three trace columns, degree should be set to 3 etc.

Panics

Panics if the provided degree is zero.

pub fn with_cycles(
    base_degree: usize,
    cycles: Vec<usize, Global>
) -> TransitionConstraintDegree

Creates a new transition degree descriptor for constraints which involve multiplication of trace columns and periodic columns.

For example, if a constraint involves multiplication of two trace columns and one periodic column with a period length of 32 steps, base_degree should be set to 2, and cycles should be set to vec![32].

Panics

Panics if:

• base_degree is zero.
• Any of the values in the cycles vector is smaller than two or is not powers of two.

pub fn get_evaluation_degree(&self, trace_length: usize) -> usize

Computes a degree to which this degree description expands in the context of execution trace of the specified length.

The expanded degree is computed as follows:

$$ b \cdot (n - 1) + \sum_{i = 0}^{k - 1}{\frac{n \cdot (c_i - 1)}{c_i}} $$

where: $b$ is the base degree, $n$ is the trace_length, $c_i$ is a cycle length of periodic column $i$, and $k$ is the total number of periodic columns for this degree descriptor.

Thus, evaluation degree of a transition constraint which involves multiplication of two trace columns and one periodic column with a period length of 32 steps when evaluated over an execution trace of 64 steps would be:

$$ 2 \cdot (64 - 1) + \frac{64 \cdot (32 - 1)}{32} = 126 + 62 = 188 $$

pub fn min_blowup_factor(&self) -> usize

Returns a minimum blowup factor needed to evaluate constraint of this degree.

This is guaranteed to be a power of two, greater than one.

Trait Implementations

impl Clone for TransitionConstraintDegree

fn clone(&self) -> TransitionConstraintDegree

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for TransitionConstraintDegree

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

Formats the value using the given formatter.

impl PartialEq<TransitionConstraintDegree> for TransitionConstraintDegree

fn eq(&self, other: &TransitionConstraintDegree) -> 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 Eq for TransitionConstraintDegree

impl StructuralEq for TransitionConstraintDegree

impl StructuralPartialEq for TransitionConstraintDegree