Struct winter_verifier::BoundaryConstraintGroup

pub struct BoundaryConstraintGroup<F, E>where
    F: FieldElement,
    E: FieldElement<BaseField = <F as FieldElement>::BaseField> + ExtensionOf<F>,{ /* private fields */ }

A group of boundary constraints all having the same divisor.

A boundary constraint is described by a rational function $\frac{f(x) - b(x)}{z(x)}$, where:

• $f(x)$ is a trace polynomial for the column against which the constraint is placed.
• $b(x)$ is the value polynomial for the constraint.
• $z(x)$ is the constraint divisor polynomial.

A boundary constraint group groups together all boundary constraints where polynomial $z$ is the same. The constraints stored in the group describe polynomials $b$. At the time of constraint evaluation, a prover or a verifier provides evaluations of the relevant polynomial $f$ so that the value of the constraint can be computed.

When the protocol is run in a large field, types F and E are the same. However, when working with small fields, F and E can be set as follows:

• F could be the base field of the protocol, in which case E is the extension field used.
• F could be the extension field, in which case F and E are the same type.

The above arrangement allows us to describe boundary constraints for main and auxiliary segments of the execution trace. Specifically:

• For the constraints against columns of the main execution trace, F is set to the base field of the protocol, and E is set to the extension field.
• For the constraints against columns of auxiliary trace segments, both F and E are set to the extension field.

Implementations

impl<F, E> BoundaryConstraintGroup<F, E>where
    F: FieldElement,
    E: FieldElement<BaseField = <F as FieldElement>::BaseField> + ExtensionOf<F>,

pub fn constraints(&self) -> &[BoundaryConstraint<F, E>]

Returns a list of boundary constraints in this group.

pub fn divisor(&self) -> &ConstraintDivisor<<F as FieldElement>::BaseField>

Returns a divisor applicable to all boundary constraints in this group.

pub fn degree_adjustment(&self) -> u64

Returns a degree adjustment factor for all boundary constraints in this group.

pub fn evaluate_at(&self, state: &[E], x: E, xp: E) -> E

Evaluates all constraints in this group at the specified point x.

xp is a degree adjustment multiplier which must be computed as x^degree_adjustment. This value is provided as an argument to this function for optimization purposes.

Constraint evaluations are merges into a single value by computing their random linear combination and dividing the result by the divisor of this constraint group as follows: $$ \frac{\sum_{i=0}^{k-1}{C_i(x) \cdot (\alpha_i + \beta_i \cdot x^d)}}{z(x)} $$ where:

• $C_i(x)$ is the evaluation of the $i$th constraint at x computed as $f(x) - b(x)$.
• $\alpha$ and $\beta$ are random field elements. In the interactive version of the protocol, these are provided by the verifier.
• $z(x)$ is the evaluation of the divisor polynomial for this group at $x$.
• $d$ is the degree adjustment factor computed as $D - deg(C_i(x)) + deg(z(x))$, where $D$ is the degree of the composition polynomial.

Thus, the merged evaluations represent a polynomial of degree $D$, as the degree of the numerator is $D + deg(z(x))$, and the division by $z(x)$ reduces the degree by $deg(z(x))$.

Trait Implementations

impl<F, E> Clone for BoundaryConstraintGroup<F, E>where
    F: Clone + FieldElement,
    E: Clone + FieldElement<BaseField = <F as FieldElement>::BaseField> + ExtensionOf<F>,
    <F as FieldElement>::BaseField: Clone,

fn clone(&self) -> BoundaryConstraintGroup<F, E>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<F, E> Debug for BoundaryConstraintGroup<F, E>where
    F: Debug + FieldElement,
    E: Debug + FieldElement<BaseField = <F as FieldElement>::BaseField> + ExtensionOf<F>,
    <F as FieldElement>::BaseField: Debug,

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

Formats the value using the given formatter.