Hadamard checks from the Lagrange basis without FFTs === *Special thanks to Kobi Gurkan for correcting an error in the proof of the key lemma and for suggesting an optimisation.* **TLDR**: We show how to prove Hadamard relations between polynomials in the Lagrange basis without FFTs. This is the second part (see [part 1](https://notes.ethereum.org/T0ZVaaywQAqP4jegqO3asg?view), [part 2](https://notes.ethereum.org/Il4z42lmQtaUYFigsjsk2Q?view), [part 3](https://notes.ethereum.org/DLRqK9V7RIOsTZkab8Hm_Q?view)) in a series showing how to do PLONK-style universal SNARKs without FFTs. **Notation** We reuse all notation from the first post in the series. Additionally, let $H_\textrm{init} = \langle\omega\rangle$ be the subgroup generated by $\omega$ and assume $|H_\textrm{init}|$ is a power of 2. When $f$ is a polynomial we denote by $\bar f, f_\textrm{e}, f_\textrm{o}$ the polynomials such that: $$\left\{\begin{array}{ll} \bar f(X) = f(-X)\\ f_\textrm{e}(X^2) = \frac{f(X) + \bar f(X)}{2}\\ f_\textrm{o}(X^2) = \frac{f(X) - \bar f(X)}{2X}\\ \end{array} \right.$$ **Key lemma** (proved in appendix 1) Let $a, b, c, d$ be polynomials defined in an $H$-Lagrange basis where $|H|$ is divisible by 2. Let $r$ a random verifier challenge. If $H' = \{h^2 | h\in H\}$ and $$\left\{\begin{array}{ll} a' = a_\textrm{e} + ra_\textrm{o}\\ b' = b_\textrm{e} + rb_\textrm{o}\\ c' = c_\textrm{e} + rc_\textrm{o}\\ d' = r^2d_\textrm{e}/X + rd_\textrm{o}\\ \end{array} \right.$$ then $$\left\{\begin{array}{ll} ab = c + d\\ a\bar b = c - d\\ \end{array} \right.\textrm{ on }H\iff \left\{\begin{array}{ll} a'b' = c' + d'\\ a'\bar b' = c' - d'\\ \end{array} \right.\textrm{ on }H'$$ **Hadamard product check** With the above lemma we construct a polynomial protocol for Hadamard product checks without FFTs. The construction is recursive and runs in a logarithmic number of rounds. *initialisation*—Given the initial Hadamard check $a_\textrm{init}b_\textrm{init}=x_\textrm{init}$ on $H_\textrm{init}$ the prover computes with a linear pass from $a_\textrm{init}, b_\textrm{init}$ the minimal polynomials $c_\textrm{init}, d_\textrm{init}$ such that $$\left\{\begin{array}{ll} a_\textrm{init}b_\textrm{init} = c_\textrm{init} + d_\textrm{init}\\ a_\textrm{init}\bar b_\textrm{init} = c_\textrm{init} - d_\textrm{init}\\ \end{array} \right.$$ The recursion is initialised with the prover sending Kate commitments to $a_\textrm{init}, b_\textrm{init}, c_\textrm{init}, d_\textrm{init}$. (Notice that the commitment to $x_\textrm{init}$ can be computed from the commitments to $c_\textrm{init}, d_\textrm{init}$ using linearity.) *recursive step*—At every round the prover has four polynomials $a, b, c, d$ in an $H$-Lagrange basis with $|H|$ divisible by 2 and the verifier has the corresponding commitments. The prover sends commitments to $a_\textrm{e}, a_\textrm{o}, b_\textrm{e}, b_\textrm{o}, c_\textrm{e}, c_\textrm{o}, d_\textrm{e}/X, d_\textrm{o}$. The verifier responds with a random challenge $r$ and derives commitments to $a', b', c', d'$ using linearity. This recursive step is repeated—replacing $a, b, c, d$ by $a', b', c', d'$ (of half the degree) and replacing $H$ by $H'$ (of half the size)—until $a_\textrm{end}, b_\textrm{end}, c_\textrm{end}, d_\textrm{end}$ have degree 0 and $|H_\textrm{end}| = 1$. *final checks*—At the end of the protocol the verifier samples a random evaluation point $z$ and performs various consistency checks. Consistency of commitment triples to $f, f_\textrm{e}, f_\textrm{o}$ (relevant for the $a, b, c$ polynomials) is as follows: $$\left\{\begin{array}{ll} f(z) = f_\textrm{e}(z^2) + zf_\textrm{o}(z^2)\\ f(-z) = f_\textrm{e}(z^2) - zf_\textrm{o}(z^2)\\ \end{array} \right.$$ Consistency of commitment triples to $f, f_\textrm{e}/X, f_\textrm{o}$ (relevant for the $d$ polynomials) is similar: $$\left\{\begin{array}{ll} f(z) = z^2(f_\textrm{e}/X)(z^2) + zf_\textrm{o}(z^2)\\ f(-z) = z^2(f_\textrm{e}X)(z^2) - zf_\textrm{o}(z^2)\\ \end{array} \right.$$ The above consistency checks are linear, i.e. operations on openings only involve multiplication by scalars (namely $-1, z, -z, z^2$), addition, and equality checking. Using commitment linearity all checks (across all polynomials and all rounds) can be batched with just three openings at the evaluation points $\{z, -z, z^2\}$. The verifier also performs the boundary checks $$\left\{\begin{array}{ll} a_\textrm{end}(z)b_\textrm{end}(z) = c_\textrm{end}(z) + d_\textrm{end}(z)\\ a_\textrm{end}(z)\bar b_\textrm{end}(z) = c_\textrm{end}(z) - d_\textrm{end}(z)\\ \end{array} \right.$$ **Early termination** Notice that the above protocol can be terminated early to avoid unnecessary work and comminication. Indeed, as soon as the FFT costs for computing the quotients $q_1 = (ab - c - d)\big/Z_H$ and $q_2 = (a\bar b - c + d)\big/Z_H$ (here $Z_H$ is the vanishing polynomial on $H$) are deemed small enough the prover sends $q_1, q_2$ and the verifier checks $$\left\{\begin{array}{ll} q_1(z)Z_H(z) = a(z)b(z) - c(z) - d(z)\\ q_2(z)Z_H(z) = a(z)b(-z) - c(z) + d(z)\\ \end{array} \right.$$ Notice that early termination allows for $|H_\textrm{init}|$ to not be a power of 2. Assymptotically, since FFTs are $O(n \log n)$, one can terminate after $O(\log n - \log \log n)$ rounds. **Hadamard square checks** Notice that for Hadamard square checks we have $a=b$ and $(a \bar a)_e = 0$ which implies: $$\left\{\begin{array}{ll} a_\textrm{e} = b_\textrm{e}\\ a_\textrm{o} = b_\textrm{o}\\ c_\textrm{o} = d_\textrm{o}\\ \end{array} \right.$$ This means the prover only needs to sends 5 (as opposed to 8) commitments at every round. Notice also that two Hadamard square checks $a_1 = x_1^2, a_2^2 = x_2^2$ can be batched into one Hadamard square check. Indeed, if $r$ is a random verifier challenge and $a_* = a_1 + ra_2$ then $$\left\{\begin{array}{ll} a_1a_1 = c_{1} + d_{1}\\ a_1\bar a_1 = c_{1} - d_{1}\\ a_2a_2 = c_{2} + d_{2}\\ a_2\bar a_2 = c_{2} - d_{2}\\ a_1a_2 = c_{1,2} + d_{1,2}\\ a_1\bar a_2 = c_{1,2} - d_{1,2}\\ \end{array} \right.\iff \left\{\begin{array}{ll} a_*a_* = (c_{1} + d_{1}) + r(c_{1,2} + d_{1,2}) + r^2(c_{2} + d_{2})\\ a_*\bar a_* = (c_{1} - d_{1}) + r(c_{1,2} - d_{1,2}) + r^2(c_{2} - d_{2})\\ \end{array} \right.$$ This batching trick comes at the cost of two commitments to the $c_{1,2}, d_{1,2}$ corresponding to the cross-product $a_1a_2$. Finally, notice that one multiplication check can be reduced to two square checks since $ab = \frac{(a + b)^2 - (a - b)^2}{4}$. Repeated reduction to squaring gates combined with batching allows for several Hadamard product checks to be batched into a single Hadamard square check. **Appendix 1—proof of key lemma** \begin{align*} &\quad (1)\left\{\begin{array}{ll} ab = c + d\\ a\bar b = c - d\\ \end{array} \right.\textrm{ on }H\\ \iff &\quad (2)\left\{\begin{array}{ll} (ab)_\textrm{e} = (c + d)_\textrm{e}\\ (ab)_\textrm{o} = (c + d)_\textrm{o}\\ (a\bar b)_\textrm{e} = (c - d)_\textrm{e}\\ (a\bar b)_\textrm{o} = (c - d)_\textrm{o}\\ \end{array} \right.\textrm{ on }H'\\ \iff &\quad (3)\left\{\begin{array}{ll} a_\textrm{e}b_\textrm{e} + Xa_\textrm{o}b_\textrm{o} = c_\textrm{e} + d_\textrm{e}\\ a_\textrm{o}b_\textrm{e} + a_\textrm{e}b_\textrm{o} = c_\textrm{o} + d_\textrm{o}\\ a_\textrm{e}b_\textrm{e} - Xa_\textrm{o}b_\textrm{o} = c_\textrm{e} - d_\textrm{e}\\ a_\textrm{o}b_\textrm{e} - a_\textrm{e}b_\textrm{o} = c_\textrm{o} - d_\textrm{o}\\ \end{array} \right.\textrm{ on }H'\\ \iff &\quad (4)\left\{\begin{array}{ll} a_\textrm{e}b_\textrm{e} = c_\textrm{e}\\ a_\textrm{o}b_\textrm{e} = c_\textrm{o}\\ a_\textrm{e}b_\textrm{o} = d_\textrm{o}\\ a_\textrm{o}b_\textrm{o} = d_\textrm{e}/X\\ \end{array} \right.\textrm{ on }H'\\ \iff &\quad (5)\left\{\begin{array}{ll} (a_\textrm{e} + ra_\textrm{o})(b_\textrm{e} + rb_\textrm{o}) = c_\textrm{e} + r(c_\textrm{o} + d_\textrm{o}) + r^2d_\textrm{e}/X\\ (a_\textrm{e} + ra_\textrm{o})(b_\textrm{e} - rb_\textrm{o}) = c_\textrm{e} + r(c_\textrm{o} - d_\textrm{o}) - r^2d_\textrm{e}/X\\ \end{array} \right.\textrm{ on }H'\\ \iff &\quad (6)\left\{\begin{array}{ll} a'b' = c' + d'\\ a'\bar b' = c' - d'\\ \end{array} \right.\textrm{ on }H'\\ \end{align*} $(1) \iff (2)$ follows from the definition of even-odd parts $(2) \iff (3)$ follows from basic arithmetic (expanding) $(3) \iff (4)$ follows from basic arithmetic (rearranging) $(4) \iff (5)$ follows from the Schwartz-Zippel lemma $(5) \iff (6)$ follows from the definition of $a', b', c', d'$