观前提醒

这篇论文符号比较多，而且每个字母的含义经常换来换去的，某种意义上来说需要断章取义的看

Abstract

本文提出了一种用于检查大小为$n$的乘法子群$H\subset \mathbb F$上多项式$f\in F_{<n}[X]$的承诺，包含一个大小为$t\in \mathbb F^d$的表

本文的协议可以被视为Bootle等人$[BCG+18]$针对类似问题的协议的简化，当我们的协议在$d\leq n$时可能会提高效率

$[BCG+18]$的协议要求对若干个度为$d\log n$的辅助多项式进行承诺，而本文的方案只需要对三个度为$n$的多项式进行承诺

zk-SNARK设置中此原语的一个常见用例是“批量范围证明”，可以用于证明所有的群$H$上的$f$都在某个范围$[0,...,M]$内

本文针对这种特殊情况提出了一个稍微优化的协议，并将其作为一个开放问题进行了改进

1 Introduction

当想要使用zk-SNARK来证明涉及AES-128或SHA-256等标准原语的语句时，会遇到这样一个问题，即这些原语中涉及的操作是“SNARK不友好的”

因为这些算法中会涉及到大量的位运算，比如按位与，按位异或，循环移位等操作，zk-SNARK不方便处理此类位操作

因此学界提出了一种新的方法，称为lookup，也即查表的方法来完成

在lookup中，通过预先计算一些合法的（输入-输出）组合来建立查找表（可以简单地理解为一个键值对表），之后再通过引入随机性的方式，将查找的大小由向量降低至单个域元素，这一过程可以用多项式表达，反映到多项式中就是两个多项式相等

举个例子，假设查找表中的值为$\{t_i\}_{i\in [d]}$，witness中的值是$\{f_i\}_{i\in[d]}$，可以证明下列多项式具有相同的根（忽略乘数）

$$ F(X)=\prod_{i\in[n]}(X-f_i)\\G(X)=\prod_{i\in[d]}(X-t_i) $$

比如对于非负整数$\{e_i\}_{i\in [d]}$，有$F(X)=\prod_{i\in[d]}(X-t_i)^{e_i}$

Bootle等人$[BCG+18]$给出了一个解决算法，但是他们的方案需要对一个较长的向量承诺，Plookup提出了一个更简单的协议用以证明上述问题

下文中记$f\subset t$，以表示$\{f_i\}_{i\in [n]} \subset \{t_i\}_{i\in [d]}$（$t$为$f$的子集）

先从一个简单的问题开始，记集合$f$排序的结果为集合$s$，然后考察一个$s$的子集$t$，并分别计算$s$和$t$中相邻元素的非零差分，若$f\sub t$，则$t$中元素在$f$中至少出现一次，因此集合$s$和$t$中的非零差分一定相等

但是反之，这个结论不成立，因此这是个必要条件，举个例子，假设有下面三个集合

$$ t=\{1,4,8\}\\ s=\{1,1,4,8,8,8\}\\ s'=\{1,5,5,5,8,8\} $$

简单计算一下，这三个集合的非零差分集均为$\{3,4\}$，但是$t$是$s$的子集，并不是$s'$的子集，也即子集关系可以推出差分集相等，但是差分集相等不能推出子集关系

因此我们需要引入一个方式来有效检查两个集合的子集关系，plookup的方式是引入随机性的思想来完成，选择域上的一个随机值$\beta \in \mathbb F$，然后比较两个集合$\{t_i+\beta \cdot t_{i+1}\}_{i\in [d-1]}$和$\{s_i+\beta \cdot s_{i+1}\}_{i\in [d-1]}$

考虑到集合中可能会出现相邻元素相等的情况，也即$s_i=s_{i+1}$，此时加入随机性后，得到了$s_i+\beta \cdot s_{i+1}=(1+\beta)\cdot s_i$，这意味着集合中重复的元素都是$1+\beta$的倍数，因此我们可以通过检查其是否能被$1+\beta$整除来验证，而不是直接在表中比较（具体而言，采用类似于$[GWC19]$的grand-product argument可以有效的完成检查）

不过这个方法有一个大前提，就是集合$t$中的值都至少在$f$中出现了一次，接下来介绍一种不需要这个前提的方法

2 Perliminaries

在介绍之前，先介绍一些符号与前置知识

  • 记$\mathbb F_{<d}[X]$表示域上度小于$d$的一元多项式

此外还需要一个$[GWC19]$中的多项式协议，该协议中Prover需要向一个理想参与方$I$证明一个度小于$d$的多项式，协议结束后，Verifier可以查询协议期间发送的多项式、输入多项式和预定义集合$H$上的预处理多项式，并检查这些多项式是否存在某些特定的关系

协议具体如下

给定正整数$d,D<t,l$，给定集合$H\sub \mathbb F$，一个$H$范围的$(d,D,t,l)$多项式协议为一个Prvoer、Verifier与可信第三方$I$的多轮协议，如下

  1. 协议包含一个预处理的多项式集合$g_1,...,g_l\in \mathbb F_{<d}[X]$
  2. Prover向$I$发送一个多项式$f\in \mathbb F_{<d}[X]$，若Prover发送的多项式不在该范围内，则协议终止
  3. Verifier向Prover返回一个随机数（公共掷币生成）
  4. 协议结束后，假设$f_1,...,f_t$为Prover发送给$I$的多项式，Verifier可能会请检查$\{f_1,...,f_t,g_1,...,g_l\}$中的某些多项式在$H$上恒等，也即

$$ F(X)=G(X,h_1(v_1(X)),...,h_M(v_M(X)))\equiv 0 $$

其中$h_i\in \{f_1,...,f_t,g_1,...,g_l\},G\in \mathbb F[X,X_1,...,X_M],v_1,...,v_M\in \mathbb F_{<d}[X]$，满足对于Prover选择的多项式$f_1,...,f_t$，有$F\in \mathbb F_{<D}[X]$

  1. Verifier收到$I$的关于多项式的身份后，若所有身份都成立，则Verifier输出接受，否则拒绝

$[GWC19]$的第4节显示了如何使用$[KZG10]$的多项式承诺方案将这样的协议编译为代数群模型中的协议

3 The main scheme

记正整数$n,d$，分别表示向量$f\in \mathbb F^n,t\in \mathbb F^d$的长度，令$H=\{g,...,g^{n+1}=1\}$为$\mathbb F$上阶为$n+1$的乘法子群

对于多项式$f\in \mathbb F[X],i\in [n+1]$，记$f_i=f(gi)$，对于向量$f\in \mathbb F^n$，将其用$\mathbb F_{<d}[X]$中的多项式表示，也即$f(g^i)=f_i$

若$f\sub t$，且$f$中的元素的顺序与$t$中一致，则称$f$以$t$排序，具体而言，对于任意的$i<i'\in [n]$，且$f_i\neq f_{i'}$，若有$j,j'\in [d]$，满足$t_j=f_i,t_{j'}=f_{i'}$，则有$j<j'$

接下来定义两个二元多项式$F,G$如下

$$ F(\beta,\gamma)=(1+\beta)^n\cdot \prod_{i\in [n]}(\gamma+f_i)\cdot \prod_{i\in [d-1]}(\gamma\cdot (1+\beta)+t_i+\beta t_{i+1}) \\ G(\beta,\gamma)=\prod_{i\in [n+d-1]}(\gamma(1+\beta)+s_i+\beta s_i) $$

接下来有个Claim，$F\equiv G$，当且仅当下列两个条件成立

  1. $f\sub t$
  2. $s=(f,t)$，且$s$以$t$排序

这里$s=(f,t)\in \mathbb F^{n+d}$表示$s=f+t$，是两个集合相加，而不是取并集

下面证明一下这个Claim

首先将$F,G$中的随机性系数$(1+\beta)$提到前面来，得到下面这样

$$ F(\beta,\gamma)=(1+\beta)^{n+d-1}\cdot \prod_{i\in [n]} (\gamma+f_i)\cdot \prod_{i\in [d-1]}\gamma+\frac{(t_i+\beta t_{i+1})}{(1+\beta)}\\ G(\beta,\gamma)(1+\beta)^{n+d-1}\cdot \prod_{i\in [n+d-1]}\gamma+\frac{(s_i+\beta s_{i+1})}{(1+\beta)} $$

对于必要性，若有上述两个条件成立，则对于所有的$j\in [d-1]$，均存在一个唯一的$i\in [n+d-1]$，满足$(t_j,t_{j+1})=(s_i,s_{i+1})$，在$F,G$中就表现为下面这个式子恒成立

$$ \gamma+\frac{(t_i+\beta t_{i+1})}{(1+\beta)}\equiv \gamma+\frac{(s_i+\beta s_{i+1})}{(1+\beta)} \tag 1 $$

接下来这样，我们把集合$[n+d-1]$划分成两个集合，$P$和$P'$，令$P'\sub [n+d-1]$，$P'$包含了上述的$d-1$个下标$i$，然后再令$P=[n+d-1]/P'$，这样一来我们就得到了一个一对一映射，也即$P\rarr [n]$，且对于任意$i\in P$，均有$s_i=f_{j(i)}$，对于任意$i\in P$，多项式$G$中的各个项为

$$ \gamma+\frac{(s_i+\beta s_{i+1})}{(1+\beta)}=\gamma +s_i=\gamma+f_{j(i)} \tag 2 $$

也即$G$中的这些项与$F$中的$\gamma +f_{j(i)}$相等，也即有$F\equiv G$

对于充分性，若两个多项式恒等，$F\equiv G$，则对于任意的$\beta,\gamma$，对这两个二元多项式赋值，得到的域元素也相等

由于$\mathbb F(\beta)[\gamma]$是唯一的因子分解域（unique factorization domain），两个多项式恒等意味着上述式(1)中的各个线性因子必然相等，因此对于任意的$i\in [d-1]$，$G$必然存在一个因子与$(\gamma+(t_i+\beta t_{i+1})/(1+\beta))$相等，也即必然存在某个$j\in [n+d-1]$，有

$$ \gamma+\frac{(t_i+\beta t_{i+1})}{(1+\beta)}\equiv \gamma+\frac{(s_i+\beta s_{i+1})}{(1+\beta)} $$

因此必然有$t_i+\beta t_{i+1}\equiv s_i+\beta s_{i+1}$，也即$t_i=s_i,t_{i+1}=s_{i+1}$

同样的，令$P'\sub [n+d-1]$表示这$d-1$个下标构成的集合，对于任意的$j\in [n+d-1]/P'$，$F$中必然有一个来自$f$因子与$G$中的因子相同，也即对于这些$j$，均有$i\in [n]$，满足

$$ \gamma+f_i=\gamma+\frac{(s_i+\beta s_{i+1})}{(1+\beta)} $$

也即有$f_i+\beta f_i=s_j+\beta s_{j+1}$，也即$f_i=s_j=s_{j+1}$

综上，当$s$中的连续值不同时，其正好等于$t$中的两个连续值，且所有的$f$中的值都是$t$中的值，证毕

这个Claim有一个点需要注意，不失一般性，假设$d=n+1$（若$d\leq n$，则重复$t$中的最后一个元素，直至满足体条件）

这个过程用公式描述可能不太好理解，画一个图就好理解了（图例参考$[2]$）

这里把公式和例子放在一起

注意$f,t$的非零差分集均为$\{3,4\}$​

$F\equiv G$，考虑之前与式(1)相关的划分$P'$的情况，有橙色框框的那两个等式成立，然后考虑与式(2)相关的划分$P$的情况，有蓝色那个框框的三个等式成立，因此有前面提到的两个条件成立，反之亦然

若我们改一下数据，把$f_3$由4改成5，则$f$的非零差分仍然为$\{3,4\}$，但是看一下此时情况如何

此时考虑式(1)，$t_1+\beta t_2$可以找到与之对应的$s_3+\beta s_4$，但是对于$t_2+\beta t_3=4+8\beta$，找不到与之对应的$s_i+\beta s_{i+1}$，因为$s_4+\beta s_5=4+5\beta$，$s_5+\beta s_6=5+8\beta$，都与之不相等，因此$t$不是$f$的子集

综上，当且仅当两个条件成立时，有$F\equiv G$，反之亦然

接下来基于这个Claim，看一下协议

协议预处理阶段，有一个预处理的多项式$t\in \mathbb F_{<n+1}[X]$描述查找表，协议输入为多项式$f\in \mathbb F_{<n}[X]$，接下来具体的协议如下

  1. 令向量$s\in \mathbb F^{2n+1}$表示$(f,t)$，以$t$排序，将$s$表示为两个度小于$n+1$的多项式$h_1,h_2\in \mathbb F_{<n+1}[X]$，其中对于$i\in [n+1]$，有$h_1(g^i)=s_i,h_2(g^i)=s_{n+i}$
  2. Prover计算$h_1,h_2$并发送给$I$
  3. Verifier选择两个随机值$\beta,\gamma \in \mathbb F$发送给Prover

  4. Prover计算一个多项式$Z\in \mathbb F_{<n+1}[X]$，用以聚合$F(\beta,\gamma)/G(\beta,\gamma)$的值，计算过程具体如下

    • 令$Z(g)=1$
    • 对于$2\leq i\leq n$，计算

$$ Z(g^i)=\frac{(1+\beta )^{i-1}\prod_{j<i}(\gamma +f_i)\cdot \prod_{1\leq j< i}(\gamma(1+\beta)+t_j+\beta t_{j+1})}{\prod_{1\leq j< i}(\gamma(1+\beta)+s_j+\beta s_{j+1})(\gamma(1+\beta)+s_{n+j}+\beta s_{n+j+1})} $$

    • 令$Z(g^{n+1})=1$
    1. Prover将$Z$发送给$I$
    2. Verifier检查$Z$确实具有正确的形式，且$Z(g^{n+1})=1$，具体而言，Verifier检查下列四项

    $$ \begin{aligned} &L_1(x)(Z(x)-1)=0\\ &(x-g^{n+1})Z(x)(1+\beta)\cdot (\gamma+f(x))(\gamma(1+\beta)+t(x)+\beta t(g\cdot x))=(x-g^{n+1})Z(g\cdot x)(\gamma(1+\beta)+h_1(x)+\beta h_1(g\cdot x))(\gamma(1+\beta)+h_2(x)+\beta h_2(g\cdot x))\\ &L_{n+1}(x)(h_1(x)-h_2(g\cdot x))=0\\ &L_{n+1}(x)(Z(x)-1)=0 \end{aligned} $$

    验证通过则Verifier输出接受

    这里步骤4的方式和Plonk类似，都是通过递归的方式定义多项式$Z$，然后令$Z(g^{n+1})=1$，相当于构成了一个循环，这里的原理和验证流程Plonk的类似，不再展开

    4 Generalizing to vector lookups and multiple tables

    向量查找的一种自然方式是查找键值对表，比如一个有$w-1$个输入的函数，我们可以令查找向量$(x_1,...,x_{w-1},f(x_1,...,x_{w-1}))$来验证

    假设有多个证据多项式$f_1,...,f_w\in \mathbb F_{<n}[X]$，以及一个查找表$t^*\in (\mathbb F^w)^d$（一个$w$行$d$列的查找表）

    我们希望检查对于所有的$j\in [n]$，都有$(f_1(g^j),...,f_w(g^j))\in t^*$，可以利用随机化的方式来优化上一节中介绍的情况，优化后可以让我们再一个等式中同时验证这$w$个多项式，接下来看看怎么做

    对于任意的$i\in [w]$，令预处理多项式中包括$t_i\in \mathbb F_{<d}[X]$，其中对于任意$j\in [d]$，有$t_i(g^j)=t^*_{i,j}$

    然后Verifier选择一个随机值$\alpha \in \mathbb F$，从而根据该随机值，可以定义下列两个多项式

    $$ t=\sum_{i\in [w]}\alpha^i t_i\\ f=\sum_{i\in [w]}\alpha^i f_i $$

    假设存在$j\in [n]$，有$(f_1(g^j),...,f_w(g^j))\notin t^*$，则$f(g^j)\notin t$概率至少为$d\cdot w/|\mathbb F|$

    4.1 Multiple tables

    假设我们有多个表$t^*_1,...,t^*_l$，对于任意的$i\in [n]$，我们希望检查一些预定义的值$j=j(i)\in [l]$，是否有$(f_1(g^i),...,f_w(g^i))\in t^*_j$

    为了进一步优化上述提到的方案，可以构建一个以$t^*_1,...,t^*_l$为子表的预处理的表，并添加指定表索引的列

    假设对于$j\in [l]$，有$t^*_j\in (\mathbb F^w)^{d/l}$，我们可以构建$t^*\in (\mathbb F^{w+1})^d$，其中包含元素$(j,(t^*_j)_i),j\in [l].i\in [d/l]$

    构建一个预处理多项式$q\in \mathbb F_{<n}[X]$，满足$q_i=j(i)$，因为$j(i)$为我们期望的第$i$个值所在的子表

    然后我们利用上述协议来检查所有的$i\in [n]$，有$(f_1(g^j),...,f_w(g^j))\in t^*$

    还是画个图来讲比较直观

    假设取$\alpha=2$，我们可以分别计算多项式$f$和$t$，如下

    $$ \begin{aligned} f(1)&=\sum_i \alpha^i \cdot f_i(1)\\ &=2\cdot 1+4\cdot 2+8\cdot 1+16\cdot 1\\ &=34\\ f(2)&=\sum_i \alpha^i \cdot f_i(2)\\ &=2\cdot 4+4\cdot 4+8\cdot 3+16\cdot 6\\ &=144\\ f(3)&=\sum_i \alpha^i \cdot f_i(3)\\ &=2\cdot 8+4\cdot 5+8\cdot 8+16\cdot 8\\ &=244\\ \end{aligned} $$

    $t$的计算同理

    这样一来，我们用随机值$\alpha$将四个多项式$f_1\sim f_4$压缩至了一个多项式$f$，同时也将查找表$t^*$由原来的四行压缩至了一行，相当于此时可以用一个等式批量验证四个多项式

    接下来扩展到多个表的情况，也即多个多项式映射到多个表的情况

    定义一个索引多项式$q$，用以表示当前列在哪一个表中可以查到，具体就是下面这个图

    其中$q(1)=1$表示当前列的（所有的$f_i(1)$）在Table 1中，而$q(3)=2$表示当前列（所有的$f_i(3)$）在Table 2中

    最后还需要在多项式$f$和$t$中加上索引$q$，就得到了上面这个结果，同样的也只需要验证一个等式即可

    5 An optimized solution for continuous ranges

    对于$d<n$，假设我们希望检查$f\sub \{0,...,d-1\}$，我们可以利用上述协议，对于$i\in [d]$，令$t_i=i-1$​

    不过本节给出一个具有相同复杂度的替代协议，该协议可以检查$f\sub \{0,...,2n-2\}$

    事实上该协议可以推广至$\{0,...,c(n-1)\}$，代价仅为增加Verifier的约束程度，具体思路可以看原文

    References

    $[1]$ Ariel Gabizon, Zachary J. Williamson:plookup: A simplified polynomial protocol for lookup tables. IACR Cryptol. ePrint Arch. 2020: 315 (2020)

    $[2]$ Plookup原理详解 - 知乎 (zhihu.com)