Galois FRI-Binius: Joseph Johnston's Idea

In this note, I will try to explicate an idea suggested to us by Joseph Johnston.

Normal FRI-Binius & Notation

In normal FRI-Binius, the prover kicks off the sumcheck by sending the verifier

$s_0:={(t(u_0,\dots ,u_{\kappa -1},r_{\kappa },\dots ,r_{\ell -1}))}_{u\in {\mathcal{B}}_{\kappa }}$. This information is enough for the verifier to compute

$t(r)$; indeed, the verifer can just compute

$\sum _{u\in {\mathcal{B}}_{\kappa }}{s}_{0,u}\cdot \widetilde{\mathtt{\text{eq}}}(u_0,\dots ,u_{\kappa -1},r_0,\dots ,r_{\kappa -1})$ and compare this thing to the claimed evaluation

$s$.

The tricky observation there is that the quantity

$s_0$ above is also nothing other than the column representation of

${\phi }_1(t^{\prime })({\phi }_0(r_{\kappa }),\dots ,{\phi }_0(r_{\ell -1}))$, which itself equals

$$\sum _{v\in {\mathcal{B}}_{{\ell }^{\prime }}}{t}^{\prime }(X_0,\dots ,X_{{\ell }^{\prime }-1})\cdot \widetilde{\mathtt{\text{eq}}}({\phi }_0(r_{\kappa }),\dots ,{\phi }_0(r_{\ell -1}),X_0,\dots ,X_{{\ell }^{\prime }-1}).$$
By running a sumcheck on this above thing, over the algebra, the prover and verifier can thus reduce the validity of

$s_0$ to that of

$t^{\prime }(r_0^{\prime },\dots ,r_{{\ell }^{\prime }-1}^{\prime })$.

Joseph's Idea

The first nontrivial claim is that the vector

$s_0:={(t(u_0,\dots ,u_{\kappa -1},r_{\kappa },\dots ,r_{\ell -1}))}_{u\in {\mathcal{B}}_{\kappa }}$ above—which, as we already saw, contains just the required data to compute

$t(r_0,\dots ,r_{\ell -1})$—is itself in turn "equivalent", up to a matrix mult, to the further data

$s^{\prime }:={({\phi }^{\{u\}}(t^{\prime })(r_{\kappa },\dots ,r_{\ell -1}))}_{u\in {\mathcal{B}}_{\kappa }}$. Here, we write

$\phi$ for the Frobenius, i.e., the thing that generates

$\text{Gal}(L/K)$. In particular:

Claim 1. We have the matrix identity:

$$\left[\begin{array}{c}{\phi }^0(t^{\prime })(r_{\kappa },\dots ,r_{\ell -1})\\ \\ ⋮\\ \\ {\phi }^{2^{\kappa }-1}(t^{\prime })(r_{\kappa },\dots ,r_{\ell -1})\end{array}\right]=\left[\begin{array}{ccc}& & \\ & & \\ \phantom{}& {\phi }^{\{u\}}({\beta }_v)\phantom{⋮}& \phantom{}\\ & & \\ & & \end{array}\right]\cdot \left[\begin{array}{c}t(0,\dots ,0,r_{\kappa },\dots ,r_{\ell -1})\\ \\ ⋮\\ \\ t(1,\dots ,1,r_{\kappa },\dots ,r_{\ell -1})\end{array}\right].$$
Proof. It's enough to fix arbitrary

$(r_{\kappa },\dots ,r_{\ell -1})\in L^{{\ell }^{\prime }}$ and

$u\in {\mathcal{B}}_{\kappa }$ and prove that

${\phi }^{\{u\}}(t^{\prime })(r_{\kappa },\dots ,r_{\ell -1})\stackrel{?}{=}\sum _{v\in {\mathcal{B}}_{\kappa }}{\phi }^{\{u\}}({\beta }_v)\cdot t(v\Vert r)$. To this end, we carry out the following calculation:

$$\begin{array}{rl}{\phi }^{\{u\}}(t^{\prime })(r_{\kappa },\dots ,r_{\ell -1})& =\sum _{w\in {\mathcal{B}}_{{\ell }^{\prime }}}{\phi }^{\{u\}}(t^{\prime }(w))\cdot \widetilde{\mathtt{\text{eq}}}(r_{[\kappa :]},w)\\ & =\sum _{w\in {\mathcal{B}}_{{\ell }^{\prime }}}{\phi }^{\{u\}}(\sum _{v\in {\mathcal{B}}_{\kappa }}t(v\Vert w)\cdot {\beta }_v)\cdot \widetilde{\mathtt{\text{eq}}}(r_{[\kappa :]},w)\\ & =\sum _{w\in {\mathcal{B}}_{{\ell }^{\prime }}}(\sum _{v\in {\mathcal{B}}_{\kappa }}t(v\Vert w)\cdot {\phi }^{\{u\}}({\beta }_v))\cdot \widetilde{\mathtt{\text{eq}}}(r_{[\kappa :]},w)\\ & =\sum _{v\in {\mathcal{B}}_{\kappa }}{\phi }^{\{u\}}({\beta }_v)\cdot (\sum _{w\in {\mathcal{B}}_{{\ell }^{\prime }}}t(v\Vert w)\cdot \widetilde{\mathtt{\text{eq}}}(r_{[\kappa :]},w))\\ & =\sum _{v\in {\mathcal{B}}_{\kappa }}{\phi }^{\{u\}}({\beta }_v)\cdot t(v\Vert r),\end{array}$$
which is what we want. The second equality above is just the definition of

$t^{\prime }(X_0,\dots ,X_{{\ell }^{\prime }-1})$. In the third, we distribute the Frobenius, and also use the fact that each

$t(v\Vert w)\in K$ (and is fixed by the Frobenius).

Claim 2. The matrix

$M$—i.e., whose

$(u,v{)}^{\text{th}}$ entry is

${\phi }^{\{u\}}({\beta }_v)$—is invertible.
Proof. This nontrivial fact is exactly [LN97, Lem. 3.51].

Now progressing onwards, we see moreover that the left-hand vector above itself can be made to relate to the evaluations of the single polynomal

$t^{\prime }(X_0,\dots ,X_{{\ell }^{\prime }-1})$ at a number of different places. Indeed, we have:

$$\left[\begin{array}{c}{\phi }^0(t^{\prime }({\phi }^{-0}(r_{\kappa }),\dots ,{\phi }^{-0}(r_{\ell -1})))\\ \\ ⋮\\ \\ {\phi }^{2^{\kappa }-1}(t^{\prime }({\phi }^{-(2^{\kappa }-1)}(r_{\kappa }),\dots ,{\phi }^{-(2^{\kappa }-1)}(r_{\ell -1})))\end{array}\right]=\left[\begin{array}{c}{\phi }^0(t^{\prime })(r_{\kappa },\dots ,r_{\ell -1})\\ \\ ⋮\\ \\ {\phi }^{2^{\kappa }-1}(t^{\prime })(r_{\kappa },\dots ,r_{\ell -1})\end{array}\right].$$
Moreover, given only the left-hand vector above, the verifier can locally "peel off" the

${\phi }^{\{u\}}$s, in order to obtain the further vector:

$$\left[\begin{array}{c}{t}^{\prime }({\phi }^{-0}(r_{\kappa }),\dots ,{\phi }^{-0}(r_{\ell -1}))\\ \\ ⋮\\ \\ t^{\prime }({\phi }^{-(2^{\kappa }-1)}(r_{\kappa }),\dots ,{\phi }^{-(2^{\kappa }-1)}(r_{\ell -1}))\end{array}\right].$$
The nice thing about this is that it's just

$t^{\prime }(X_0,\dots ,X_{{\ell }^{\prime }-1})$ evaluated at a number of different points, namely the "componentwise Galois orbit" of

$(r_{\kappa },\dots ,r_{\ell -1})\in L^{{\ell }^{\prime }}$. The idea now is that we're going to use [Fig. 3, RR21]-style batching on this set of claims. This will entail a single sumcheck which takes place entirely over

$L$.

Summary of Protocol

We will now sketch the end-to-end protocol.

0. In the commitment phase, the prover commits to the packed polynomial
   $t^{\prime }(X_0,\dots ,X_{{\ell }^{\prime }-1})\in L[X_0,\dots ,X_{{\ell }^{\prime }-1}{]}^{⪯1}$ just like it usually does.

In the eval phase, the parties have a joint evaluation point

$(r_0,\dots ,r_{\ell -1})$ and a claimed evaluation

$s$. The prover has

$t(X_0,\dots ,X_{\ell -1})\in K[X_0,\dots ,X_{\ell -1}{]}^{⪯1}$.

1. Prover sends verifier
   $s_0$, which is claimed to be
   ${(t(u_0,\dots ,u_{\kappa -1},r_{\kappa },\dots ,r_{\ell -1}))}_{u\in {\mathcal{B}}_{\kappa }}$.
2. Verifier checks
   $\sum _{u\in {\mathcal{B}}_{\kappa }}{s}_{0,u}\cdot \widetilde{\mathtt{\text{eq}}}(r_0,\dots ,r_{\kappa -1},u_0,\dots ,u_{\kappa -1})\stackrel{?}{=}s$.
3. Verifier then sets:
   
   $$\left[\begin{array}{c}\\ \\ s^{\prime }\\ \\ \end{array}\right]:=\left[\begin{array}{ccc}& & \\ & & \\ \phantom{}& M& \phantom{}\\ & & \\ & & \end{array}\right]\cdot \left[\begin{array}{c}\\ \\ s_0\\ \\ \end{array}\right],$$
   understood as an
   $L$-matrix mult. Verifier then moreover sets:
   
   $$\left[\begin{array}{c}\\ \\ \hat{s}\\ \\ \end{array}\right]:=\left[\begin{array}{c}\\ \\ {\phi }^{-\{u\}}\left(s^{\prime }\right)\\ \\ \end{array}\right];$$
   by this notation, we mean that the verifier applies
   ${\phi }^{-\{u\}}$ to each entry of
   $s^{\prime }$—i.e., with the exponent
   $-\{u\}$ varying—in order to get
   $\hat{s}$.

The prover and verifier now run an [RR21]-style batched sumcheck on the claims

${\hat{s}}_u\stackrel{?}{=}{t}^{\prime }({\phi }^{-\{u\}}(r_{\kappa }),\dots ,{\phi }^{-\{u\}}(r_{\ell -1}))$, for

$u\in {\mathcal{B}}_{\kappa }$. Unwinding what this means, we have:

4. The verifier samples random challenges
   $(r_0^{″},\dots ,r_{\kappa -1}^{″})$; sends them to the prover.
5. The verifier defines the initial sumcheck claim
   $s_0^{\ast }:=\sum _{u\in {\mathcal{B}}_{\kappa }}{\hat{s}}_u\cdot \widetilde{\mathtt{\text{eq}}}(r^{″},u)$.
6. Meanwhile, prover defines:
   
   $$h(X_0,\dots ,X_{{\ell }^{\prime }-1}):=t^{\prime }(X_0,\dots ,X_{{\ell }^{\prime }-1})\cdot \sum _{u\in {\mathcal{B}}_{\kappa }}\widetilde{\mathtt{\text{eq}}}(r^{″},u)\cdot \widetilde{\mathtt{\text{eq}}}(X,{\phi }^{-\{u\}}(r_{[\kappa :]}))$$
   here, we slightly abuse notation by writing
   ${\phi }^{-\{u\}}(r_{[\kappa :]}):=({\phi }^{-\{u\}}(r_{\kappa }),\dots ,{\phi }^{-\{u\}}(r_{\ell -1}))$.
7. The prover and verifier now run a normal sumcheck over L on the polynomial
   $h(X_0,\dots ,X_{{\ell }^{\prime }-1})$, for
   ${\ell }^{\prime }$ rounds. In parallel, they also FRI-fold.
8. At the very end, the verifier has a final sumcheck claim, which we'll call
   $s_{{\ell }^{\prime }}^{\ast }$, as well as a final FRI oracle, which we'll call
   $c$. At this point, the verifier checks
   
   $$s_{{\ell }^{\prime }}^{\ast }\stackrel{?}{=}c\cdot \sum _{u\in {\mathcal{B}}_{\kappa }}\widetilde{\mathtt{\text{eq}}}(r^{″},u)\cdot \widetilde{\mathtt{\text{eq}}}(r^{\prime },{\phi }^{-\{u\}}(r_{[\kappa :]}));$$
   here,
   $r^{\prime }:=(r_0^{\prime },\dots ,r_{{\ell }^{\prime }-1}^{\prime })$ is the point sampled during the course of the sumcheck.
9. Finally, the verifier does FRI querying.

Correctness

Assuming the truth of Claim 1, we argue correctness in the following way. If the prover is honest, then

$s_0={(t(u_0,\dots ,u_{\kappa -1},r_{\kappa },\dots ,r_{\ell -1}))}_{u\in {\mathcal{B}}_{\kappa }}$ will hold; by Claim 1, the verifier will have

$s^{\prime }={({\phi }^{\{u\}}(t^{\prime })(r_{\kappa },\dots ,r_{\ell -1}))}_{u\in {\mathcal{B}}_{\kappa }}={\left({\phi }^{\{u\}}(t^{\prime }({\phi }^{-\{u\}}(r_{\kappa }),\dots ,{\phi }^{-\{u\}}(r_{\ell -1})))\right)}_{u\in {\mathcal{B}}_{\kappa }}$. We see that the verifier will finally in turn have

$\hat{s}={(t^{\prime }({\phi }^{-\{u\}}(r_{\kappa }),\dots ,{\phi }^{-\{u\}}(r_{\ell -1})))}_{u\in {\mathcal{B}}_{\kappa }}$ The rest comes down to the correctness of Rothblum-style batching. In particular, you need to convince yourself that

$$\sum _{v\in {\mathcal{B}}_{{\ell }^{\prime }}}h(v)=\sum _{u\in {\mathcal{B}}_{\kappa }}\widetilde{\mathtt{\text{eq}}}(r^{″},u)\cdot t^{\prime }({\phi }^{-\{u\}}(r_{[\kappa :]}))=\sum _{u\in {\mathcal{B}}_{\kappa }}\widetilde{\mathtt{\text{eq}}}(r^{″},u)\cdot {\hat{s}}_u=s_0^{\ast }$$
will hold. The first equality involves interchanging a sum, and is essentially the "content" of [Fig. 3, RR21]'s completeness statement. The second equality holds assuming the prover was honest; this was just calculated above. The third equality is by definition on the verifier's part. Thus if the prover is honest, then its sumcheck claim will be true. The verifier's final step amounts to evaluating

$h(r_0^{\prime },\dots ,r_{{\ell }^{\prime }-1}^{\prime })$; here,

$c$ is used as a standin for

$t^{\prime }(r_0^{\prime },\dots ,r_{{\ell }^{\prime }-1}^{\prime })$.

Efficiency

The efficiency of the above protocol is quadratic for the verifier in

$2^{\kappa }$. Indeed, you can see this already in the verifier's multipliation

$s^{\prime }:=[M]\cdot s_0$. Actually, it is interesting to ask whether there is a kind of "Galois NTT", which would allow multiplication by

$[M]$ to be carried out in

$O(\kappa \cdot 2^{\kappa })$ time.

A further question is the verifier's computation of

$\hat{s}:={\phi }^{-\{u\}}(s^{\prime })$ above. It seems that the verifier needs to do "triangularly many" applications of the inverse Frobenius here; i.e., for each

$u\in {\mathcal{B}}_{\kappa }$, the computation

${\hat{s}}_u:={\phi }^{-\{u\}}(s_u^{\prime })$ will take

$\{u\}$ inverse Frobeniuses. Up to the issue of forward versus inverse (which shouldn't matter, since we can just "invert the triangle", using cyclicity), this will again take quadratic total work in

$2^{\kappa }$.

As far as proof cost: the total cost is a FRI-run on something

${\ell }^{\prime }$-variate over

$L$ and then also a sumcheck on something

${\ell }^{\prime }$-variate over

$L$. So it seems that we are getting 0 embedding overhead whatsoever (for the prover—the verifier needs to do some work).

Security

The fascinating fact is that Claim 2 is necessary for security. As a sketch, we need to argue that if

$t(r_0,\dots ,r_{\ell -1})\ne s$, then

$\mathcal{V}$ will reject. First off, assuming that (i.e. that the prover's claim is false), we immediately get the claim that if

$s_0={(t(u_0,\dots ,u_{\kappa -1},r_{\kappa },\dots ,r_{\ell -1}))}_{u\in {\mathcal{B}}_{\kappa }}$ then

$\mathcal{V}$ will reject its check 2. above. We may thus assume that

$s_0\ne {(t(u_0,\dots ,u_{\kappa -1},r_{\kappa },\dots ,r_{\ell -1}))}_{u\in {\mathcal{B}}_{\kappa }}$. In this case, assuming Claim 2, we have that

$M$ is injective; we may thus assume further that

$s^{\prime }\ne {({\phi }^{\{u\}}(t^{\prime })(r_{\kappa },\dots ,r_{\ell -1}))}_{u\in {\mathcal{B}}_{\kappa }}={\left({\phi }^{\{u\}}(t^{\prime }({\phi }^{-\{u\}}(r_{\kappa }),\dots ,{\phi }^{-\{u\}}(r_{\ell -1})))\right)}_{u\in {\mathcal{B}}_{\kappa }}$ will hold. Thus we finally get that

$\hat{s}\ne {(t^{\prime }({\phi }^{-\{u\}}(r_{\kappa }),\dots ,{\phi }^{-\{u\}}(r_{\ell -1})))}_{u\in {\mathcal{B}}_{\kappa }}$ will hold, since everything Frobenius-related is invertible. This then comes down to the soundness of (tensor-style) Rothblum batching, and the usual arguments of FRI-Binius. Thus the soundness overhead of this protocol over and above normal FRI-Binius is that of the tensor-style batch, which is

$O\left(\frac{\kappa }{|L|}\right)$.

References

[LN97]: Lidl, Rudolf and Niederreiter, Harald. Finite Fields. 1997.
[RR21]: Ron-Zewi, Noga and Rothblum, Ron. Local Proofs Approaching the Witness Length. Journal of the ACM.