Abstract

介绍一种基于承诺多项式的查表协议，需要$O(N\log N)$的预处理步骤，Prover开销为要$O(N\log N)$

本文的构造依赖于同态表承诺（目的是简化向量查找），不过区别于之前的工作，本文无需Prover在$\mathbb G_2$点上定义的配对，从而可以在递归聚合中有更好的表现

1 Introduction

查找是现代zkSNARK研究方向之一，查找协议旨在设计一个协议来证明一个承诺多项式$f$的值包含在一个大小为$n$的包含合法预定义值的表$T$中

之前诸如Caulk/Caulk+、baloo、flookup等方案均要求两个源群之间的配对，且配对参数在协议中不是固定的，因此这些方案难以用于重复聚合多个证明

因此本文提出cq协议，主要有下列三个优化

  1. 将Prover的域运算开销降低至$O(n\log n)$，且与baloo方案相比具有更小的常数和证明大小
  2. 基于Caulk/Caulk+、baloo类似的同态表承诺，实现更方便的向量查找
  3. Verifier采用协议定义的$\mathbb G_2$参数来完成配对，可以实现更边界的聚合性

下表给出了本文方案与之前的一些查表方案的效率对比，其中$n$表示witness大小，$N$表示查找表大小，Aggrega table表示Prover定义的配对参数均来自于$\mathbb G_1$

查表协议的优化方向之一是降低Prover的计算开销，将Prover的开销降低至表大小$N$的亚线性阶，或者flookup之类的方案可以做到Prover的开销与表的大小无关

回顾一下之前的博客介绍的Caulk/Caulk+，此类查找协议主要是证明一个多项式$f$的值包含在一个大小为$N$的查找表中，Caulk的主要思想是，预计算过程中对一个特定的商多项式进行承诺，后续协议中只需要利用这个承诺值来完成查表的验证

Caulk-like的方法首次实将效率优化至表的大小的亚线性阶，但是问题在于：提取$f$中子表的限制与从原始表中抽取任意集合的限制相当，因此之前的工作均利用了任意集合的多项式插值与求值的方式来构造协议，此类方式的效率渐进性为$O(n\log ^2n)$

本文的cq协议与之前协议的关键区别在于：本文利用了商承诺简洁计算的思想，不直接提取子表，而是在原始表中更有效地执行查找，具体而言，本文使用了$[Eag22,Hab22]$的基于对数导数（logarithmic derivative based）的查找

对于给定的多项式$A,B$的承诺，$[Hab22]$利用和校验协议，在一个随机点$\beta$上对该等式进行检查

计算多项式承诺不是问题，问题在于Prover如何让Verifier确信$A$具有正确的形式，这一检查等价于：Prover让Verifier确信，存在某一商多项式$Q_A(X)$，满足下列等式

$$ A(X)\cdot(T(X)+\beta)-m(X)=Q_A(X)\cdot Z_{\mathbb V}(X) $$

上述等式也等价于下列等式，其中$R(X)\in \mathbb F_{<N}[X]$

$$ A(X)\cdot(T(X)+\beta)=Q_A(X)\cdot Z_{\mathbb V}(X)+R(X) $$

这一等式也是本文的核心概念之一：缓存商（cached quotients），注意到计算$Q_A$可能会很久，可以通过计算对应的承诺$[Q_A]_1$来代替，只需要$O(n)$次运算

本文的方式是，对于$\mathbb V$中的每一个拉氏基多项式$L_i(X)$，计算其与$T(X)$相乘时的上承诺，比如对于余项多项式$R_i(X)\in \mathbb F_{<N}(X)$，可以对$Q_i(X)$进行承诺，对应的等式如下

$$ L_i(X)\cdot T(X)=Q_i(X)\cdot Z_{\mathbb V}(X)+R_i(X) $$

给定承诺值$[Q_i(X)]_1$，计算$[Q_A(X)]_1$所需的操作次数为$O(n)$，而且根据Feist和Khovratovich的方案$[2]$，所有的$[Q_i]_1$均可以在$O(N\log N)$内计算

2 Preliminaries

  • $\mathbb F$：素数域
  • $\mathbb F_{<d}[X]$：阶小于$d$的多项式
  • $\lambda$：安全参数
  • $(\mathbb F,\mathbb G_1,\mathbb G_2,\mathbb G_t,g_1,g_2,g_t)$：配对群
  • $[x]_1=x\cdot g_1$：$g_2$同理
  • $[n]$：表示正整数集合$\{1,\dots,n \}$
  • $srs$：结构化参考串，本文的协议需要访问SRS，SRS的结构为$\{[x^i]_1\}_{a\leq i\leq b},\{[x^i]_2\}_{c\leq i\leq d},x\in \mathbb F$，$srs$会作为部分算法的隐式输入
  • $\mathbb V=\{1,g,g^2,\dots,g^{N-1}\}$：表示大小为$N$的乘法子群（$\mathbb V\sub \mathbb F$），且$N$为2的幂
  • $L_i(X)\in \mathbb F_{<N}[X]$：表示$\mathbb V$的拉氏基多项式，有$(L_i)_i=1,(L_i)_j=0,i\neq j\in [N]$
  • $P_i=P(g^i)$：表示多项式$P$在$g^i$处的取值
  • n-sparse：若多项式$A(X)\in \mathbb F_{<N}[X]$有至多$n$个点求值不为零，则称该多项式为$n$稀疏的
  • $supp(A)=\{i\in [N]|A_i\neq 0\}$：表示多项式$A(X)$求值不为零的点-值对$(i,A_i)$构成的集合
  • Q-DLOG：两个源群之间的假设，对于整数$Q$，给定$[1]_i,[x]_i\dots,[x^Q]_i,i\in \{1,2\}$，敌手输出$x$的概率可忽略

本文的和校验协议基于下面这个引理

Lemma 1：记$H\in \mathbb F$为一乘法子群，大小为$t$，对于$f\in \mathbb F_{<t}[X]$，有等式$\sum_{a\in H}f(a)=t\cdot f(0)$成立

2.1 The algebraic group model

本文的代数群模型和和之前介绍的一样，当敌手$\mathcal A$输出一个群元素$A\in \mathbb G_i,i\in\{1,2\}$，其同时输出一个向量$v$，满足$A=<v,srs_i>$，本文采用阶为$Q$的SRS，记$f_{i,j}$表示$srs_i$的第$j$个元素对应的多项式

记敌手输出的域元素向量$a,b$，分别编码两个源群中的元素，真实配对检查（real pairing check）为检查等式$(a\cdot T_1)\cdot(T_2\cdot b)=0$，其中$T_1,T_2$为域上的两个矩阵，该检查可以用配对来完成

对于给定的真实配对检查，敌手和协议执行过程中输出的元素，定义理想检查（ideal check）如下：由于敌手输出一个群元素$[a_j]_i$时，还会输出一个向量$v$，满足$a_j=\sum v_l\cdot f_{i,l}(x)=R_{i,j}(x)$，其中$R_{i,j}(X)=\sum v_l\cdot f_{i,l}(X)$

对于$i\in \{1,2\}$，多项式$R_i=(R_{i,j})_j$，对应的理想检查为检查多项式等式$(R_1\cdot T_1)\cdot (T_2\cdot R_2)=0$​

这里介绍一个相关的引理，该引理基于Q-DLOG（引理证明见$[GWC19]$）

Lemma 2：若Q-DLOG假设在$(\mathbb G_1,\mathbb G_2)$上成立，对于阶为$Q$的SRS的协议，任意代数敌手$\mathcal A$可以通过真实配对检查的概率仅比理想检查的概率高一个可忽略的常数

然后引入$[Hab22]$中的一个引理

Lemma 3：当且仅当存在$m\in \mathbb F^m$，使得下列等式成立时，有$f|_{\mathbb H}\sub t$

$$ \sum_{i\in[N]}\frac{m_i}{X+t_i}=\sum_{i\in[n]}\frac{1}{X+f_i} $$

3 Cached quotients

本节主要介绍一种计算商多项式承诺的方法，和前面介绍的一样，该承诺从预处理多项式的乘积导出（相关结果基于$[2]$）

首先介绍一个引理

Lemma 4：对于大小为$N$的子集$\mathbb V$和多项式$T\in \mathbb F_{<N}[X]$，存在一个需要$O(N\log N)$次群运算的算法，给定$\mathbb G_1$上的SRS，用于计算$q_i=[Q_i(x)]_1$，其中$Q_i(X)$满足等式$L_i(X)\cdot T(X)=T_i\cdot L_i(X)+Z_{\mathbb V}(X)\cdot Q_i(X)$

可以证明一下这个引理：回顾一下拉氏插值多项式的形式

$$ L_i(X)=\frac{Z_{\mathbb V}(X)}{Z'_{\mathbb V}(g^i)(X-g^i)} $$

将引理4中的等式移项后，得到商$Q_i(X)$如下

$$ Q_i(X)=\frac{T(X)-T_i}{Z'_{\mathbb V}(g^i)(X-g^i)}=Z'_{\mathbb V}(g^i)^{-1}\cdot K_i(X) $$

这里记$K_i(X)=\frac{T(X)-T_i}{X-g^i}$，不难看出，多项式$K_i$对应的群元素$\{[K_i(x)]_1\}_{i\in [N]}$表示$T(X)$的KZG承诺在集合$\mathbb V$上的揭示，因此根据FK的方案$[2]$，可以在$O(N\log N)$次群运算中计算所有这些KZG承诺的证明$[K_i(x)]_1$

然后是计算$Z'_{\mathbb V}(g^i)^{-1}$，注意到$Z_{\mathbb V}(X)=X^N-1$，$X^{N-2}$与$X$互为逆元，因此有

$$ Z'_{\mathbb V}(X)^{-1}=(N\cdot X^{N-1})^{-1}\equiv X/N \mod {Z_{\mathbb V}(X)} $$

然后将两个多项式相乘就可以得到$Q_i(X)$了（这里相当于用$K_i$与$g^i/n$相乘）

上述过程中，Prover计算多项式$T$需要$O(N\log N)$次域运算，$T_i$的KZG承诺需要$O(N\log N)$次群运算，最后两个多显示相乘需要$O(n)$次群运算，因此总的域运算和群运算复杂度为$O(N\log N)$，引理证毕

基于上述引理，给出本文的一个定理

Thm 1：对于给定的两个整数$0\leq n\leq N$（均为2的幂），给定多项式$T\in \mathbb F_{<N}[X]$和子群$\mathbb V$，记$srs=\{[x^i]_1\}_{i\in[N-1]},x\in \mathbb F$，对于给定的$n$-稀疏的多项式$A\in \mathbb F_{<N}[X]$及其稀疏表达，算法在$O(n)$次域运算和$n$次群运算中可以计算$cm_1=[Q(x)]_1,cm_2=[R(x)]_1$，满足下列等式

$$ A(X)\cdot T(X)=Q(X)\cdot Z_{\mathbb V}(X)+R(X) $$

根据引理4，商多项式承诺$[Q_i(X)]_1$已经在预处理步骤中计算好，且每个商多项式均满足等式$L_i(X)\cdot T(X)=T_i\cdot L_i(X)+Z_{\mathbb V}(X)\cdot Q_i(X)$

由于多项式$A$为$n$-稀疏的，因此可以将多项式表示为$\mathbb V$中拉氏基多项式的形式，如下

$$ A(X)=\sum_{i\in supp(A)}A_i\cdot L_i(X) \tag 1 $$

将式1两侧同时乘多项式$T$，可以得到

$$ \begin{aligned} A(X)\cdot T(X)&=\sum_{i\in supp(A)}A_i\cdot L_i(X)\cdot T(X)\\ &=\sum_{i\in supp(A)}A_i\cdot T_i\cdot L_i(X)+A_i\cdot Z_{\mathbb V}(X)\cdot Q_i(X)\\ &= \sum_{i\in supp(A)}A_i\cdot T_i\cdot L_i(X)+Z_{\mathbb V}(X) \cdot \sum_{i\in supp(A)}A_i\cdot Q_i(X) \end{aligned} $$

注意到

$$ \begin{aligned} Q(X)&=\sum_{i\in supp(A)}A_i\cdot Q_i(X)\\ R(X)&=\sum_{i\in supp(A)}A_i\cdot T_i\cdot L_i(X) \end{aligned} $$

因此我们可以得到对应的承诺值$cm_1,cm_2$如下

$$ \begin{aligned} cm_1 &= [Q(x)]_1=\sum_{i\in supp(A)}A_i\cdot [Q_i(X)]_1\\ cm_2 &= [R(x)]_1=\sum_{i\in supp(A)}A_i\cdot T_i\cdot [L_i(X)]_1 \end{aligned} $$

定理证毕

4 cq - our main protocol

本节介绍本文的cq协议，本文将查找协议记为$P=(gen,IsInTable)$

  • $gen(N,t)$：给定整数$N,t\in \mathbb F^N$，算法输出由$\mathbb G_1,\mathbb G_2$元素组成的$srs$
  • $IsInTable(cm,t,srs,\mathbb H;f)$：Prover和Verifier之间的公共掷币交互式协议，其中Prover的秘密输入为多项式$f\in \mathbb F_{<n}[X]$，双方的公共输入为$t,cm$，协议满足完备性和代数群模型中的知识合理性

注意：协议不具备零知识的性质，只是一个代数群模型中的查找协议

若对于任意$N$和给定的随机性，算法$gen$可以表示为$(gen_1,gen_2(t))$（其中$gen_1$固定，$gen_2$为$\mathbb F$中$t$的线性函数），则称该查找协议为同态的

4.1 The cq protocol

首先看一下$gen$算法

  1. 选择随机数$x\in \mathbb F$，计算$srs=\{[x^i]_1\}_{i\in [N-1]},\{[x^i]_2\}_{i\in [N]}$
  2. 计算$[Z_{\mathbb V}(x)]_2$
  3. 计算$T(X)=\sum_{i\in[N]}t_i\cdot L_i(X)$，计算$[T(x)]_2$
  4. 对$i\in [N]$，计算$q_i=[Q_i(x)]_1,[L_i(x)]_1,[\frac{L_i(x)-L_i(0)}{x}]_1$

其中$L_i$为拉氏基多项式，$Q_i$满足等式$L_i\cdot T=t_i\cdot L_i+Z_{\mathbb V}\cdot Q_i$

接下来是$IsInTable$算法，该算法分为三轮

第一轮首先需要承诺一个乘法向量，如下

  1. Prover计算多项式$m(X)\in \mathbb F_{<N}[X]$，计算方式为对于所有$f|_{\mathbb H}$中的$t_i$，令$m_i=t_i$
  2. Prover计算并发送承诺值$m=[m(x)]_1$

第二轮中，双方需要在一个随机点$\beta$处进行有理恒等式的插值，并利用配对完成检查

  1. Verifier选择随机数$\beta \in \mathbb F$
  2. Prover计算$A\in \mathbb F_{<N}[X]$，满足$A_i=m_i/(t_i+\beta)$
  3. Prvoer计算并发送$a=[A(x)]_1,q_a=[Q_A(x)]_1$，其中$Q_A(X)$满足等式$A(X)\cdot (T(X)+\beta)-m(X)=Q_A(X)\cdot Z_{\mathbb V}(X)$
  4. Prover计算$B(X),B_0(X)$，其中$B_i=\frac{1}{f_i+\beta},B_0(X)=\frac{B(X)-B(0)}{X}$，计算并发送承诺值$b_0=[B_0(x)]_1$
  5. Prover计算$Q_B(X)$及其对应的承诺$q_b=[Q_B(x)]_1$，满足等式$B(X)\cdot (f(x)+\beta)-1=Q_B(X)\cdot Z_{\mathbb H(X)}$
  6. Prover计算并发送承诺$p=[P(x)]_1$，其中$P(X)=B_0(X)\cdot X^{N-1-(n-2)}$
  7. Verifier验证两个配对等式：$e(a,[T(x)]_2)=e(q_a,[Z_{\mathbb V}(x)]_2)\cdot e(m-\beta\cdot a,[1]_2)$和$e(b_0,[x^{N-1-(n-2)}]_2)=e(p,[1]_2)$

第二轮的第四步有一个点需要注意一下：因为需要在处揭示多项式$B$，为了提高效率，可以直接对$B_0$承诺而无需对$B$承诺再揭示，此时有$B(X)=B_0(X)\cdot X+b_0$

协议第三轮中Verifier需要在一个随机点$\gamma$处验证多项式$B$的正确性

  1. Verifier选择并发送随机点$\gamma,\eta\in \mathbb F$
  2. Prvoer计算并发送$b_{0,\gamma}=B_0(\gamma),f_\gamma=f(\gamma),a_0=A(0)$
  3. Verifier令$b_0=\frac{N\cdot a_0}{n}$
  4. Verifier根据Prover发送的消息，计算$Z_{\mathbb H}(\gamma)=\gamma^n-1,b_\gamma=b_{0,\gamma}\cdot \gamma+b_0,Q_{b,\gamma}=\frac{b_\gamma\cdot (f_\gamma+\beta)-1}{Z_{\mathbb H}(\gamma)}$
  5. 之后双方需要执行一个KZG的批量检查，双方利用之前的随机数$\eta$，计算$v=b_{0,\gamma}+\eta\cdot f_\gamma+\eta^2\cdot Q_{b,\gamma}$
  6. Prover计算证明$\pi_\gamma=[h(x)]_1$，其中$h(X)=\frac{B_0(X)+\eta\cdot f(X)+\eta^2\cdot Q_B(X)-v}{X-\gamma}$
  7. Verifier计算$c=b_0+\gamma\cdot cm+\eta^2\cdot q_b$，之后验证配对等式$e(c-[v]_1+\gamma\cdot \pi_\gamma,[1]_2)=e(\pi_\gamma,[x]_2)$
  8. 最后双方需要检查$a_0$的正确性，Prover计算并发送$a_0=[A_0(x)]_1=[\frac{A(x)-a_0}{x}]_1$，Verifier验证配对等式$e(a-[a_0]_1,[1]_2)=e(a_0,[x]_2)$

注意到上述协议中一共需要9次配对，有点多，不过注意到有些配对的第二源群的元素相同（比如第二轮步骤7中第二个配对等式的右侧和第三轮第七步中配对等式的左侧，第二源群元素均为$[1]_2$），此时可以用配对的批处理技术来将这两个配对整合成一个配对，最终配对的数量可以减少到5次

接下来有几个主要的分析点：$gen$算法的预处理效率，$IsInTable$算法中的Prover开销和算法的知识合理性，这里主要看一下算法的知识合理性（效率分析可以看原文）

记$\mathcal A$为高效代数敌手，记$f$为协议第三轮中由敌手发送的多项式，对应的承诺值为$cm=[f(x)]_1$，由于$\mathcal A$是代数敌手，因此敌手在协议中不仅会发送多项式的承诺，还会发送承诺所对应的多项式

此时记事件$E$表示Verifier输出接受，注意到敌手赢得知识合理性游戏时包含事件$E$（$E$表示协议中所有配对检查均通过），记事件$A\sub E$表示其中一个理想配对检查未通过，根据之前的引理2，若$E$发生，则有$Pr[A]=negl(\lambda)$​

由于事件$A$发生的概率可忽略，首先观察协议的第二轮，步骤7中的第一个配对等式表明，对于所有的$i\in [N]$，均有$A_i=\frac{M_i}{T_i+\beta}$，第二个配对等式表明$deg(B_0)\leq n-2$

之后观察协议第三轮，若Prover为恶意的，则这两个验证等式成立的概率为$\frac{n}{|\mathbb F|}$，若验证通过，则表明Prover在第二步中发送的三个值正确

之前协议中定义$B(X)=B_0(X)\cdot X+b_0$，也即$deg(B)<n$，记$\omega$为$\mathbb H$的生成元，若第三轮两个验证等式通过，则第二轮步骤5中的等式成立的概率为$1-\frac{N+n}{|\mathbb F|}$，此时表明对于所有的$i\in [n]$，均有$B(\omega^i)=\frac{1}{f(\omega^i)+\beta}$

最后根据引理1，可以得到

$$ \begin{aligned} N\cdot a_0&=\sum_{i\in[N]}A_i=\sum_{i\in [N]}\frac{m_i}{T_i+\beta}\\ n\cdot b_0&=\sum_{i\in[N]}B_i=\sum_{i\in [N]}\frac{1}{f(\omega^i)+\beta} \end{aligned} $$

根据之前的检查，有$N\cdot a_0=n\cdot b_0$，因此有下列等式成立

$$ \sum_{i\in [N]}\frac{m_i}{T_i+\beta}=\sum_{i\in [N]}\frac{1}{f(\omega^i)+\beta} $$

根据引理3，此时表明$f|_{\mathbb H}\sub t$

综上，若对于$f|_{\mathbb H}\not \sub t$，Verifier输出接受的概率可忽略，故协议满足知识合理性

再次提醒：协议不满足零知识性

References

$[1]$ Liam Eagen, Dario Fiore, Ariel Gabizon:cq: Cached quotients for fast lookups. IACR Cryptol. ePrint Arch. 2022: 1763 (2022)

$[2]$ D. Feist and D. Khovratovich. Fast amortized kate proofs.

‍