Struct winter_verifier::DeepCompositionCoefficients

pub struct DeepCompositionCoefficients<E>where
    E: FieldElement,{
    pub trace: Vec<(E, E, E), Global>,
    pub constraints: Vec<E, Global>,
    pub degree: (E, E),
}

Coefficients used in construction of DEEP composition polynomial.

These coefficients are created by the Air::get_deep_composition_coefficients() function. In the interactive version of the protocol, the verifier draws these coefficients uniformly at random from the extension field of the protocol.

The coefficients are used in computing the DEEP composition polynomial in two steps. First, we compute a random linear combination of trace and constraint composition polynomials as: $$ Y(x) = \sum_{i=0}^k{( \alpha_i \cdot \frac{T_i(x) - T_i(z)}{x - z} + \beta_i \cdot \frac{T_i(x) - T_i(z \cdot g)}{x - z \cdot g} + \gamma_i \cdot \frac{T_i(x) - T_i(\overline{z})}{x - \overline{z}} )} + \sum_{j=0}^m{\delta \cdot \frac{H_j(x) - H_j(z^m)}{x - z^m}} $$ where:

• $z$ is an out-of-domain point drawn randomly from the entire field. In the interactive version of the protocol, $z$ is provided by the verifier. $\overline{z}$ is the conjugate of $z$.
• $g$ is the generator of the trace domain. This is the same as $n$th root of unity where $n$ is the length of the execution trace.
• $T_i(x)$ is an evaluation of the $i$th trace polynomial at $x$, and $k$ is the total number of trace polynomials (which is equal to the width of the execution trace).
• $H_i(x)$ is an evaluation of the $j$th constraint composition column polynomial at $x$, and $m$ is the total number of column polynomials. The number of column polynomials is equal to the highest constraint degree rounded to the next power of two. For example, if the highest constraint degree is 6, $m$ will be equal to 8.
• $\alpha_i, \beta_i, \gamma_i$ are composition coefficients for the $i$th trace polynomial.
• $\delta_j$ is a composition coefficient for $j$th constraint column polynomial.

$T(x)$ and $H(x)$ are polynomials of degree $n - 1$, where $n$ is the length of the execution trace. Thus, the degree of $Y(x)$ polynomial is $n - 2$. To bring the degree back up to $n - 1$, we compute the DEEP composition polynomial as: $$ C(x) = Y(x) \cdot (\lambda + \mu \cdot x) $$ where $\lambda$ and $\mu$ are the composition coefficients for degree adjustment.

Fields

trace: Vec<(E, E, E), Global>

Trace polynomial composition coefficients $\alpha_i$, $\beta_i$, and $\gamma_i$.

constraints: Vec<E, Global>

Constraint column polynomial composition coefficients $\delta_j$.

degree: (E, E)

Degree adjustment composition coefficients $\lambda$ and $\mu$.

Trait Implementations

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

fn clone(&self) -> DeepCompositionCoefficients<E>

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.