排列论证是一种证明两个列表包含相同元素（但可能顺序不同）的证明方法。例如，[2,3,1] 是 [1,2,3] 的一个排列，反之亦然。

排列论证在证明一个列表是另一个列表的排序版本时非常有用。也就是说，如果列表 B 与列表 A 拥有相同的元素，且 B 中的元素是有序的，那么我们就可以知道证明者正确地对 A 进行了排序。

为了确定两个列表是否相同，我们通常会对它们进行排序，并逐个元素进行比较。

然而，要确信一个列表是有序的，我们需要检查：1）元素是否按顺序排列；2）排序算法的输出是否包含与输入相同的元素。

这就产生了一个循环依赖——要知道一个列表是另一个列表的排列，我们必须知道它们的排序版本是完全相同的。但要知道排序算法是否被正确执行，我们又必须知道排序的输出是输入的排列。

在常规代码中这不是问题，但在 ZK（零知识证明）中，我们必须对计算的每一步都进行约束。

我们已经展示过如何证明一个列表是有序的。本章重点讲解如何证明两个列表互为排列。

选项 1：为排序算法编写约束

在前一章中，我们展示了如何为选择排序算法编写约束。选择排序算法的运行时间为 $\mathcal{O}(n^2)$，因此它将产生 $\mathcal{O}(n^2)$ 个约束。我们可以使用更高效的算法（如归并排序）来实现同一目标，从而产生 $\mathcal{O}(n \log n)$ 个约束，但正如我们很快会看到的，还有更好的解决方案。

选项 2：尝试直接约束一对一映射

我们可以尝试直接编写一个电路，当且仅当一个列表是另一个列表的排列时，该电路才会满足条件。换句话说，一个列表中的每个元素都在另一个列表中有匹配的元素，反之亦然。

例如，要证明 [a1, a2, a3] 是 [b1, b2, b3] 的排列，我们需要展示两者之间的映射关系。只需证明每个 a_i 都映射到 b 列表中的某个元素，且每个 b_i 都映射到 a 列表中的某个元素即可。

为了创建一个能够证明这种双向映射的电路，我们定义一个由 s 信号组成的矩阵，如下所示：

Copy

               b1             b2             b3
    --------------------------------------------
a1 | s11 = (a1-b1)  s12 = (a1-b2)  s12 = (a1-b3)
a2 | s21 = (a2-b1)  s22 = (a2-b2)  s23 = (a2-b3)
a3 | s31 = (a3-b1)  s32 = (a3-b2)  s33 = (a3-b3)

请注意，如果某个 s 信号为 0，则对应的 a 元素与 b 元素相等。例如，如果 a3 == b1，那么 s31 将会是 0。

然后，如果我们对 s 信号进行逐行和逐列的相乘，并将其乘积约束为如下所示的 o 信号，那么只要至少存在一个匹配元素，这些 o 信号就将为零。

Copy
     b1      b2      b3
a1  s11  ×  s12  ×  s13   =  o_row1
     ×       ×       ×
a2  s21  ×  s22  ×  s23   =  o_row2
     ×       ×       ×
a3  s31  ×  s32  ×  s33   =  o_row3
    ||      ||       ||
    o_col1  o_col2   o_col3

如果我们约束每个 o 信号都为零，这就等同于约束了 a 中的每个元素在 b 中至少有一个匹配的元素，反之亦然。考虑一下这些输出信号的含义：

• o_row1 为零当且仅当 a1 在 b 中有匹配的元素。
• o_row2 为零当且仅当 a2 在 b 中有匹配的元素。
• o_row3 为零当且仅当 a3 在 b 中有匹配的元素。
• o_col1 为零当且仅当 b1 在 a 中有匹配的元素。
• o_col2 为零当且仅当 b2 在 a 中有匹配的元素。
• o_col3 为零当且仅当 b3 在 a 中有匹配的元素。

因此，如果所有 o 信号均为零，那么每个列表中的各个元素在另一个列表中都有一个匹配项。

这种方法的缺点是，约束的数量会随着列表的长度呈二次方增长。

取而代之的是，我们将展示一种能在与列表长度呈线性的时间内证明一个列表是另一个列表的排列的方法。

致谢： 本文其余部分很大程度上参考了这份 Triton VM 的文档，我们仅展示了 Circom 的实现，并添加了一些更适合初学者的解释。

排列论证的工作原理

考虑一个如下形式的多项式：

如果改变相乘的顺序，它的值不会发生改变：

换句话说，对多项式的线性因式进行排列重组，不会改变该多项式的值。（线性因式是指形式为 $(x - a)$ 的项）。

我们并不通过在代数上将各项相乘来检查多项式是否相等。相反，我们可以使用一种更为高效、被称为 Schwartz-Zippel 引理 的多项式相等性测试。

该测试为 $x$ 采样一个随机点，并将其代入这两个多项式中。如果它们的计算结果相同，那么它们极有可能是同一个多项式（要了解为什么该测试是安全的，请参阅上面链接的文章）。

这种技术可用于证明数组 $[a,b,c]$ 和 $[b,c,a]$ 互为排列。我们创建一个电路，该电路将两个数组 $c_1,c_2,c_3,...,c_n$ 和 $d_1,d_2,d_3,...,d_n$ 作为输入，然后构造如下多项式：

最后，它为 $x$ 选取一个随机点，计算这两个多项式的值，并约束这两个乘积必须相同。

为了生成这个随机点（我们称之为 $r$），我们使用输入的哈希值，也就是对拼接后的数组进行哈希：

这样一来，证明者就无法试图通过选取一个多项式相交的值 $r$ 来“作弊”。一旦证明者提供了多项式，他们就无法控制评估这些多项式所用的值 $r$。

如果证明者更改了多项式，用于测试它们的值 $r$ 也会随之改变。

下面的电路接收两个列表并检查它们是否互为排列。数组信号 prodA 包含以下各项：

• $\texttt{prodA[0] = } r - a_0$
• $\texttt{prodA[1] = prodA[0]} \cdot(r - a_1)$
• $\texttt{prodA[2] = prodA[1]} \cdot(r - a_2)$
• $\texttt{prodA[n - 1] = prodA[n - 2]}\cdot(r -a_{n-1})$

因此，最后一个条目 prodA[n - 1] 保存的是多项式在 r 处的计算结果。在这里，r 是 hash.out，也就是数组 a 和 b 所有条目的 Poseidon 哈希值。

Copy

include "circomlib/poseidon.circom";

template IsPermutation(n) {
  signal input a[n];
  signal input b[n];

  // the random point will be the hash
  // of the concatenation of the arrays
  component hash = Poseidon(2 * n);
  for (var i = 0; i < n; i++) {
    hash.inputs[i] <== a[i];
    hash.inputs[i + n] <== b[i];
  }

  signal prodA[n];
  signal prodB[n];

  prodA[0] <== hash.out - a[0];
  prodB[0] <== hash.out - b[0];

  for (var i = 1; i < n; i++) {
    prodA[i] <== (hash.out - a[i]) * prodA[i - 1];
    prodB[i] <== (hash.out - b[i]) * prodB[i - 1];
  }

  // the evaluation of the polynomials at r = hash.out
  prodA[n - 1] === prodB[n - 1];
}

component main = IsPermutation(3);

/* INPUT = {
  "a": [1,2,3,4,5,6],
  "b": [1,2,3,4,6,5]
}
*/

漏洞：未对所有元素进行哈希

以这种方式生成随机点时，哈希值必须依赖于计算的所有输入。否则，恶意的证明者可以保持哈希值不变，并不断微调输出数组的值，直到找到多项式的相交点为止。

关于安全性的说明

该算法依赖的前提是，不相等的多项式最多只在 $d$ 个点相交，其中 $d$ 是这两个多项式的最大度数。如果有限域的规模远大于 $d$，那么在实际应用中我们可以假设，如果 $p$ 和 $q$ 是不相等的多项式，且 $r$ 是一个随机点，则 $p(r)\neq q(r)$。Circom 使用的有限域规模略大于 $2^{253}$。如果多项式的度数为一百万，那么 $r$ 是相交点的概率大约为 $2^{20}/2^{253}$ 或 $1/2^{233}$，即 $10^{70}$ 分之一。这几乎与宇宙中原子的数量在同一个数量级。

然而，如果我们使用一个非常小的有限域，例如 31 位数量级，那么对于一个随机的 $r$，出现 $p(r)=q(r)$ 且 $q \ne p$ 的概率就不可忽略了。