# 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](https://www.espressosys.com/papers/hyperplonk.pdf) 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'$ 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'$ **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,p'_o,q'_e,q'_o$ the corresponding polynomials modulu $Z_{H'}$. Note that this modulu operation doesn't change values on $H'$. So, since $a^2\in H'$ when $a\in H$, we have for all $a\in H$. $$p'_e(a^2)+a\cdot p'_o(a^2)=q'_e(a^2)+a\cdot q'_o(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(X^2)+X\cdot p'_o(X^2)=q'_e(X^2)+X\cdot q'_o(X^2)$$ Note that in the above the coefficients of $p'_e$ are the even coefficients of the lhs, and the coefficients of $q'_e$ are the coefficients of the even powers of the rhs. Therefore, since the above is a polynomial identity, we must have $p'_e=q'_e$. Similarly, we can argue the above implies $p'_o=q'_o$. In the other direction, assume $p_e=q_e$, and $p_o=q_o$ on $H'$. 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'$ three polynomials of deg $<n/2$ - $h_0:=f_e\cdot g_e\;mod\; Z_{H'}$ - $h_1:=f_e\cdot g_o + f_o\cdot g_e\;mod\; Z_{H'}$ - $h_2:=f_o\cdot g_o\;mod\;Z_{H'}$ 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'$ 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'$ of $H'$. 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'$. 3. The prover shows that - $h_e=h_0+X^2h_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'=f_e+r\cdot f_o,g'=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':= h_0+rh_1 +r^2h_2$ from the commitments to $h_0,h_1,h_2$. 8. Prover and verifier recursively run the protocol to check that $f'\cdot g' = h'$ on $H'$. **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+rh_1 +r^2h_2$ on $H'$ implies - $f_e g_e = h_0$ on $H'$ - $f_eg_o + f_o g_e = h_1$ on $H'$, - $f_o g_o = h_2$ on $H'$ as the coefficient of each power of $r$ must be equal on both sides. Since we checked that - $h_e=h_0+X^2h_2$. - $h_o=h_1$. and we know that - $(f\cdot g)_e = f_e\cdot g_e + X^2f_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'$ - $(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,\ldots,f_k,h$ of degree $<n$, and we assume the prover already has their values over $H$. We have a polynomial $P(X_1,\ldots,X_k)$ of total degree $d$, and wish to show that $$P(f_1(a),\ldots,f_k(a))=h(a), \forall a\in H$$ We will similarly reduce to a check over $H'$ that will look like $$P(f'_1(a),\ldots,f'_k(a))=h'(a) \forall a\in H'$$ For some $f'_i$ and $h'$ of degree $<n/2$. To start, we need a slightly cumbersome definition. Given $P$, we define $d+1$ polynomials $P_0,\ldots,P_d$ such that over variables $X_1,\ldots,X_k,Y_1,\ldots Y_k,Z$ $$P(X_1+ZY_1,\ldots,X_k+ZY_k)=\sum_{j=0}^dZ^i P_j(X_1,\ldots,X_k,Y_1,\ldots,Y_k)$$ For example, when $P=X_1 X_2 X_3$ we have - $P_0=X_1X_2X_3$ - $P_1=X_1X_2Y_3+X_1Y_2X_3+Y_1X_2X_3$ - $P_2=X_1Y_2Y_3+Y_1Y_2X_3+Y_1X_2Y_3$ - $P_3=Y_1Y_2Y_3$ 1. The prover computes on $H'$ the evaluations of $d+1$ polynomials $h_0,\ldots,h_d$ of deg $<n/2$. Where $$h_i:=P_i(f_{1,e},\ldots,f_{k,e},f_{1,o},\ldots,f_{k,o})\;mod\;Z_{H'}$$ 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'$, 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'$, 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,\ldots h_d$$. This takes $O(dn)$ $G_1$ operations, assuming we precompute the commitments to the basis functions in $L'$. 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=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':= \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,\ldots,f'_k)= h'$ on $H'$. **Soundness** Similarly, to the Hadamard check case, one can check the protocol guarantees - $P(f_1,\ldots,f_k)_e = h_e$ - $P(f_1,\ldots,f_k)_o = h_o$ on $H'$. Which from the lemma tells us that $P(f_1,\ldots,f_k)(a)=h(a)$ for all $a\in H$.