查找表（Lookup）论据

halo2实现任意集合的数据查找，相比Plookup简单。

语言（Language）说明

除了 语言的一般说明:

• $Z(X)$多项式（针对置换论据的大乘积论据多项式）称为“置换乘积”列。

技术描述

为了解释简单，我们先描述一个忽略零知识证明的论据描述的简单版本。

查找可以表示成 $2^k$行表（编号从0开始）的“子集”。$A$和$S$列分别是“子集”和“全集”。

“子集”论据保证$A$列中的元素都在 $S$列中。这意味着，$A$列中多个位置的元素对应着$S$列中同一位置的元素，并且$S$列中的某些元素可以不出现在$A$列的任何位置上。

• $S$ 列并不一定是固定的。也就是说，我们可以支持固定元素的查找或者动态查找（后者采用advice列）。
• $A$ 和$S$列中的元素可以重复。如果$A$ 和$S$列中的元素个数不正好是$2^k$的话，可以用$A$ 和$S$列中任意元素进行扩展。
  • 或者我们可以增加一个“查找选择子”，控制在$A$列中的哪些元素参与查找。采用这种方法可以替换下述公式中的$A(X)$ 。如果一个元素不需要查找，用$S_0$替换$A$。

假设 ${\ell }_i$ 是拉格朗日基多项式，在$i$行多项式为1，其他行为0。

从$A$ 和$S$列的置换开始。假设它们的置换分别为$A^{\prime }$ 和 $S^{\prime }$列。我们可以通过置换论据$Z$约束它们之间的置换关系： $$\begin{gathered} Z(\omega X)\cdot (A^{\prime }(X)+\beta )\cdot (S^{\prime }(X)+\gamma )-Z(X)\cdot (A(X)+\beta )\cdot (S(X)+\gamma )=0 \\ {\ell }_0(X)\cdot (1-Z(X))=0 \end{gathered}$$

也就是说，在除以0不发生的情况下，对所有的$i\in [0,2^k)$满足： $$\begin{gathered} Z_{i+1}=Z_i\cdot \frac{(A_i+\beta )\cdot (S_i+\gamma )}{(A_i^{\prime }+\beta )\cdot (S_i^{\prime }+\gamma )} \\ {Z}_{2^k}=Z_0=1. \end{gathered}$$

这个版本的论据证明$A^{\prime }$ 和 $S^{\prime }$列是$A$ 和$S$列的置换，但是并没有指明具体的置换关系。$\beta$ 和$\gamma$ 是独立因子。采用这两个因子，可以将两个置换论据组合在一起，不需要担心相互干扰。

这些置换的目的是让证明者提供的$A^{\prime }$ 和 $S^{\prime }$列满足一定的条件：

1. $A^{\prime }$列中相同的元素位置靠在一起。这可以通过某种排序算法实现。重要的是，相同的元素在$A^{\prime }$列中挨在一起，并且$A^{\prime }$列是$A$列的置换。
2. $A^{\prime }$列中挨在一起的相同元素的第一个元素存在于$S^{\prime }$列中。除去这个限制外，$S^{\prime }$列是$S$列的一个任意置换。

现在我们通过如下的规则限制$A_i^{\prime }=S_i^{\prime }$ 或者 $A_i^{\prime }=A_{i-1}^{\prime }$： $$(A^{\prime }(X)-S^{\prime }(X))\cdot (A^{\prime }(X)-A^{\prime }({\omega }^{-1}X))=0$$

除此之外，我们通过如下的规则限制$A_0^{\prime }=S_0^{\prime }$：

$${\ell }_0(X)\cdot (A^{\prime }(X)-S^{\prime }(X))=0$$

由于第二个规则，第一个规则中的($A^{\prime }(X)-A^{\prime }({\omega }^{-1}X)$ 这一项在$0$行没有效果，尽管 ${\omega }^{-1}X$ “能反转”。

这些约束规则一起有效的限制了$A^{\prime }$列（也就是$A$列）中的每个元素都存在于 $S^{\prime }$列中（也就是$S$列）。

加入零知识

为了在PLONK算法为基础的证明系统中加入零知识，我们需要在每列的最后加入$t$个随机元素。这些需要对查找论据进行调整，因为这些随机的元素并不满足之前的约束。

我们限制有效的行数为$u=2^k-t-1$。我们增加两个选择子：

• $q_{blind}$ 在最后 $t$ 行设置为1，其他行设置为0；
• $q_{last}$ 只在$u$行设置为1，其他行设置为0 （也就是说，它设置在有效行和盲化行的交界处）。

我们将之前的规则限制在有效行上：

$$\begin{gathered} (1-(q_{last}(X)+q_{blind}(X)))\cdot (Z(\omega X)\cdot (A^{\prime }(X)+\beta )\cdot (S^{\prime }(X)+\gamma )-Z(X)\cdot (A(X)+\beta )\cdot (S(X)+\gamma ))=0 \\ (1-(q_{last}(X)+q_{blind}(X)))\cdot (A^{\prime }(X)-S^{\prime }(X))\cdot (A^{\prime }(X)-A^{\prime }({\omega }^{-1}X))=0 \end{gathered}$$

在$0$行的限制规则保持不变：

$$\begin{gathered} {\ell }_0(X)\cdot (A^{\prime }(X)-S^{\prime }(X))=0 \\ {\ell }_0(X)\cdot (1-Z(X))=0 \end{gathered}$$

因为我们不能再依赖在 ${\omega }^{2^k}$点的环绕保证$Z$为1，相反我们要约束$Z({\omega }^u)$ 为1。这里有个难点：如果在任意$i\in [0,u)$， $A_i+\beta$ 或者 $S_i+\gamma$为0的话，置换论据可能不成立。虽然这种情况在 $\beta$ 和$\gamma$的取值下概率可以忽略，但是，对于完美零知识和完备性来说是个障碍（攻击者可以构造这样的情况）。

确保完美的完备性和零知识，我们允许$Z({\omega }^u)$为0或者1: $$q_{last}(X)\cdot (Z(X{)}^2-Z(X))=0$$

如果$A_i+\beta$ 和 $S_i+\gamma$在某些$i$ 上为0，我们可以在$i<j\le u$范围设置$Z_j=0$，满足上述的约束。

注意的是，挑战因子$\beta$ 和$\gamma$ 是在$A$ 和$S$列（以及$A^{\prime }$ 和 $S^{\prime }$列）承诺后生成的，证明者无法伪造$A_i+\beta$ 和 $S_i+\gamma$为0的情况。因为这种情况的概率可以忽略，可行性不受影响。

开销

• 原始$A$列和固定$S$列。
• 置换函数 $Z$。
• 两个置换$A^{\prime }$ 和 $S^{\prime }$列。
• 约束方程（门）的阶都不高。

泛化

halo2的查找论据实现实现了上述技术的泛化：

• $A$ 和$S$列扩展为多列，这些列之间通过随机挑战因子进行组合。$A^{\prime }$ 和 $S^{\prime }$列还是单列。
  • $S$列的各列承诺可以提前计算。这样在挑战因子确定后，利用Pedersen承诺的同态性质，可以很简便的组合成$S$列的承诺。
  • $A$列可以是采用相对引用的任意多项式表达式。这些可以替换到约束规则中去，受制于最大的阶。这样可能可以省去一个或者多个advice列。
• 这样的话，查找论据可以通过子集论据实现任意长度的关系。也就是说，为了约束$\mathcal{R}(x,y,...)$，将$\mathcal{R}$看成是$S$（通过前面的方法），并且检查关系成立 $(x,y,...)\in \mathcal{R}$。
  • 如果$\mathcal{R}$代表一个函数，同样需要检查输入是否在域中。这是我们想要的，经常会省去额外的范围检查。
• 我们可以在同一个电路中支持多表。利用标示列将多个表组合成一张表。
  • 标示列可以和之前提到的“查找选择子”合并。

这些泛化和Plookup论文的第4和第5节中的技术类似。和Plookup的区别是子集论据。相关技术，子集论据也适用；举个例子，Plookup论文的第5节中的优化范围检查技术同样可以用在子集论据中。