小结：
a. Halo2 使用 Permutation argument 技术，允许在任意数量的 columns 上进行 copy constraint;
b. 和 Plonk 里的 permutation argument 基本类似，但表现形式不同；
c. 对应的 Halo2 代码 main 分支,commit 为:
a7cd600eb60b1528159b92af5e426adcc615de1a
d. Halo2 book:
https://zcash.github.io/halo2/design/proving-system/permutation.html
Technique Description
1. Permutation cycle
Halo2 book 上说的算法稍微有点晦涩难懂（个人一开始没看懂），这里将通过一个简单实例来简单的表达下其主要思想，首先，让我们先看一个定义：
Define: cycle(a,b,c) => 表示元素之间的循环映射关系，即：map[a] = b, map[b] = c, map[c] = a，此定义可以延伸到任意大小的 cycle。
现在，考虑一个多项式 f(x)， 其部分点的取值为下表所示：
如果我们现在没有任何 copy constraint，那可以把四个 X 的值看成一个个独立的 permutation cycle，即 (0)(1)(2)(3)；现在，我们加上了第一个 copy constraint，f(0) = (f2)，显然，cycle (1) 和 cycle(3) 不受影响，而 cycle(0) 和 cycle(2) 将会组合成一个大的 cycle，其组合算法可以参考 Halo2 book 中的 Algoruthm 细节，下面用一张图来简单示意增加多个 copy constraints 后的 permutation cycle 的变化过程：
Figure1 permutation cycle composition
2. Without zero knowledge
Note1: 为了便于理解，先暂时忽略 zero knowledge 特性；
Note2: 在 Halo2 中，circuit 的所有信息由一个 table 表示，table 大小取决于 circuit 的大小
和 Lookup argument 类似，我们将在一个 table 上
(2k rows，index 从 0 开始 ) 论述多列数据部分元素之间的 equality property，即 copy constraint。如下图例所示，存在三组数据，分别占用了 table 的三列（cell 的数据格式如图中右上角所示）：
Figure2 copy constraint in halo2
如图所示：存在三列数据，分别对应三个多项式 V3(X), V5(X), V7(X) 依次在{X = 0…2k-1}之间的值；可以发现，在不同的多项式之间，我们对部分的 X 上的值进行了相等约束（copy constraint，如图中紫色和蓝色线条所示），因此，接下来，我们将通过 permutation argument 协议，来证明我们所希望的那些值相等的点 X，确实是成立的。
3. Permutation Argument Protocol:
Step1: Label And Define permutation index polynomial S
和 Lookup argument 不同，Permutation argument 明确指定了相等值的具体位置，如图中的 V3(1) = V5(0) 等；因此，需要定义一个新的多项式来表示不同的多项式之间的索引对应关系，具体的如下图所示：
Figure 3 define permutation index polynomial S
由于不同的多项式对应不同的 column index，因此通过引入 column index 可以区分不同的 evaluation domain(在 plonk 中，是通过引入 domain n 来区分，即如果有 k 个多项式，perm_index_poly 的 domain 是 kn)，其映射关系可以表示为：
以第 column index = 7 的多项式 V7(X) 为例，其对应的置换索引多项式 S7(col:i, row:j) 的真值为图中右侧所示。
Step2: Generate the proof
基于 Step1 生成的置换索引多项式集合 S = { Si } ，我们需要确保以下等式成立：
Note: 如果对三个多项式的索引进行重新排序（和原始的顺序无关，重新从 0 开始，则多项式索引依次为 0,1,2），则上述等式可以简单表示为：
其中置换索引多项式定义为： Scol:i (row : j) = σ i′w j′
其原理如下图所示：
由于引入了随机数β和γ，因此，当且只有 copy constraints 真正满足时，图中紫色线条和蓝色线条连接的两个 cell，才能以接近于 1 的概率确保相等（根据 Schwartz-Zippel 定理），因此最终分子和分母累乘的结果也是相等。
定义多项式 Zp ，满足 Zp(W0)=1 , 对于 0 < j < n,，则有：
对应的约束为：
4. Introduce zero knowledge
和 Lookup argument 类似，我们需要引入一些随机数来实现 zero knowledge，如果总的 rows 数为 2k ，有效的为 rows 数 u, 无效的 rows 数 t, 则需要满足 u+t+1=2k 。
新增了两个 selector：
1. qblind ，最后 t 行，值为 1，其他为 0
2. qlast ，row u 值为 1，其他为 0（在 usable rows 和 blind rows 中间）
则上述的约束需要修改成：
第 0 行的约束不变：
第 u 行的约束：
根据多项式的 Zp(X) 的公式可知，Zp(wu)=1( 分子分母值得集合相同 )。值得注意的是,这个约束，把 Zp(wu) 约束在了{0,1}范围内,但是为 0 的概率非常小
5. Spanning a large number of columns
根据公式可以发现，当参与 permutation argument 的多项式个数（m）很多时，会导致约束多项式的 degree 超过 SRS 定义的 degree bound。
因此，需要对上述的累乘过程切分成多次，思想如下图所示：
如图所示，切分粒度以 2 为例，假设 m = 3。我们先对多项式 V3(X),V5(X) 进行累乘操作，此时标记为 Zp,0(X) 且 Zp,0(w0)=1 ，当累乘到最后一个点时，即 j = u 时（u 为有效的 rows number），此时标记为 Zp,0(wu) ；然后启动第二个 chunk 的累乘，此时标记为 Zp,1(X) 且满足 Zp,1(w0)=Zp,0(wu) ，直到最后一个点时，需满足 Zp,1(wu)=1 。
综上，则约束变为：
其中: 0 ≤ a < b ; b = ceil (m / b)
第一行约束不变：
多个 chunk 之间需满足：
最后一行需满足：
关于我们
Sin7y 成立于 2021 年，由顶尖的区块链开发者组成。我们既是项目孵化器也是区块链技术研究团队，探索 EVM、Layer2、跨链、隐私计算、自主支付解决方案等最重要和最前沿的技术。
微信公众号:Sin7y
GitHub: Sin7y
Twitter: @Sin7y_Labs
Medium: Sin7y
Mirror: Sin7y
HackMD: Sin7y
HackerNoon: Sin7y
Email: contact@sin7y.org
【免责声明】市场有风险，投资需谨慎。本文不构成投资建议，用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资，责任自负。
