Struct winter_verifier::TransitionConstraintGroup

pub struct TransitionConstraintGroup<E> where
    E: FieldElement,  { /* fields omitted */ }

A group of transition constraints all having the same degree.

A transition constraint group does not actually store transition constraints - it stores only their indexes and the info needed to compute their random linear combination. The indexes are assumed to be consistent with the order in which constraint evaluations are written into the evaluation table by the Air::evaluate_transition() function.

A transition constraint is described by a ration function of the form $\frac{C(x)}{z(x)}$, where:

• $C(x)$ is the constraint polynomial.
• $z(x)$ is the constraint divisor polynomial.

The divisor polynomial is the same for all transition constraints (see Air::transition_constraint_divisor()) and for this reason is not stored in a transition constraint group.

Implementations

impl<E> TransitionConstraintGroup<E> where
    E: FieldElement, 

pub fn indexes(&self) -> &[usize]

Returns indexes of all constraints in this group.

pub fn degree(&self) -> &TransitionConstraintDegree

Returns degree descriptors for all constraints in this group.

pub fn add(&mut self, constraint_idx: usize, coefficients: (E, E))

Adds a new constraint to the group. The constraint is identified by an index in the evaluation table.

pub fn merge_evaluations<B>(&self, evaluations: &[B], x: B) -> E where
    E: From<B>,
    B: FieldElement, 

Computes a linear combination of evaluations relevant to this constraint group.

The linear combination is computed as follows: $$ \sum_{i=0}^{k-1}{C_i(x) \cdot (\alpha_i + \beta_i \cdot x^d)} $$ where:

• $C_i(x)$ is the evaluation of the $i$th constraint at x (same as evaluations[i]).
• $\alpha$ and $\beta$ are random field elements. In the interactive version of the protocol, these are provided by the verifier.
• $d$ is the degree adjustment factor computed as $D + (n - 1) - deg(C_i(x))$, where $D$ is the degree of the composition polynomial, $n$ is the length of the execution trace, and $deg(C_i(x))$ is the evaluation degree of the $i$th constraint.

There are two things to note here. First, the degree adjustment factor $d$ is the same for all constraints in the group (since all constraints have the same degree). Second, the merged evaluations represent a polynomial of degree $D + n - 1$, which is higher then the target degree of the composition polynomial. This is because at this stage, we are merging only the numerators of transition constraints, and we will need to divide them by the divisor later on. The degree of the divisor for transition constraints is always $n - 1$. Thus, once we divide out the divisor, the evaluations will represent a polynomial of degree $D$.

Trait Implementations

impl<E> Clone for TransitionConstraintGroup<E> where
    E: Clone + FieldElement, 

pub fn clone(&self) -> TransitionConstraintGroup<E>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<E> Debug for TransitionConstraintGroup<E> where
    E: Debug + FieldElement, 

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

Formats the value using the given formatter.