Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improving DEEP quotients computation #54

Open
hecmas opened this issue Oct 30, 2023 · 3 comments
Open

Improving DEEP quotients computation #54

hecmas opened this issue Oct 30, 2023 · 3 comments
Assignees

Comments

@hecmas
Copy link
Contributor

hecmas commented Oct 30, 2023

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 trick1 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).

@hecmas hecmas self-assigned this Oct 30, 2023
@symulacr
Copy link

In Round 6 of eSTARK, what polynomial is computed?

@symulacr
Copy link

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

@hecmas
Copy link
Contributor Author

hecmas commented Nov 17, 2023

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants