pub struct TransitionConstraintGroup<E>where
E: FieldElement,{ /* private fields */ }
Expand description
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
sourceimpl<E> TransitionConstraintGroup<E>where
E: FieldElement,
impl<E> TransitionConstraintGroup<E>where
E: FieldElement,
sourcepub fn degree(&self) -> &TransitionConstraintDegree
pub fn degree(&self) -> &TransitionConstraintDegree
Returns degree descriptors for all constraints in this group.
sourcepub fn degree_adjustment(&self) -> u64
pub fn degree_adjustment(&self) -> u64
Returns degree adjustment factor for this constraint group.
sourcepub fn domain_offset_exp(&self) -> <E as FieldElement>::BaseField
pub fn domain_offset_exp(&self) -> <E as FieldElement>::BaseField
Returns c^degree_adjustment where c is the coset offset.
sourcepub fn add(&mut self, constraint_idx: usize, coefficients: (E, E))
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.
sourcepub 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>,
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 asevaluations[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
sourceimpl<E> Clone for TransitionConstraintGroup<E>where
E: Clone + FieldElement,
<E as FieldElement>::BaseField: Clone,
impl<E> Clone for TransitionConstraintGroup<E>where
E: Clone + FieldElement,
<E as FieldElement>::BaseField: Clone,
sourcefn clone(&self) -> TransitionConstraintGroup<E>
fn clone(&self) -> TransitionConstraintGroup<E>
1.0.0 · sourcefn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read more