fflonk

• fflonk central idea: reduce opening many polys to one using the FFT ideneity
• Cheaply opening a poly at $d$ points

Reduce opening many polys at $s$ to opening one poly at many points, then can use BDFG.

fflonk central idea: reduce opening many polys to one using the FFT ideneity

polys ${\mathbf{f}}_0,{\mathbf{f}}_1,a={\mathbf{f}}_0(s),b={\mathbf{f}}_1(s)$
First attempt: Only open the sum - $\mathbf{F}(\mathbf{X}):={\mathbf{f}}_0(\mathbf{X})+{\mathbf{f}}_1(\mathbf{X})$. Prove that $\mathbf{F}(\mathbf{s})=\mathbf{c}=\mathbf{a}+\mathbf{b}$. Problem: Doesn't constrain $a,b$ individually - for any $a^{\prime },(a^{\prime },c-a^{\prime })$ will also verify Solution: Use "FFT equation in reverse direction": $$\mathbf{F}(\mathbf{X})={\mathbf{f}}_0({\mathbf{X}}^2)+\mathbf{X}{\mathbf{f}}_1({\mathbf{X}}^2)$$
To commit to ${\mathbf{f}}_0,{\mathbf{f}}_1$ send $C_{\mathbf{F}}$

Assume $s=t^2$. To open ${\mathbf{f}}_0(\mathbf{s}),{\mathbf{f}}_1(\mathbf{s})$ open $\mathbf{F}$ at $\{t,-t\}$: $${\mathbf{b}}_0:=\mathbf{F}(\mathbf{t})={\mathbf{f}}_0(\mathbf{s})+\mathbf{t}{\mathbf{f}}_1(\mathbf{s})=\mathbf{a}+\mathbf{tb}$$ $${\mathbf{b}}_1:=\mathbf{F}(-\mathbf{t})={\mathbf{f}}_0(\mathbf{s})-\mathbf{t}{\mathbf{f}}_1(\mathbf{s})=\mathbf{a}-\mathbf{tb}$$ i.e. $(b_0,b_1)$ give two independent constraints on $(a,b)$!

• Similar construction can open $k$ polys at any $s=t^k$
• Important: poly-iop based snarks work fine with a PCS that only open $k$'th powers.

Cheaply opening a poly at $d$ points

Notation: $[x{]}_1=x\cdot G_1$ Given poly $\mathbf{f}$ with commitment $C$, $s_0,\dots ,s_{k-1}\in \mathbb{F}$, suppose $z_i=\mathbf{f}({\mathbf{s}}_{\mathbf{i}})$ for $i<k$.

• Define poly $r$ of degree $<k$ with $r(s_i)=z_i$ for $i<k$.
• Define $\mathbf{Z}(\mathbf{X})={\prod }_{\mathbf{i}<\mathbf{k}}(\mathbf{X}-{\mathbf{s}}_{\mathbf{i}})$. Then we have $Z|(f-r)$
• Let $\mathbf{h}(\mathbf{X}):=\frac{(\mathbf{f}(\mathbf{X})-\mathbf{r}(\mathbf{X}))}{\mathbf{Z}(\mathbf{X})}$.Prover sends $\pi =[\mathbf{h}(\mathbf{x}){]}_1$.
• From [KZG]: Verifier can now check
  $$e(C-[r(x){]}_1,G_2)\stackrel{?}{=}e(\pi ,[Z(x){]}_2)$$
  This requires $k$ $G_1$ and $G_2$ verifier scalar muls!

In[BDFG] we trade these scalar mults for an extra group element in the proof:

• Verifier chooses random $\alpha \in \mathbb{F}$ and sends to prover.
• Define the polynomial $$\mathbf{L}(\mathbf{X}):=\mathbf{f}(\mathbf{x})-\mathbf{r}(\alpha )-\mathbf{Z}(\alpha )\mathbf{h}(\mathbf{X})$$
• If evals are correct, $L(X)$ should be zero at $\alpha$
• Verifer can compute $C_{\mathbf{L}}$ with only two scalar muls: $$C_{\mathbf{L}}=C-[r(\alpha ){]}_1-Z(\alpha )\pi$$
• Prover and verifier can now use KZG to check $\mathbf{L}(\alpha )=0$