You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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:
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:
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).$$
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:
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
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). ↩
The text was updated successfully, but these errors were encountered:
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:
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:
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$ .
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
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). ↩
The text was updated successfully, but these errors were encountered: