## std::crypto::stark::deep_queries
| Procedure | Description |
| ----------- | ------------- |
| combine_main | Computes a single step of the random linear combination defining the DEEP composition polynomial
that is the input to the FRI protocol. More precisely, the sum in question is:
$$
\sum_{i=0}^k{\alpha_i \cdot \left(\frac{T_i(x) - T_i(z)}{x - z} +
\frac{T_i(x) - T_i(z \cdot g)}{x - z \cdot g} \right)}
$$
and the following instruction computes the denominators $\alpha_i \cdot (T_i(x) - T_i(z))$ and
$\alpha_i \cdot (T_i(x) - T_i(z \cdot g))$ and stores the values in two accumulators $r$ and $p$,
respectively. This instruction is specialized to main trace columns i.e. the values $T_i(x)$ are
base field elements.
The stack transition of the instruction can be visualized as follows:
+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+---+
\| T7 \| T6 \| T5 \| T4 \| T3 \| T2 \| T1 \| T0 \| p1 \| p0 \| r1 \| r0 \|x_addr\|z_addr\|a_addr\| - \|
+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+---+
\|\|
\/
+------+------+------+------+------+------+------+------+------+------+------+------+------+--------+--------+---+
\| T0 \| T7 \| T6 \| T5 \| T4 \| T3 \| T2 \| T1 \| p1' \| p0' \| r1' \| r0' \|x_addr\|z_addr+1\|a_addr+1\| - \|
+------+------+------+------+------+------+------+------+------+------+------+------+------+--------+--------+---+
Here:
1- Ti for i in 0..=7 stands for the the value of the i-th trace polynomial for the current query i.e. T_i(x).
2- (p0, p1) stands for an extension field element accumulating the values for the quotients with common denominator (x - gz).
3- (r0, r1) stands for an extension field element accumulating the values for the quotients with common denominator (x - z).
4- x_addr is the memory address from which we are loading the Ti's using the MSTREAM instruction.
5- z_addr is the memory address to the i-th OOD evaluation frame at z and gz i.e. T_i(z):= (T_i(z)0, T_i(z)1)
and T_i(gz):= (T_i(gz)0, T_i(gz)1)
6- a_addr is the memory address of the i-th random element used in batching the trace polynomial quotients.
The random elements a := (a0, a1) are stored in memory as [0, 0, a0, a1].
Input: [T7, T6, T5, T4, T3, T2, T1, T0, p1, p0, r1, r0, x_addr, z_addr, a_addr, 0]
Output: [T0, T7, T6, T5, T4, T3, T2, T1, p1', p0', r1', r0', x_addr, z_addr+1, a_addr+1, 0]
|
| combine_aux | Computes a single step of the random linear combination defining the DEEP composition polynomial
that is the input to the FRI protocol. More precisely, the sum in question is:
$$
\sum_{i=0}^k{\alpha_i \cdot \left(\frac{T_i(x) - T_i(z)}{x - z} +
\frac{T_i(x) - T_i(z \cdot g)}{x - z \cdot g} \right)}
$$
and the following instruction computes the denominators $\alpha_i \cdot (T_i(x) - T_i(z))$ and
$\alpha_i \cdot (T_i(x) - T_i(z \cdot g))$ and stores the values in two accumulators $r$ and $p$,
respectively. This instruction is specialized to auxiliary trace columns i.e. the values $T_i(x)$
are field elements in a quadratic extension field.
The stack transition of the instruction can be visualized as follows:
+-------+-------+-------+-------+-------+-------+-------+-------+------+------+------+------+------+------+------+---+
\| T31 \| T30 \| T21 \| T20 \| T11 \| T10 \| T01 \| T00 \| p1 \| p0 \| r1 \| r0 \|x_addr\|z_addr\|a_addr\| - \|
+-------+-------+-------+-------+-------+-------+-------+-------+------+------+------+------+------+------+------+---+
\|\|
\/
+-------+-------+-------+-------+-------+-------+-------+-------+------+------+------+------+------+--------+--------+-----+
\| T31 \| T30 \| T21 \| T20 \| T11 \| T10 \| T01 \| T00 \| p1' \| p0' \| r1' \| r0' \|x_addr\|z_addr+1\|a_addr+b\| - \|
+-------+-------+-------+-------+-------+-------+-------+-------+------+------+------+------+------+--------+--------------+
Here:
1- Tij for i in 0..=3 and j=0,1 stands for the the value of the j-th coordinate in the quadratic extension field
of the i-th auxiliary trace polynomial for the current query i.e. $T_i(x)$.
2- (p0, p1) stands for an extension field element accumulating the values for the quotients with common denominator (x - gz).
3- (r0, r1) stands for an extension field element accumulating the values for the quotients with common denominator (x - z).
4- x_addr is the memory address from which we are loading the Ti's using the MSTREAM instruction.
5- z_addr is the memory address to the i-th OOD evaluation frame at z and gz i.e. T_i(z):= (T_i(z)0, T_i(z)1) and T_i(gz):= (T_i(gz)0, T_i(gz)1)
6- a_addr is the memory address of the i-th random element used in batching the trace polynomial quotients.
The random elements a := (a0, a1) are stored in memory as [0, 0, a0, a1].
Input: [T31, T30, T21, T20, T11, T10, T01, T00, p1, p0, r1, r0, x_addr, z_addr, a_addr, 0]
Output: [T01, T00, T31, T30, T21, T20, T11, T10, p1', p0', r1', r0', x_addr, z_addr', a_addr', 0]
|
| compute_deep_composition_polynomial_queries | Compute the DEEP composition polynomial FRI queries.
Input: [query_ptr, ...]
Output: [...]
Cycles: 6 + num_queries * 463
|