Struct winter_verifier::DeepCompositionCoefficients

pub struct DeepCompositionCoefficients<E>
where
    E: FieldElement,
{
    pub trace: Vec<E>,
    pub constraints: Vec<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 as: $$ Y(x) = \sum_{i=0}^k{( \alpha_i \cdot (\frac{T_i(x) - T_i(z)}{x - z} + \frac{T_i(x) - T_i(z \cdot g)}{x - z \cdot g}) )} + \sum_{j=0}^m{\beta_j \cdot \frac{H_j(x) - H_j(z)}{x - z}} $$ 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.
• $g$ is the generator of the trace domain. This is the $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.
• $\alpha_i$ is a composition coefficient for the $i$th trace polynomial.
• $\beta_j$ is a composition coefficient for the $j$th constraint column polynomial.

The soundness of the resulting protocol with batching as above is given in Theorem 8 in https://eprint.iacr.org/2022/1216 and it relies on two points:

1. The evaluation proofs for each trace polynomial at $z$ and $g \cdot z$ can be batched using the non-normalized Lagrange kernel over the set ${z, g \cdot z}$. This, however, requires that the FRI protocol is run with rate $\rho^{+} := \frac{\kappa + 2}{\nu}$ where $\kappa$ and $\nu$ are the length of the execution trace and the LDE domain size, respectively.
2. The resulting $Y(x)$ do not need to be degree adjusted but the soundness error of the protocol needs to be updated. For most combinations of batching parameters, this leads to a negligible increase in soundness error. The formula for the updated error can be found in Theorem 8 of https://eprint.iacr.org/2022/1216.

Fields

trace: Vec<E>

Trace polynomial composition coefficients $\alpha_i$.

constraints: Vec<E>

Constraint column polynomial composition coefficients $\beta_j$.

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.