owned this note
owned this note
Published
Linked with GitHub
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'$