Abstract
基于Caulk和Caulk+的研究继续改进
本文的方案需要$O(N\log ^2 N)$的预处理步骤，并将Prover Time进一步优化至拟线性阶$O(m\log ^2 m)$
1 Introduction
查找表是最近几年的zk-SNARK研究热点之一，简单来说就是构造一个协议，证明一个承诺多项式$\phi(X)$包含在大小为$N$的查找表$T$中，该查找表包含了预定义的所有的（或者大部分的）合法值
若查找表对应的运算不包含域上的有效低度算术运算时，查找表可以显著节省协议的开销
最早的方案应该是基于plook构建的plookup，在多项式IOP中构造了一个查找表的解决方案，Prover复杂度与$m$和$N$均呈拟线性关系
plookup的研究还引出了一个问题：对表$T$执行预处理步骤后，是否可以使得对$N$的依赖变为亚线性的，Caulk利用双线性配对解决了这个问题，将复杂度优化到了$O(m^2+m\log N)$，Caulk+进一步优化到了$O(m^2)$
但是Caulk和Caulk+还是包含一个与$m$相关的平方项，如果用这两个算法处理具有许多查找门的电路来说非常不友好，本文提出了flookup方案来解决这个问题，方案的复杂度与$m$呈拟线性关系，且在预处理步骤后与表的大小$N$无关
image-20221211163702-qznhhjt.png
1.1 Usefulness of the result
从宏观角度对比一下flookup和plookup算法，plookup算法的Prover Time为$O(N\log N)$，flookup的Prover Time为$O(m\cdot \log^2 m)$，且$O$的常数因子很小，因此flookup非常适用于$m\ll N/\log N$的情况
不过flookup也有缺点，与Caulk和Caulk+相同，flookup的验证需要一次由Prover定义的配对，这导致递归聚合证明不那么平滑
此外，flookup不具备plookup和Caulk中优良的线性性质，线性性质可以将多个查表聚合成一个，flookup这一点做的不这么好，相对而言，flookup在查找单表的时候，尤其是范围检查的情况下具有比较好的性能（比如对表$T=\{0,...,2^t-1\}$进行范围检查）
flookup更好的应用场景是一些范围较大的SNARK unfriendly操作，比如各种按位与，按位异或，移位，循环移位等等
比如SHA-256中有一个32bit的位操作，可以定义一个映射$f$，并构造所有$2^{32}$种可能的表$A+2^{32}\cdot f(A)$，比如输入和输出分别为$w_1,w_2$，满足$f(w_1)=w_2$，可以利用flookup检查$w_1+2^{32}\cdot w_2$是否在这个表中来完成验证
2 Terminology and Conventions
本文用到的符号和记法与之前几篇相同
本文的协议需要用到通用可更新的单项式SRS，形式为$\{[x^i]_1\}_{a\leq i\leq b},\{[x^i]_2\}_{c\leq i\leq d}$，其中$x\in \mathbb F$为随机选择的元素，$a,b,c,d$为以$poly(\lambda)$为上界的整数
其他用到的密码学原语和组件如下
- 密码学假设：q-DLOG
- 代数群模型（AGM）
- KZG多项式承诺及其变体（d-PCS）
3 Bi-linear polynomial IOPs
介绍一个新的概念，双线性多项式IOP
对于正整数$d\in \mathbb F$，d-BLIOP为一个P，V与理想可信方$I$的协议，如下
- 协议包含两个预计算的多项式集合$P_1,P_2\sub \mathbb F_{<d}[X]$
- Prover发送给$I$的多项式为$(f,i)$，其中$f\in \mathbb F_{<d}[X],i=1,2$，若P发送的多项式不符合这个形式，则协议终止
- P和V都是随机掷币
- 对于$i=1,2$，记$F_i$表示P发送给$I$的多项式集合，记$A_i=F_i\cup P_i$
V可以向$I$发起连个请求
- 求值查询$(f,x)$：其中$f\in A_1,x\in \mathbb F$，$I$返回$f(x)$
- 双线性恒等式查询：查询$\sum_{j\in [k] }c_j\cdot f_j(X)\cdot h_j(X)\equiv 0$是否成立，其中$k$为随机正整数，$c_j\in \mathbb F,f_j\in A_1,h_j\in A_2$，对于每个恒等式查询，$I$返回true或false
协议结束后，V根据查询结果输出接受或拒绝
根据上述协议定义完整性和知识合理性，具体可以看原文的Def 3.2
上述只是定义了双线性多项式IOP，但并未提供抗代数敌手的能力，原文的3.1节定义一些术语来实现这一点，这里介绍一些记法
- $\mathcal P$：表示多项式协议，输入为$(x,w)$
- $D_1(\mathcal P,x,w)=\sum_{f\in F_1}(def(f)+1)$
- $D_2(\mathcal P,x,w)$：表示为所有的$f\in F_2$计算$[f]_2$所需要的群$\mathbb G_2$上的标量乘法的次数
- $\mathcal O=([f]_1,z,f(z);f)$
- $E(\mathcal P,x,w)$表示V发起的双线性查询中被求和数的总数（total number of summands in all bi-linear queries）
相关概念及其证明可以看原文，这里略过
3.2节介绍了一些描述BLIOP和PIOP的惯例，如下
- 若d-BLIOP不包含双线性检查（$A_2$为空），此时称为d-PIOP，并将P发送的消息$(f,1)$简写为$f$
- 若V请求检查恒等式$P(f_1(X),...,f_k(X)),f_i\in A_1$，此时表示V选择随机值$\alpha\in \mathbb F$并请求$f_1(\alpha),...,f_k(\alpha)$，计算$z=P(f_1(\alpha),...,f_k(\alpha))$，若$z\neq 0$则V拒绝
在分析d-BLIOP的合理性（知识合理性）时，可以假设$g(X)=P(f_1(X),...,f_k(X))$为非零多项式 - 若V在$H\sub \mathbb F$上请求$P(f_1(X),...,f_k(X)),f_i\in A_1$，，此时表示P发送一个商多项式$T(X)=P(f_1(X),...,f_k(X))/Z_H(X)$，V检查等式$P(f_1(X),...,f_k(X))=Z_H(X)\cdot T(X)$
4 Protocol for subtable extraction
Caulk+采用分数分解来从$Z_T$中抽取子集$I\sub T$对应的消失多项式$Z_I$，$[PK22]$中的表$T$同时还是一个乘法子群，因为$T$代表表值的索引，而非表值本身，本文通过计算大小为$|T|-1$的所有子表的承诺来完成协议，这确保了当$T$是任意集合时，可以确保预处理过程的复杂度为拟线性的而非平方阶
这里先介绍一个引理
Lemma 4.1：给定大小为$N$的集合$T\sub \mathbb F$和集合$\{[x^i]_2\}_{i\in \{0,...,N-1\}}$，存在一个算法计算集合元素$\mathcal T$，需要$O(N\cdot \log ^2N)$次$\mathbb G_2$中标量乘法和域$\mathbb F$上操作
$$ \mathcal T=\big \{ [Z_{T\backslash\{i\}}(x)] _2 \big \}_{i\in T} $$
证明如下，看一下如何在$O(N\cdot \log ^2N)$内完成计算
Proof：用下面这个表示多项式 $Z_{T\backslash \{i\}}(X)$的系数向量
然后让所有的系数向量组成一个矩阵
我们的目标是计算$\mathcal T={Z_{T\backslash *}}\times SRS$
$$ SRS=\Big [ [1]_2,[x]_2,...,[x^{N-2}] _2,[x^{N-1}]_2 \Big ]^T $$
这里介绍一个小技巧，对于两个度为$N/2$的多项式$a(X),b(X)$，若有多项式$c(X)=a(X)\cdot b(X)$，则可以用矩阵与向量的积表示这个乘法，记三个多项式的系数向量分别为$\bar a,\bar b,\bar c$，此时可以将这个多项式乘法写成下面这个向量与矩阵的乘积
记后面那个矩阵为$A_b$，该矩阵共有$N/2+1$行，$N+1$列
这个矩阵$A_b$有个学名，叫做托普利兹矩阵，又称为长对角矩阵/T型阵/次对称阵，特点是主对角线及与之平行的线上的元素均相等，矩阵中各元素关于次对角线对称
此时多项式乘法$c(X)=a(X)\cdot b(X)$可以简记为$\bar c=\bar a\times A_b$
回到原来的计算，我们将集合$T$拆分为前半部分$T_1=\{v_1,v_2,...,v_{N/2}\}$和后半部分$T_2=\{v_{N/2+1},v_{N/2+2},...,v_{N}\}$，此时我们有
接下来看一下计算$\mathcal T$的算法
- 计算$Z_T(X)$的系数及其子积树（tree of subproducts），开销为$O(N\log ^2N)$
- 将$T$拆分为两个部分$T_1,T_2$，消失多项式分别为$Z_{T_2}(X),Z_{T_1}(X)$
- 计算托普利兹矩阵向量$a_1=A_{Z_{T_1}}\times SRS,a_2=A_{Z_{T_2}}\times SRS$，开销为$O(N\log N)$
- 递归计算$b_1=Z_{T_1\backslash*}\times a_2,b_2=Z_{T_2\backslash*}\times a_1$，跳转至步骤2
- 输出$b_1,b_2$的串联
这里细说一下步骤1的计算过程，用到的是vzGG$[2]$这篇资料中的算法10.3
- 将$T$拆分为两个部分$T_1,T_2$
- 分别令$T=T_1,T=T_2$，递归步骤1并计算$Z_{T_1},Z_{T_2}$
- 利用FFT算法，聚合得到$Z_{T_1},Z_{T_2}$，开销为$O(N\log N)$
引理证毕
接下来继续描述子表提取协议$IsVanishingSubtable_T(g(X))$
- 预处理多项式：$P_1,P_2$，其中$P_1=\{Z_T\}$，对于所有的$i\in T$，在$P_2$中插入多项式$Z_{T\backslash\{i\}}$
- 输入：$g(X)\in \mathbb F_{<d}[X]$
协议分为两步
- P向$I$发送$(Z_{T\backslash S},2)$
- V发起一次双线性查询，验证等式$g\cdot Z_{T\backslash S}\equiv Z_T$，当且仅当等式成立时接受P
这里有个引理
Lemma 4.2：$IsVanishingSubtable_T$是关于语言$L=\{g(X)\in \mathbb F_{<d}[X]|g(X)=Z_S(X),S\sube T\}$的d-BLIOP，输入为$g=Z_S$，Prover复杂度为$O(m\log ^2m)$次域运算，$O(m)$次$\mathbb G_1,\mathbb G_2$上的标量乘法（$m=|S|$），预处理需要$O(N\log^2N)$次$\mathbb G_2$标量乘法和域运算（$N=|T|$）
这个引理证明可以看原文
5 A PIOP for lookups when given the table in vanishing form
上一节介绍了一种抽取子表消失多项式的方式，可以用grand-product论证来将子表转换为拉氏多项式的形式，然后利用一个查找协议（比如plookup）来证明表具有预期的格式
不过本文给出另一种方案，通过直接同时处理表的消失多项式，可以优化plookup的效率，当witness和表的大小都为$m$时，本文的方案大约需要$3m$次群$\mathbb G_1$的标量乘法（plookup需要$5m$次）
在介绍方案之前，先介绍一个概念，非正规有理拉格朗日函数（Unnormalized rational Lagrange functions）
分析的主要内容是有理拉格朗日函数在相关集合之外的点的定义，简单来说这个过程可以让我们检查集合中的包含情况
对于一个集合$T\sub \mathbb F$，令$v\in \mathbb F$，记一个有理函数如下
$$ \Gamma^T_v(X)=\frac{Z_T(X)}{X-v} $$
不难看出这个函数也是一个多项式（定义域除了$v\in T$）
接下来介绍一个引理，这个引理允许我们在区分多项式和有理函数时减少查找的次数
Lemma 5.1：对于任意向量$v,a\in \mathbb F^m$，任意的集合$T\sub \mathbb F$，定义一个有理函数$R(X)=\sum_{j\in [m]}a_j\cdot \Gamma^T_{v_j}(X)$
- 若对于所有的$j\in [m]$，都有$v_j\in T$，则$R(X)\in \mathbb F[X]$
- 令$S\sub [m]$表示所有的$j\in [m],v_j\notin T$构成的子集，假设$S\neq \emptyset$，若$\sum_{j\in S}a_j\neq 0$，则$R(X)\notin \mathbb F[X]$
具体而言，当$\forall j\in [m],a_j=1$，若$|char(\mathbb F)|>m$，则$R(X)\notin \mathbb F[X]$
接下来证明一下
第一条显然成立，因为多个多项式相加的结果显然也是多项式，这里用反证法证明第二条
假设集合$S$非空，通过证明有理函数无法被消去来证明第二条，假设向量$a_j\in \mathbb F^m$，满足$\sum_{j\in S}a_j\neq 0$，我们可以将$R(X)$拆分成两个部分$R(X)=R_1(X)+R_2(X)$
$$ \begin{aligned} R_1(X)&=\sum_{j\in [m]\backslash S}a_j\cdot \Gamma^T_{v_j}(X)\\ R_2(X)&=\sum_{j\in S}a_j\cdot \Gamma^T_{v_j}(X) \end{aligned} $$
不难看出$R_1$是多项式，而且当且仅当$R_2$是多项式时，$R$才是多项式
现在假设有$R_2\in \mathbb F[X]$，则有下列等式成立
$$ Z_T(X)\sum_{j\in S}\frac{a_j}{X-v_j}=R_2(X) \tag 1 $$
令两个多项式$Q,Q'$如下
$$ \begin{aligned} Q(X)&=\prod_{j\in S}(X-v_j)\\ Q'(X)&=\sum_{j\in S}a_j \prod_{i\in S\backslash\{j\}}(X-v_i) \end{aligned} $$
式1两侧同时乘$\prod_{j\in S}(X-v_j)$，得到
$$ Z_T(X)\cdot Q'(X)=R_2(X)\cdot Q(X) \tag 2 $$
排除$R_2(X)\equiv0$的情况（如若$R_2(X)\equiv0$，由于$Z_T(X)\neq 0$，则必然有$Q'(X)\equiv 0$，显然$Q'\not\equiv 0$，矛盾），此时$Q'$中$X^{|S|-1}$的系数为$\sum_{j\in S}a_j$（前面假设了这个求和结果非零）
由于$R_2(X)\not\equiv0$，且$Q$没有整除$Z_T$的因子，若式2等号两侧相等，则必然有$Q|Q'$，但是$deg(Q)=|S|,deg(Q')<|S|$，因此$Q\nmid Q'$，因此假设$R_2\in \mathbb F[X]$不成立，故$R_2\notin \mathbb F[X]$
综上，得到$R\notin \mathbb F[X]$，证毕
利用上述引理，接下来看一下如何构造本文的核心协议
令$\mathbb H=\{g,g^2,...,g^m=1\}\sub \mathbb F$，$g$为生成元，给定多项式$\phi(X)\in \mathbb F_{<d}[X]$，给定集合$T\sub \mathbb F$，定义一个多项式如下
$$ R_{T,\phi}(X)=\sum_{v\in \mathbb H}\Gamma^T_{\phi(v)}(X) $$
协议的目的是对该多项式$R_{T,\phi}(X)$承诺并证明承诺正确，这个过程表明了两件事
- $R_{T,\phi}$是多项式
- $\phi|_\mathbb H\sub T$
为了证明承诺对应于$R_{T,\phi}$，通过在一个随机点$\beta \in \mathbb F$求值$R_{T,\phi}(\beta)$的方式验证，这里用到了Justin Drake提出的grand sum argument的方式验证（这个方法算是$[GWC19]$提出的grand product argument的一种变体）
Justin Drake - grand sum argument：Youtube - Link，链接视频无法播放，尝试找一下其他的参考文献
记$\mathbb H$的拉氏基多项式为$\{L_i(X)\}_{i\in [m]}$，对于给定的子集$\mathbb H,T\sub \mathbb F$，构造下列协议$IsInVanishing_{\mathbb H,T}(\phi)$
- 预处理多项式$P_1=\{Z_T\}$
- 输入：多项式$\phi\in \mathbb F_{<d}[X]$
协议如下
- P发送多项式$g(X)=R_{T,\phi}(X)$
- V发送随机挑战$\beta \in \mathbb F$，同时查询值$z=g(\beta)$
- P计算并发送多项式$Z(X)\in \mathbb F_{<m}[X]$，这里$\forall i\in [m],Z(\omega^i)=\sum^i_{j=1}\Gamma^T_{\phi(g^i)}(\beta)$
- V查询$Z_T(\beta)$
- V在$\mathbb H$上检查下列三个等式
$$ \begin{aligned} (a) \ &L_1(X)\cdot\big (Z(X)\cdot (\beta-\phi(X))-Z_T(\beta)\big )=0\\ (b) \ &(X-g)\cdot \big( Z(X)-Z(X/g)\cdot \frac{Z_T(\beta)}{\beta-\phi(X)} \big)=0\\ (c) \ &L_m(X)\cdot (Z(X)-z)=0 \end{aligned} $$
这里给一个定理
Thm 5.2：上述协议是关于语言$L=\{\phi(X)\in \mathbb F_{<d}[X] \ | \ \phi|_\mathbb H\sub T\}$的d-PIOP，其中$deg(\phi),|T|=O(m)$，Prover Time为$O(m\cdot \log^2 m)$，协议在预处理阶段需要取决于表$T$的$O(m\cdot\log^2m)$次$\mathbb G_1$标量乘法，此后Prover只需要$O(m\cdot \log m)$次域运算和$O(m)$次$\mathbb G_1$标量乘法
证明如下
假设$\phi\notin L$，令事件$E$表示$g(\beta)=R_{T,\phi}(\beta)$，若有$\phi(X)\notin L$，则根据引理5.1，有$R_{T,\phi(X)}\notin \mathbb F[X]$，由于$g\in \mathbb F_{<d}[X]$，则有事件$E$发生的概率为可忽略
注意到上述协议中的步骤五的三个验证等式
- 式a表明$Z(g)=\Gamma^T_{\phi(g)}(\beta)$
- 式b表明，对于所有的$i\in \{2,...,m\}$，有$Z(g^i)=Z(g^{i-1})+\Gamma^T_{\phi(g^i)}(\beta)$，联合式a和式b，可以得到$Z(g^m)=\sum_{i\in [m]}\Gamma^T_{\phi(g^i)}(\beta)=R_{T_\phi}(\beta)$
- 式c表明$Z(g^m)=z=g(\beta)$
若三个等式均通过验证则表明$g(\beta)=R_{T,\phi}(\beta)$，根据假设，若有$\phi(X)\notin L$，则此时V接受的概率为可忽略
语言归属部分证明完毕，接下来看复杂度分析部分
在Prover Time中，最复杂的部分是计算$R_{T,\phi}(\beta)$，可以通过系数插值将开销降低至$O(m\cdot \log^2m)$，Prover首先在$O(m\cdot \log m)$内计算$\{a_v\}_{v\in T}$，其中$a_v$由$x\in \mathbb H$定义，满足$\phi(x)=v$，此时有
$$ R_{T,\phi}(X)=\sum_{v\in T}a_v\cdot \Gamma^T_v(X) $$
令$\{\tau_v(X)\}_{v\in T}$表示$T$的拉氏基多项式，对于所有的$v\in T$，都有$\Gamma^T_v(X)=c_v\cdot \tau_v(X)$，其中系数项$c_v=\prod_{v\neq i \in T}(v-i)$，此时有
$$ R_{T,\phi}(X)=\sum_{v\in T}a_v\cdot c_v\cdot \tau_v(X) $$
此时对于$\forall v\in T$，有$R_{T,\phi}(v)=a_v\cdot c_v$，因此如果我们有$\{a_v\cdot c_v\}_{v\in T}$，我们可以利用插值法得到$R_{T,\phi}(X)$的系数
注意到$\{c_v\}_{v\in T}$是$Z_T(X)$的导数$Z_T'(X)$在$T$处的求值，因此可以在有限的时间内计算
观察给定的表$T$，我们可以利用引理4.1预计算$S_v=[\Gamma^T_v(x)]_1$，并利用这些值计算$\sum_{v\in T}a_v\cdot S_v$的KZG承诺$[R_{T,\phi}(x)]_1$（需要$O(m)$次群$\mathbb G_1$标量乘法和$O(m\cdot \log m)$次域运算）
此外，预计算阶段还需要计算$\{c_v\}_{v\in T}$，给定这些值，可以计算$R_{T,\phi}$的KZG承诺在$r\in \mathbb F\backslash T$处的揭示$z=R_{T,\phi}(r)$
$$ \Big [\frac{R_{T,\phi}(x)-z}{x-r}\Big ]_1=\sum_{v\in T}\frac{a_v-z/c_v}{v-r}\cdot S_v $$
证毕
6 Putting it all together
最后就是把上面这些缝在一起，构成最后的协议
- 预处理多项式：$P_1=\{Z_T\}$
- 输入：多项式$\phi\in \mathbb F_{<d}[X]$
协议如下
- P计算集合$I\sube T$，满足$I=\phi|\mathbb H$
- P计算并向V发送$Z_I$
- P和V运行协议$IsVanishingSubtable_T(Z_I)$
- P和V运行协议$IsVanishingSubtable_{\mathbb H,Z_I}(\phi)$
这里有个定理其实就是将上面的引理4.2和定理5.2结合在一起，可以看原文
References
$[1]$ Flookup: Fractional decomposition-based lookups in quasi-linear time independent of table size
$[2]$ J. von zur Gathen and J. Gerhard. Fast polynomial evaluation and interpolation. Modern Computer Algebra, chapter 10, pages 295–310.