Checking univariate identities in linear time

By Justin Drake && Ariel Gabizon && Izaak Meckler

Let

$H\subset F$ be a multiplicative subgroup of order

$n=2^t$.
In this note, we show a method for proving univariate identities over

$H$ hold where the prover runs in

$O(n)$ time when the polynomials involved have degree

$O(n)$, and the base identity is of constant degree. The most common example of such an identity is the degree 2 identity

$XY-Z$; namely, the Hadamard check:

$f\cdot g=h$ on

$H$.

The typical way to do such checks is via computing a quotient, e.g.

$T=(f\cdot g-h)/Z_H$ in the Hadamard case. This requires

$O(n\log n)$ operations.

Comparison to hyperplonk

Lately, people have been using sumcheck and multilinear polynomials to get

$O(n)$ prover time. Our protocol nearly matches the asymptotic performance of HyperPLONK.

In general, for an identity

$P$ of degree

$d$ involving

$k$ polynomials; the approach here will require essentially

$O(n\cdot d)$ evaluations of

$P$ from the prover, which is the same as the multilinear sumcheck approach used in HyperPLONK. In addition, however, we perform

$O(n)$ size

$d$ FFTs and a few other operations, which requires

$O(n\cdot (k+d\log d))$ additional field operations.

Depending on the structure of

$P$, the additional computation may be small enough
that a closer analysis of the concrete computation involved in both protocols would be required to determine their relative efficiencies.

Preliminaries

Denote by

$H\subset F$ a multiplicative subgroup of order

$n=2^t$.

$F$ is a field of prime order. Let

$H^{\prime }$ be the set of squares in

$H$ of size

$n/2$.
Througout the note we use FFT-style decomposition of univariate polynomials.
Namely, for a polynomial

$f$ of degree

$<d$,
we denote by

$f_e,f_o$ the unique polyonmials of degree

$<d/2$ such that

$$f(X)=f_e(X^2)+X\cdot f_o(X^2)$$

We make frequent use of how this decomposition behaves under multiplication. For example, given polys

$f,g$, we have

$$(f\cdot g{)}_e=f_e\cdot g_e+X^2{f}_o\cdot g_o$$

$$(f\cdot g{)}_o=f_e\cdot g_o+f_o\cdot g_e$$

We make crucial use of the fact that

$f_e,f_o$ can be evaluated at squares in

$F$ given oracle access to

$f$ via

$$f_e(x^2)=(f(x)+f(-x))/2;f_o(x^2)=(f(x)-f(-x))/2x$$

Lemma:
Given polys

$p,q$;

$p=q$ on

$H$ iff

$p_e=q_e$ and

$p_o=q_o$ on

$H^{\prime }$

proof:
Suppose that

$p=q$ on

$H$.
Using the above identity, we have that for each

$a\in H$,

$$p_e(a^2)+a\cdot p_o(a^2)=q_e(a^2)+a\cdot q_o(a^2)$$
Denote by

$p_e^{\prime },p_o^{\prime },q_e^{\prime },q_o^{\prime }$ the corresponding polynomials modulu

$Z_{H^{\prime }}$.
Note that this modulu operation doesn't change values on

$H^{\prime }$. So, since

$a^2\in H^{\prime }$ when

$a\in H$, we have for all

$a\in H$.

$$p_e^{\prime }(a^2)+a\cdot p_o^{\prime }(a^2)=q_e^{\prime }(a^2)+a\cdot q_o^{\prime }(a^2)$$
Note that the above is an identity holding for

$n$ points, where the lhs and rhs have degree smaller than

$n$.
Thus, we have as a polynomial identity

$$p_e^{\prime }(X^2)+X\cdot p_o^{\prime }(X^2)=q_e^{\prime }(X^2)+X\cdot q_o^{\prime }(X^2)$$
Note that in the above the coefficients of

$p_e^{\prime }$ are the even coefficients of the lhs, and the coefficients of

$q_e^{\prime }$ are the coefficients of the even powers of the rhs.
Therefore, since the above is a polynomial identity, we must have

$p_e^{\prime }=q_e^{\prime }$.

Similarly, we can argue the above implies

$p_o^{\prime }=q_o^{\prime }$.

In the other direction, assume

$p_e=q_e$, and

$p_o=q_o$ on

$H^{\prime }$.
For any

$a\in H$, we have

$$p(a)=p_e(a^2)+a\cdot p_o(a^2)=q_e(a^2)+a\cdot q_o(a^2)=q(a)$$

Basic case - a Hadamard check

Given KZG commitments to polynomials

$f,g,h$
of degree smaller than

$n$. (In fact, we just need that their degrees are

$O(n)$.)
We wish to check that

$f\cdot g=h$ on

$H$.
We reduce this to a similar check of half the size.

1. The prover interpolates on

   $H^{\prime }$ three polynomials of deg
   $<n/2$
   • $h_0:=f_e\cdot g_{e}mod{Z}_{H^{\prime }}$
   • $h_1:=f_e\cdot g_o+f_o\cdot g_{e}mod{Z}_{H^{\prime }}$
   • $h_2:=f_o\cdot g_{o}mod{Z}_{H^{\prime }}$
     Note that this can be done in
     $O(n)$ operations:
     we can compute
     $f_e,f_o,g_e,g_o$ on any point
     $a^2\in H^{\prime }$ using
     the values of
     $f,g$ on
     $a,-a\in H$.
     And thus in
     $O(n)$ time we can compute representations to
     $h_0,h_1,h_2$
     in the Lagrange base
     $L^{\prime }$ of
     $H^{\prime }$.

2. The prover computes and sends

   $KZG$-commitments to
   $h_0,h_1,h_2$.
   This can be done in
   $O(n)$
   $G_1$ operations, assuming we precompute the commitments to the basis functions in
   $L^{\prime }$.

3. The prover shows that

   • $h_e=h_0+X^2{h}_2$.
   • $h_o=h_1$.
     by the verifier choosing random
     $\alpha \in F$ and checking that
     
     $$h(\alpha )=h_0({\alpha }^2)+{\alpha }^2{h}_2({\alpha }^2)+\alpha \cdot h_1({\alpha }^2).$$

4. Verifier chooses random

   $r\in F$.

5. Prover sends commitments to

   $f^{\prime }=f_e+r\cdot f_o,g^{\prime }=g_e+r\cdot g_o$.

6. Verifier checks these commitments are correct at

   $\gamma ={\beta }^2$ for random
   $\beta$ (using the fact that
   $f_e(\gamma ),f_o(\gamma )$ can be evaluated using
   $f(\beta ),f(-\beta )$).

7. The verifier computes the commitment to

   $h^{\prime }:=h_0+r{h}_1+r^2{h}_2$ from the commitments to
   $h_0,h_1,h_2$.

8. Prover and verifier recursively run the protocol to check that

   $f^{\prime }\cdot g^{\prime }=h^{\prime }$ on
   $H^{\prime }$.

Efficiency:
We have

$\log n$ rounds with

$O(n/2^j)$ prover work in round

$j$, so total

$O(n)$

Soundness
Since

$f,g,h,h_0,h_1,h_2$ are committed before

$r$ is chosen, the recursive check

$(f_e+r\cdot f_o)(g_e+r\cdot g_o)=h_0+r{h}_1+r^2{h}_2$ on

$H^{\prime }$
implies

• $f_e{g}_e=h_0$ on
  $H^{\prime }$
• $f_e{g}_o+f_o{g}_e=h_1$ on
  $H^{\prime }$,
• $f_o{g}_o=h_2$ on
  $H^{\prime }$

as the coefficient of each power of

$r$ must be equal on both sides.
Since we checked that
-

$h_e=h_0+X^2{h}_2$.
-

$h_o=h_1$.
and we know that

• $(f\cdot g{)}_e=f_e\cdot g_e+X^2{f}_o\cdot g_o$
• $(f\cdot g{)}_o=f_e\cdot g_o+f_o\cdot g_e$

it follows that the recursive check tells us that on

$H^{\prime }$

• $(f\cdot g{)}_e=h_e$
• $(f\cdot g{)}_o=h_o$

which from the lemma tells us that

$fg=h$ on

$H$.

General Identities

In the general case, we have committed polynomials

$f_1,\dots ,f_k,h$ of degree

$<n$, and we assume the prover already has their values over

$H$.
We have a polynomial

$P(X_1,\dots ,X_k)$ of total degree

$d$,
and wish to show that

$$P(f_1(a),\dots ,f_k(a))=h(a),\mathrm{\forall }a\in H$$

We will similarly reduce to a check over

$H^{\prime }$ that will look like

$$P(f_1^{\prime }(a),\dots ,f_k^{\prime }(a))=h^{\prime }(a)\mathrm{\forall }a\in H^{\prime }$$

For some

$f_i^{\prime }$ and

$h^{\prime }$ of degree

$<n/2$.

To start, we need a slightly cumbersome definition.
Given

$P$, we define

$d+1$ polynomials

$P_0,\dots ,P_d$
such that over variables

$X_1,\dots ,X_k,Y_1,\dots Y_k,Z$

$$P(X_1+Z{Y}_1,\dots ,X_k+Z{Y}_k)=\sum _{j=0}^d{Z}^i{P}_j(X_1,\dots ,X_k,Y_1,\dots ,Y_k)$$

For example, when

$P=X_1{X}_2{X}_3$ we have

• $P_0=X_1{X}_2{X}_3$
• $P_1=X_1{X}_2{Y}_3+X_1{Y}_2{X}_3+Y_1{X}_2{X}_3$
• $P_2=X_1{Y}_2{Y}_3+Y_1{Y}_2{X}_3+Y_1{X}_2{Y}_3$
• $P_3=Y_1{Y}_2{Y}_3$

1. The prover computes on

   $H^{\prime }$ the evaluations of
   $d+1$ polynomials
   $h_0,\dots ,h_d$ of deg
   $<n/2$. Where
   
   $$h_i:=P_i(f_{1,e},\dots ,f_{k,e},f_{1,o},\dots ,f_{k,o})mod{Z}_{H^{\prime }}$$

   We claim the evaluations of the

   $\{h_i\}$ can be computed by
   $O(n\cdot d)$ evaluations of
   $P$ and
   $O(n\cdot (k+d\log d))$ additional field operations.

   To that end let

   $D\subseteq F$ be a smooth domain of size at least
   $d+1$. In practice when using power-of-two size domains,
   $D$ will have size equal to the smallest power of two greater than
   $d$, so size at most
   $2d$.

   • For each

     $a\in H^{\prime }$, we will simultaneously compute
     $h_0(a),\dots ,h_d(a)$:
     • Consider the univariate polynomial
       
       $$p_a(Z):=P(f_{1,e}(a)+Z{f}_{1,o}(a),\dots ,f_{k,e}(a)+Z{f}_{k,o}(a))$$
       For each
       $\delta \in D$, compute
       $p_a(\delta )$. Note that since we have access to the evalutions of the
       $f_{i,e}$ and
       $f_{i,o}$ on
       $H^{\prime }$, the computation of
       $p_a(\delta )$ only involves
       $k$ multiplications and additions followed by an evaluation of
       $P$.
       Then perform an iFFT on those evaluations to obtain the coefficients of
       $p_a$. By definition of the
       $P_j$,
       $p_a(Z)$ is equal to
       
       $$\sum _{j=0}^d{Z}^j{P}_j(f_{1,e}(a),\dots ,f_{k,e}(a),f_{1,o}(a),\dots ,f_{k,o}(a))=\sum _{j=0}^d{h}_j(a)Z^j$$
       Therefore, the coefficients of
       $p_a$ that we have computed are precisely
       $h_0(a),\dots ,h_d(a)$ as desired.

   This procedure involves

   $\frac{n}{2}\cdot d$ evaluations of
   $P$ and
   $\frac{n}{2}$ FFTs of size
   $O(d)$, which gives it the claimed efficiency.

2. The prover computes and sends

   $KZG$-commitments to
   $$h_0,h_1,\dots h_d$$.
   This takes
   $O(dn)$
   $G_1$ operations, assuming we precompute the commitments to the basis functions in
   $L^{\prime }$.

3. The prover shows that

   • $h_e=\sum _{i=0}^{d/2}{X}^{2i}{h}_{2i}(X)$.
   • $h_o=\sum _{i=0}^{d/2-1}{X}^{2i}{h}_{2i+1}(X)$.
     by the verifier choosing random
     $\alpha \in F$ and checking that
     
     $$h(\alpha )=\sum _{i=0}^d{\alpha }^i{h}_i({\alpha }^2)$$

4. Verifier chooses random

   $r\in F$.

5. For

   $i\in [k]$, the Prover sends commitments to
   $f_i^{\prime }=f_{i,e}+r\cdot f_{i,o}$.

6. Verifier checks these commitments are correct at

   $\gamma ={\beta }^2$ for random
   $\beta$ (using the fact that
   $f_{i,e},f_{i,o}$ can be evaluated using
   $f_i(\beta ),f_i(-\beta )$).

7. The verifier computes the commitment to

   $h^{\prime }:=\sum _{i=0}^d{r}^i{h}_i$ from the commitments to
   $\{h_i\}$.

8. Prover and verifier recursively run the protocol to check that

   $P(f_1^{\prime },\dots ,f_k^{\prime })=h^{\prime }$ on
   $H^{\prime }$.

Soundness
Similarly, to the Hadamard check case, one can check the protocol guarantees

• $P(f_1,\dots ,f_k{)}_e=h_e$
• $P(f_1,\dots ,f_k{)}_o=h_o$
  on
  $H^{\prime }$.

Which from the lemma tells us that

$P(f_1,\dots ,f_k)(a)=h(a)$ for all

$a\in H$.