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

置换论证(Permutation argument)

鉴于 halo2 电路中的门是"局部地"操作的(作用于当前行或定义好的相对行中的单元格),因此常常需要把某个任意单元格中的值复制到当前行中,以供门使用。这是通过等式约束(equality constraint)来完成的,该约束强制源单元格与目标单元格包含相同的值。

我们实现这些等式约束的方式,是构造一个表示这些约束的置换,然后在证明中使用置换论证来强制它们成立。

记号

置换(permutation)是一个集合到其自身的一一(one-to-one)且映满(onto)的映射。一个置换可以唯一地分解为若干循环(cycle)的复合(在循环的排序以及每个循环的旋转意义下)。

我们有时使用循环记号(cycle notation)来书写置换。设 $(abc)$ 表示一个循环,其中 $a$ 映到 $b$,$b$ 映到 $c$,$c$ 映到 $a$(对任意大小的循环有显然的推广)。把两个或多个循环并排书写表示对应置换的复合。例如,$(ab)(cd)$ 表示这样的置换:把 $a$ 映到 $b$,$b$ 映到 $a$,$c$ 映到 $d$,$d$ 映到 $c$。

构造置换

目标

我们想要构造一个置换,使得处于同一等式约束集合中的每一组变量构成一个循环。例如,假设我们有一个电路,定义了如下等式约束:

• $a\equiv b$
• $a\equiv c$
• $d\equiv e$

由此我们得到等式约束集合 $\{a,b,c\}$ 和 $\{d,e\}$。我们想要构造置换:

$$(abc)(de)$$

它定义了从 $[a,b,c,d,e]$ 到 $[b,c,a,e,d]$ 的映射。

算法

我们需要跟踪一组循环,这是一个不相交集合的集合(set of disjoint sets)。针对这一问题已有高效的数据结构;为简单起见,我们选择一个并非渐近最优、但易于实现的数据结构。

我们将当前状态表示为:

• 一个数组 $\mathsf{mapping}$,表示置换本身;
• 一个辅助数组 $\mathsf{aux}$,跟踪每个循环的一个特定代表元素;
• 另一个数组 $\mathsf{sizes}$,跟踪每个循环的大小。

我们有这样一个不变式:对于给定循环 $C$ 中的每个元素 $x$,$\mathsf{aux}(x)$ 都指向同一个元素 $c\in C$。这使我们能够通过检查 $\mathsf{aux}(x)=\mathsf{aux}(y)$ 来快速判定给定的两个元素 $x$ 和 $y$ 是否在同一循环中。此外,$\mathsf{sizes}(\mathsf{aux}(x))$ 给出包含 $x$ 的循环的大小。(这一点仅对 $\mathsf{sizes}(\mathsf{aux}(x))$ 成立,而不对 $\mathsf{sizes}(x)$ 成立。)

算法以恒等置换(identity permutation)的表示作为起点:对所有 $x$,我们设 $\mathsf{mapping}(x)=x$,$\mathsf{aux}(x)=x$,$\mathsf{sizes}(x)=1$。

要添加一个等式约束 $left\equiv right$:

1. 检查 $left$ 和 $right$ 是否已经在同一循环中,即是否 $\mathsf{aux}(left)=\mathsf{aux}(right)$。若是,则无需做任何事。
2. 否则,$left$ 和 $right$ 属于不同的循环。让 $left$ 为较大的循环、$right$ 为较小的循环:当 $\mathsf{sizes}(\mathsf{aux}(left))<\mathsf{sizes}(\mathsf{aux}(right))$ 时把二者交换。
3. 设 $\mathsf{sizes}(\mathsf{aux}(left)):=\mathsf{sizes}(\mathsf{aux}(left))+\mathsf{sizes}(\mathsf{aux}(right)).$
4. 沿着映射绕较小(右侧)循环走一圈,对每个元素 $x$ 设 $\mathsf{aux}(x):=\mathsf{aux}(left)$。
5. 通过交换 $\mathsf{mapping}(left)$ 与 $\mathsf{mapping}(right)$,把较小的循环拼接(splice)进较大的循环中。

例如,给定两个不相交的循环 $(ABCD)$ 和 $(EFGH)$:

A +---> B
^       +
|       |
+       v
D <---+ C       E +---> F
                ^       +
                |       |
                +       v
                H <---+ G

在添加约束 $B\equiv E$ 之后,上述算法产生如下循环:

A +---> B +-------------+
^                       |
|                       |
+                       v
D <---+ C <---+ E       F
                ^       +
                |       |
                +       v
                H <---+ G

错误的替代做法

如果我们不检查 $left$ 和 $right$ 是否已经在同一循环中,那么我们可能会撤销一个等式约束。例如,如果我们有如下约束:

• $a\equiv b$
• $b\equiv c$
• $c\equiv d$
• $b\equiv d$

而我们试图仅用上述算法的第 5 步来实现等式约束的添加,那么我们最终会构造出循环 $(ab)(cd)$,而不是正确的 $(abcd)$。

论证规约(Argument specification)

我们需要检查 $m$ 列中单元格的一个置换,这些列以拉格朗日基表示为多项式 $v_0,\dots ,v_{m-1}$。

我们将给这 $m$ 列中的每个单元格标注一个 ${\mathbb{F}}^{\times }$ 中唯一的元素。

假设我们在这些标签上有一个置换, $$\sigma (\mathsf{column}:i,\mathsf{row}:j)=(\mathsf{column}:i^{\prime },\mathsf{row}:j^{\prime }).$$ 其中各循环对应于等式约束集合。

如果我们考虑序对的集合 $\{(label,value)\}$,那么每个循环中的各个值彼此相等,当且仅当用 $\sigma$ 对每个序对中的标签进行置换后,得到的是同一个集合:

由于标签互不相同,集合相等等同于多重集合(multiset)相等,而后者可以用乘积论证(product argument)来检查。

设 $\omega$ 为一个 $2^k$ 次单位根(root of unity),设 $\delta$ 为一个 $T$ 次单位根,其中 $T\cdot 2^S+1=p$,$T$ 为奇数且 $k\le S.$ 我们将用 ${\delta }^i\cdot {\omega }^j\in {\mathbb{F}}^{\times }$ 作为置换论证中第 $i$ 列第 $j$ 行单元格的标签。

我们用一个由 $m$ 个多项式 $s_i(X)$ 构成的向量来表示 $\sigma$,使得 $s_i({\omega }^j)={\delta }^{i^{\prime }}\cdot {\omega }^{j^{\prime }}.$

注意,恒等置换可以用由 $m$ 个多项式 ${\mathsf{ID}}_i({\omega }^j)$ 构成的向量来表示,使得 ${\mathsf{ID}}_i({\omega }^j)={\delta }^i\cdot {\omega }^j.$

我们将用一个挑战 $\beta$ 把每个 $(label,value)$ 序对压缩为 $value+\beta \cdot label.$ 正如我们在查表中所用的乘积论证一样,我们还使用一个挑战 $\gamma$ 来随机化乘积的每一项。

现在,给定由 $s_0,\dots ,s_{m-1}$ 表示的置换,作用于由 $v_0,\dots ,v_{m-1}$ 表示的各列,我们想要确保: $$\prod _{i=0}^{m-1}\prod _{j=0}^{n-1}\left(\frac{v_i({\omega }^j)+\beta \cdot {\delta }^i\cdot {\omega }^j+\gamma }{v_i({\omega }^j)+\beta \cdot s_i({\omega }^j)+\gamma }\right)=1$$

这里 $v_i({\omega }^j)+\beta \cdot {\delta }^i\cdot {\omega }^j$ 表示未置换的 $(label,value)$ 序对,而 $v_i({\omega }^j)+\beta \cdot s_i({\omega }^j)$ 表示已置换的 $(\sigma (label),value)$ 序对。

设 $Z_P$ 满足 $Z_P({\omega }^0)=Z_P({\omega }^n)=1$,且对 $0\le j<n$: $$\begin{array}{rl}{Z}_P({\omega }^{j+1})& =\prod _{h=0}^j\prod _{i=0}^{m-1}\frac{v_i({\omega }^h)+\beta \cdot {\delta }^i\cdot {\omega }^h+\gamma }{v_i({\omega }^h)+\beta \cdot s_i({\omega }^h)+\gamma }\\ & =Z_P({\omega }^j)\prod _{i=0}^{m-1}\frac{v_i({\omega }^j)+\beta \cdot {\delta }^i\cdot {\omega }^j+\gamma }{v_i({\omega }^j)+\beta \cdot s_i({\omega }^j)+\gamma }\end{array}$$

那么,强制如下规则就足够了: $$\begin{gathered} Z_P(\omega X)\cdot \prod _{i=0}^{m-1}\left(v_i(X)+\beta \cdot s_i(X)+\gamma \right)-Z_P(X)\cdot \prod _{i=0}^{m-1}\left(v_i(X)+\beta \cdot {\delta }^i\cdot X+\gamma \right)=0 \\ {\ell }_0\cdot (1-Z_P(X))=0 \end{gathered}$$

这里假设列数 $m$ 使得上述第一条规则中的多项式能够落在 PLONK 配置的次数界之内。我们将在下文看到如何处理更多列数的情况。

用于得到恒等置换简洁表示的这一优化由 Vitalik Buterin 为 PLONK 提出,描述在 PLONK 论文第 8 节末尾。注意,只要启用等式约束的列数不超过 $T$,这些 ${\delta }^i$ 就都是各不相同的二次非剩余(quadratic non-residue);对于 Halo 2 所用的曲线,这一点在实践中总是成立。

零知识调整

与查表论证类似,我们需要对上述论证作出调整,以应对每一列最后 $t$ 行被填充为随机值的情况。

我们把可用行的数量限制为 $u=2^k-t-1$。我们添加两个选择子,其定义方式与查表论证中相同:

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

我们仅对可用行启用上面的乘积规则:

$(1-(q_{last}(X)+q_{blind}(X)))\cdot$ $\left(Z_P(\omega X)\cdot \prod _{i=0}^{m-1}\left(v_i(X)+\beta \cdot s_i(X)+\gamma \right)-Z_P(X)\cdot \prod _{i=0}^{m-1}\left(v_i(X)+\beta \cdot {\delta }^i\cdot X+\gamma \right)\right)=0$

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

$${\ell }_0(X)\cdot (1-Z_P(X))=0$$

由于我们不能再依赖绕回来保证每个乘积 $Z_P$ 在 ${\omega }^{2^k}$ 处重新变为 $1$,我们改为需要约束 $Z({\omega }^u)=1$。这就引出了与查表论证中所描述的相同的问题。因此我们允许 $Z({\omega }^u)$ 取零或一:

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

这给出了完美完备性和零知识。

跨越大量列

halo2 的实现在实践中并不限制可启用等式约束的列数。因此,它必须解决一个问题:上述方法可能产生一个乘积规则,其中的多项式超出了 PLONK 配置的次数界。次数界可以提高,但如果没有其他规则需要更大的次数,这样做会效率低下。

取而代之,我们把乘积拆分到 $b$ 个由 $m$ 列组成的列集(column set)上,使用乘积列 $Z_{P,0},\dots Z_{P,b-1}$,并用另一条规则把乘积从一个列集的末端复制到下一个列集的开端。

也就是说,对 $0\le a<b$ 我们有:

$(1-(q_{last}(X)+q_{blind}(X)))\cdot$ $\left(Z_{P,a}(\omega X)\cdot \prod _{i=am}^{(a+1)m-1}\left(v_i(X)+\beta \cdot s_i(X)+\gamma \right)-Z_P(X)\cdot \prod _{i=am}^{(a+1)m-1}\left(v_i(X)+\beta \cdot {\delta }^i\cdot X+\gamma \right)\right)$ $=0$

为简单起见,这里的书写假设启用等式约束的列数是 $m$ 的倍数;如果不是,那么最后一个列集的乘积将少于 $m$ 项。

对于第一个列集我们有:

$${\ell }_0\cdot (1-Z_{P,0}(X))=0$$

对于每个后续列集 $0<a<b$,我们用如下规则把 $Z_{P,a-1}({\omega }^u)$ 复制到下一个列集的起点 $Z_{P,a}({\omega }^0)$:

$${\ell }_0\cdot \left(Z_{P,a}(X)-Z_{P,a-1}({\omega }^{u}X)\right)=0$$

对于最后一个列集,我们允许 $Z_{P,b-1}({\omega }^u)$ 取零或一:

$$q_{last}(X)\cdot \left(Z_{P,b-1}(X{)}^2-Z_{P,b-1}(X)\right)=0$$

这与之前一样给出了完美完备性和零知识。