Improving DEEP quotients computation

[hecmas]

TL;DR: The quotient $(f_i(X) - f_i(z))(X - z)$ can be moved entirely over the base field when the polynomial $f_i$ is defined over the base field, with a small overhead in the proof size and verification time that justifies a big improvement in proving time.

---

In the following, we denote by $\mathbb{F}$ a finite field of prime order and by $\mathbb{K}$ an extension field of $\mathbb{F}$ of degree $d$. We also denote by $\omega$ to a primitive $n$-th root of unity over $\mathbb{F}$.

In Round 6 of our eSTARK, we compute the following polynomial:

$$F(X) := \sum_{i=1}^{M} \epsilon_2^{i-1} \frac{f_i(X) - f_i(z)}{X - z} + \epsilon_1 \sum_{i=1}^{N} \epsilon_2^{i-1} \frac{h_i(X) - h_i(\omega z)}{X - \omega z}, \quad (1)$$

where $z \in \mathbb{K}$ is the opening challenge set by the verifier in Round 5, $\epsilon_1,\epsilon_2 \in \mathbb{K}$ are sent by the verifier at the start of Round 6 and $f_i,h_j$ are polynomials whose coefficients can be either over $\mathbb{F}$ or over $\mathbb{K}$ .

Notice that when the polynomial is over $\mathbb{F}$ we are "paying too much" in each of the quotients that involve such polynomials, i.e., we operate entirely over the extension field (including the division) even tho both the numerator and the denominator only have the constant coefficient in $\mathbb{K}$.

Explanation

Here is a trick¹ from the Polygon Zero team to reduce this cost. The idea starts by noticing that an extension field element $z$ is completely characterised by its minimal polynomial $m_z(X)$, that is, the (monic) polynomial of least degree (at most $d$) over $\mathbb{F}$ such that $m_z(z) = 0$.

Notice that such polynomial $m_z$ satisfies:

1. The value of a base field $f$ at $z$ coincides with that of the remainder $r(X) = f(X) \pmod{m_z(X)}$ (which is also a polynomial over $\mathbb{F}$): $$f(z) = q(z) \cdot m_z(z) + r(z) = r(z).$$
2. Proving that $f(X) - r(X)$ is divisible by $m_z(X)$ implies 1. and therefore the original eSTARK quotient claim.

Thus, the prover provides the polynomial $r$ instead of the value $f(z)$ and then it prove to V the low-degreeness of the quotient $(f(X) - r(X)) / m_z(X)$ rather than $(f(X) - f(z)) / X - z$, avoiding extension field operations at all.

Costs

First, both newly introduced polynomials $m_z$ and $r$ are defined over $\mathbb{F}$ and computing the its LDE is cheaper than computing the LDE over the extension field alternative. Also, notice that in our case there are only two minimal polynomials that need to be computed, namely $m_z$ and $m_{\omega z}$.

Second, the minimal polynomial $m_z$ is computed by searching for the smallest $2 \leq \ell \leq d$ such that the following linear system of $d$ equations and $\ell$ unknowns : $$c_0 + c_1 \cdot z + \dots + c_{\ell - 1} \cdot z^{\ell - 1} = - z^{\ell},$$ has solutions such that at least one of $c_0,c_1,\dots,c_{\ell - 1}$ is distinct from $0$.

Unrolling it out for our case, one must solve one of the following:

$$\left. \begin{array}{r} c_0+c_1 \cdot z_0 + z_0' = 0 \\ c_1 \cdot z_1 + z_1' = 0 \\ c_1 \cdot z_2 + z_2' = 0 \end{array} \right\} \qquad \left. \begin{array}{r} c_0+c_1 \cdot z_0 + c_2 \cdot z_0' + z_0'' = 0 \\ c_1 \cdot z_1 + c_2 \cdot z_1' + z_1'' = 0 \\ c_1 \cdot z_2 + c_2 \cdot z_2' + z_2'' = 0 \end{array} \right\}$$

where $z := (z_0,z_1,z_2), z^2 := (z_0,'z_1',z_2')$ and $z^3 := (z_0'',z_1'',z_2'')$.

The polynomials $m_z, m_{\omega z}$ are computed by both the prover and the verifier.

Use Case

This idea does not overcome the costs of the basic idea if the polynomials involved in the computation of $F(X)$ are not, in a huge amount, over the base filed. However, only those polynomials computed in the auxiliary trace of the eSTARK protocol are those the appear to be over the extension field. Following the ideas in pilcom-#53 would avoid having auxiliary columns and constraints and therefore this trick would be a big overall improvement.

Footnotes

1. I explain the trick for those polynomials whose evaluation at $z$ is requested, but the same holds for those whose evaluation at $\omega z$ is requested (in fact, at any other point). ↩

[symulacr]

In Round 6 of eSTARK, what polynomial is computed?

[symulacr]

What's the observation when the polynomial is over the base field?

[hecmas]

@solowmow Both questions are answered in the first comment. Aren't them?