# 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$.
Last changed by  
 
Ariel Gabizon
2104

Read more

Aztec emulated field and group operations

Disclaimer: This documentation was written on September, 2021. It is intended to give readers a high-level understanding. The codebase is the canonical source of truth, and over time this document might fall behind the implementation details of the code.

4/13/2024
Multiset checks in PLONK and Plookup

Grand Products PLONK at its technical heart is based on the following primitive - The grand product check: given commitments to polynomials $f,g$ over a finite field $\mathbb{F}$, and a subset $H={x_1,\ldots,x_n}\subset \mathbb{F}$ check that the product of values of $f$ and $g$ over $H$ agree. That is, whether $$\prod_{i\in [n]} a_i \stackrel{?}{=} \prod_{i\in [n]} b_i,$$ where $a_i = f(x_i)$ and $b_i = g(x_i)$. The PLONK paper shows this check can be performed with great efficiency when $H$ is a multiplicative subgroup. Polynomials and Vectors Throughout this post, whenever we discuss a vector $a$ of length $n$, we assume in the actual protocol the prover has sent a commitment to a polynomial $f$ with $f(x_i)=a_i$ as above. Thus, we can allow operations like adding vectors coordinate wise, that will be emulated in the real protocol by applying the same operation on the polynomial commitments.

6/10/2022
The Halo Effect

The purpose of this note is to explain (also to myself) the main idea in the Halo recursive SNARK construction of Bowe, Grigg and Hopwood https://eprint.iacr.org/2019/1021. In fact, my understanding of the protocol heavily relies on the new paper of Bünz, Chiesa, Mishra and Spooner [BCMS] which fills in many details and generalizes the approach to achieve "Proof Carrying Data Via Accumulation Schemes". The starting point is the inner product argument of Bootle et. al and its optimization in the Bullet Proofs paper. It was known that a special case of this inner product argument gave a polynomial commitment scheme (by taking the second vector to be a power vector of the form $(1,x,x^2,\ldots,x^n)$). Let us call this scheme for brevity the BP-PCS. For the purpose of this note it is not needed to understand the inner workings of BP-PCS. Here are its main good and bad properties:

3/12/2021
Read more from Ariel Gabizon
Published on HackMD