pub struct DeepCompositionCoefficients<E> where
E: FieldElement, {
pub trace: Vec<(E, E, E), Global>,
pub constraints: Vec<E, Global>,
pub degree: (E, E),
}
Expand description
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,
impl<E> Clone for DeepCompositionCoefficients<E> where
E: Clone + FieldElement,
fn clone(&self) -> DeepCompositionCoefficients<E>
fn clone(&self) -> DeepCompositionCoefficients<E>
Returns a copy of the value. Read more
1.0.0 · sourcefn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
Auto Trait Implementations
impl<E> RefUnwindSafe for DeepCompositionCoefficients<E> where
E: RefUnwindSafe,
impl<E> Send for DeepCompositionCoefficients<E>
impl<E> Sync for DeepCompositionCoefficients<E>
impl<E> Unpin for DeepCompositionCoefficients<E> where
E: Unpin,
impl<E> UnwindSafe for DeepCompositionCoefficients<E> where
E: UnwindSafe,
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more
sourceimpl<T> ToOwned for T where
T: Clone,
impl<T> ToOwned for T where
T: Clone,
type Owned = T
type Owned = T
The resulting type after obtaining ownership.
sourcefn clone_into(&self, target: &mut T)
fn clone_into(&self, target: &mut T)
toowned_clone_into
)Uses borrowed data to replace owned data, usually by cloning. Read more