Struct winter_prover::TransitionConstraintGroup

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

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() or Air::evaluate_aux_transition() function.

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 degree_adjustment(&self) -> u64

Returns degree adjustment factor for this constraint group.

pub fn domain_offset_exp(&self) -> <E as FieldElement>::BaseField

Returns c^degree_adjustment where c is the coset offset.

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, F>(&self, evaluations: &[F], xp: B) -> Ewhere B: FieldElement, F: FieldElement<BaseField = <B as FieldElement>::BaseField> + ExtensionOf<B>, E: FieldElement<BaseField = <B as FieldElement>::BaseField> + ExtensionOf<B> + ExtensionOf<F>,

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 xp)} $$ where:

• $C_i(x)$ is the evaluation of the $i$th constraint at x (same as evaluations[i]).
• $xp = x^d$ where $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.
• $\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, <E as FieldElement>::BaseField: Clone,

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, <E as FieldElement>::BaseField: Debug,

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

Formats the value using the given formatter.