译自 halo2 book:https://zcash.github.io/halo2/design/proving-system/lookup.html

查表论证(Lookup argument)

Halo 2 使用以下查表技术,它允许在任意集合中进行查表,并且可以说比 Plookup 更简单。

关于术语的说明

除了关于术语的通用说明之外:

• 我们把 $Z(X)$ 多项式(置换论证中的大乘积论证多项式,grand product argument polynomial)称为"置换乘积"(permutation product)列。

技术描述

为了便于讲解,我们先描述一个忽略零知识(zero knowledge)的简化版本论证。

我们用一个"子集论证"(subset argument)来表达查表,该论证作用于一张具有 $2^k$ 行(从 0 开始编号)、含有列 $A$ 和 $S$ 的表格之上。

子集论证的目标是强制 $A$ 中的每个单元格都等于 $S$ 中的_某个_单元格。这意味着 $A$ 中的多个单元格可以等于 $S$ 中的_同一个_单元格,而 $S$ 中的某些单元格不需要等于 $A$ 中的任何单元格。

• $S$ 可以是固定的,但不必如此。也就是说,我们既支持在固定表中查值,也支持在变量表(后者包含建议列)中查值。
• $A$ 和 $S$ 可以包含重复项。如果 $A$ 和/或 $S$ 所表示的集合的大小不天然为 $2^k$,我们就用重复项扩充 $S$,并用已知存在于 $S$ 中的占位值(dummy value)扩充 $A$。
  • 或者,我们可以添加一个"查表选择子"(lookup selector),用来控制 $A$ 列中的哪些元素参与查表。这会修改下面置换规则中 $A(X)$ 的出现:当某行未被选中进行查表时,把 $A$ 替换为(例如)$S_0$。

设 ${\ell }_i$ 为拉格朗日基(Lagrange basis)多项式,它在第 $i$ 行求值为 $1$,其余处为 $0$。

我们先允许证明者提供 $A$ 和 $S$ 的置换列。分别称之为 $A^{\prime }$ 和 $S^{\prime }$。我们可以用一个带乘积列 $Z$ 的置换论证来强制它们确实是置换,规则如下:

$$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$$

即:只要不发生除以零的情况,对所有 $i\in [0,2^k)$ 我们有:

$$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.$$

这是置换论证的一个版本,它允许 $A^{\prime }$ 和 $S^{\prime }$ 分别是 $A$ 和 $S$ 的置换,但并不指定具体的置换。$\beta$ 和 $\gamma$ 是两个独立的挑战(challenge),这样我们就可以把这两个置换论证合并为一个,而不必担心它们彼此干扰。

这些置换的目标,是允许证明者以特定方式排列 $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$$

(尽管 ${\omega }^{-1}X$ 会"绕回",这里第一条规则中的 $A^{\prime }(X)-A^{\prime }({\omega }^{-1}X)$ 项在第 $0$ 行也不起作用,因为有第二条规则。)

这些约束合在一起,有效地强制 $A^{\prime }$(从而 $A$)中的每个元素都至少等于 $S^{\prime }$(从而 $S$)中的一个元素。证明:对各行前缀做归纳。

零知识调整

为了让基于 PLONK 的证明系统实现零知识,我们需要把每一列的最后 $t$ 行填充为随机值。这要求对查表论证作出调整,因为这些随机值并不满足上面描述的约束。

我们把可用行(usable row)的数量限制为 $u=2^k-t-1$。我们添加两个选择子:

• $q_{blind}$ 在最后 $t$ 行上置为 $1$,其余处为 $0$;
• $q_{last}$ 仅在第 $u$ 行置为 $1$,其余处为 $0$(即它被置于可用行与盲化行之间的那一行)。

我们仅对可用行启用上面的约束:

$$(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$$

在第 $0$ 行启用的规则保持不变:

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

由于我们不能再依赖绕回(wraparound)来保证乘积 $Z$ 在 ${\omega }^{2^k}$ 处重新变为 $1$,我们改为需要把 $Z({\omega }^u)$ 约束为 $1$。然而,这里存在一个潜在困难:如果对某个 $i\in [0,u)$,$A_i+\beta$ 或 $S_i+\gamma$ 中有任何一个为零,那么可能无法满足置换论证。这种情况在 $\beta$ 和 $\gamma$ 的选择上以可忽略的概率发生,但它既是实现完美零知识的障碍(因为对手可以排除掉会导致这种情况的见证值),也是实现完美完备性(perfect completeness)的障碍。

为了同时确保完美完备性和完美零知识,我们允许 $Z({\omega }^u)$ 取零或一:

$$q_{last}(X)\cdot (Z(X{)}^2-Z(X))=0$$

现在,如果对某个 $i$,$A_i+\beta$ 或 $S_i+\gamma$ 为零,我们就可以对 $i<j\le u$ 设 $Z_j=0$,从而满足约束系统。

注意,挑战 $\beta$ 和 $\gamma$ 是在对 $A$ 和 $S$(以及 $A^{\prime }$ 和 $S^{\prime }$)做出承诺之后才选定的,因此证明者无法强行制造出某个 $A_i+\beta$ 或 $S_i+\gamma$ 为零的情况。由于这种情况以可忽略的概率发生,可靠性(soundness)不受影响。

开销

• 有原始列 $A$ 和固定列 $S$。
• 有一个置换乘积列 $Z$。
• 有两个置换 $A^{\prime }$ 和 $S^{\prime }$。
• 这些门的次数(degree)都很低。

推广

Halo 2 的查表论证实现以如下方式推广了上述技术:

• $A$ 和 $S$ 可以扩展为多列,并用一个随机挑战组合起来。$A^{\prime }$ 和 $S^{\prime }$ 仍保持为单列。
  • 对 $S$ 各列的承诺可以预先计算,然后在挑战已知后,利用 Pedersen 承诺的同态(homomorphic)性质廉价地组合起来。
  • $A$ 的各列可以用相对引用以任意多项式表达式给出。这些表达式会被代入乘积列约束中,但要受最大次数界(maximum degree bound)的限制。这有可能节省一个或多个建议列。
• 然后,任意宽度关系的查表论证可以用子集论证来实现,即:为了在每一行约束 $\mathcal{R}(x,y,...)$,把 $\mathcal{R}$ 看作一个元组集合 $S$(使用上一点的方法),并检查 $(x,y,...)\in \mathcal{R}$。
  • 在 $\mathcal{R}$ 表示一个函数的情况下,这隐式地也检查了输入是否在定义域内。这通常正是我们想要的,且常常能省掉一次额外的范围检查(range check)。
• 我们可以在同一个电路中支持多张表,办法是把它们合并成单张表,其中包含一个标签列(tag column)来标识原始表。
  • 如果前面提到的"查表选择子"得以实现,标签列可以与之合并。

这些推广与 Plookup 论文第 4、5 节中的推广类似。也就是说,与 Plookup 的差异在于子集论证。这一论证随后可以用于所有相同的用途;例如,Plookup 论文第 5 节中优化的范围检查技术也可以与这个子集论证一起使用。