Struct 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 is given in Theorem 8 in https://eprint.iacr.org/2022/1216 and it relies on the following 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 a larger agreement parameter.
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.
3. The error will depend on the batching used in building the DEEP polynomial. More precisely, when using algebraic batching there might be a loss of log_2(k + m - 1) bits of soundness.

Fields

trace: Vec<E>

Trace polynomial composition coefficients $\alpha_i$.

constraints: Vec<E>

Constraint column polynomial composition coefficients $\beta_j$.

Implementations

impl<E> DeepCompositionCoefficients<E>

where E: FieldElement,

pub fn draw_linear( public_coin: &mut impl RandomCoin<BaseField = <E as FieldElement>::BaseField>, trace_width: usize, num_constraint_composition_columns: usize, ) -> Result<DeepCompositionCoefficients<E>, RandomCoinError>

Generates the random values used in the construction of the DEEP polynomial when linear batching is used.

pub fn draw_algebraic( public_coin: &mut impl RandomCoin<BaseField = <E as FieldElement>::BaseField>, trace_width: usize, num_constraint_composition_columns: usize, ) -> Result<DeepCompositionCoefficients<E>, RandomCoinError>

Generates the random values used in the construction of the DEEP polynomial when algebraic batching is used.

pub fn draw_horner( public_coin: &mut impl RandomCoin<BaseField = <E as FieldElement>::BaseField>, trace_width: usize, num_constraint_composition_columns: usize, ) -> Result<DeepCompositionCoefficients<E>, RandomCoinError>

Generates the random values used in the construction of the DEEP polynomial when Horner-type batching is used.

Trait Implementations

impl<E> Clone for DeepCompositionCoefficients<E>

where E: Clone + FieldElement,

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

Returns a duplicate 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.