由于Halo2 circuit中的gate是operate “locally”（on cells in the current row or defined relative rows），因此，通常需要从 任意cell中复制a value 到 gate所在当前行中。通常以equality argument的方式来实现，用于约束source cell和destination cell中的值相同。
Halo2中通过构建a permutation来实现equality constraints，并在proof中使用a permutation argument来完成相应约束。
所谓permutation： 为a one-to-one and onto mapping of a set onto itself。
可将a permutation唯一分解为cycles组合（up to ordering of cycles, and rotation of each cycle）。
有时，也会用cycle notation来表示permutation。令 ( a b c ) (a\ b\ c) (a b c)表示a cycle，其中 a a a maps to b b b， b b b maps to c c c， c c c maps to a a a，可将此扩展为任意size的cycle。 将两个或多个cycles写在一起，表示相应的permutation组合。如 ( a b ) ( c d ) (a\ b)\ (c\ d) (a b) (c d)表示a permutation： a a a maps to b b b， b b b maps to a a a， c c c maps to d d d，以及 d d d maps to c c c。
2. 构建permutation 2.1 目标想要构建a permutation，其中，a equality-constraint set中的每个subset of variables可形成a cycle。 如，假设具有定义了如下equality constraints的circuit：
- a ≡ b a \equiv b a≡b
- a ≡ c a \equiv c a≡c
- d ≡ e d \equiv e d≡e
从而具有equality-constraint sets { a , b , c } \{a,b,c\} {a,b,c}和 { d , e } \{d,e\} {d,e}。即想构建permutation： ( a b c ) ( d e ) (a\ b\ c)\ (d\ e) (a b c) (d e) 其中定义了mapping of [ a , b , c , d , e ] [a,b,c,d,e] [a,b,c,d,e] to [ b , c , a , e , d ] [b,c,a,e,d] [b,c,a,e,d]。
2.2 算法为了跟踪the set of cycles，需使用 disjoint set data structure，这种方式比较简单也易于实现，尽管不是最优的方案。
将current state 表示为：
- 1）一个数组 m a p p i n g \mathsf{mapping} mapping 来表示permutation 本身。
- 2）一个辅助数组 a u x \mathsf{aux} aux 来跟踪每个cycle的distinguished element。
- 3）另一个数组 s i z e s \mathsf{sizes} sizes 来跟踪每个cycle的size。
对于cycle C C C中的每个元素 c c c，有 a u x ( x ) \mathsf{aux}(x) aux(x)指向该元素 c ∈ C c\in C c∈C。这可支持快速判断2个element x , y x,y x,y是否在同一cycle——check a u x ( x ) = a u x ( y ) \mathsf{aux}(x)=\mathsf{aux}(y) aux(x)=aux(y)是否成立。 同理， s i z e s ( a u x ( x ) ) \mathsf{sizes}(\mathsf{aux}(x)) sizes(aux(x)) 为包含 x x x的cycle size。（仅适于 s i z e s ( a u x ( x ) ) \mathsf{sizes}(\mathsf{aux}(x)) sizes(aux(x))，而不是 s i z e s ( x ) \mathsf{sizes}(x) sizes(x)。）
以identity permutation为例： 对于所有的 x x x，有 m a p p i n g ( x ) = x , a u x ( x ) = x , s i z e s ( x ) = 1 \mathsf{mapping}(x)=x,\mathsf{aux}(x)=x,\mathsf{sizes}(x)=1 mapping(x)=x,aux(x)=x,sizes(x)=1。
为了增加an equality constraint l e f t ≡ r i g h t \mathit{left} \equiv \mathit{right} left≡right：
- 1）check l e f t \mathit{left} left 和 r i g h t \mathit{right} right 是否在同一cycle，即判断 a u x ( l e f t ) = a u x ( r i g h t ) \mathsf{aux}(left)=\mathsf{aux}(right) aux(left)=aux(right)是否成立，若成立，则直接返回。
- 2）若不成立，则 l e f t \mathit{left} left 和 r i g h t \mathit{right} right分属不同的cycle。将 l e f t \mathit{left} left 标记为larger cycle, r i g h t \mathit{right} right 标记为smaller cycle。若 s i z e s ( a u x ( l e f t ) ) < s i z e s ( a u x ( r i g h t ) ) \mathsf{sizes}(\mathsf{aux}(\mathit{left})) < \mathsf{sizes}(\mathsf{aux}(\mathit{right})) sizes(aux(left))<sizes(aux(right))，则将 l e f t \mathit{left} left 和 r i g h t \mathit{right} right 两者交换。
- 3）设置 s i z e s ( a u x ( l e f t ) ) = s i z e s ( a u x ( l e f t ) ) + s i z e s ( a u x ( r i g h t ) ) \mathsf{sizes}(\mathsf{aux}(\mathit{left})) = \mathsf{sizes}(\mathsf{aux}(\mathit{left})) + \mathsf{sizes}(\mathsf{aux}(\mathit{right})) sizes(aux(left))=sizes(aux(left))+sizes(aux(right))。
- 4）跟随 r i g h t \mathit{right} right （smaller）cycle的mapping around步骤，对于每一个元素 x x x，设置 a u x ( x ) = a u x ( l e f t ) \mathsf{aux}(x)=\mathsf{aux}(\mathit{left}) aux(x)=aux(left)。
- 5）通过交换 m a p p i n g ( l e f t ) \mathsf{mapping}(\mathit{left}) mapping(left)和 m a p p i n g ( r i g h t ) \mathsf{mapping}(\mathit{right}) mapping(right)，将smaller cycle 拼接成 larger cycle。
比如，已知2个disjoint cycles ( A B C D ) (A\ B\ C\ D) (A B C D) 和 ( E F G H ) (E\ F\ G\ H) (E F G H)：
A +---> B
^ +
| |
+ v
D <---+ C E +---> F
^ +
| |
+ v
H <---+ G
在增加constraint B ≡ E B \equiv E B≡E 后，以上算法生成的cycle为：
A +---> B +-------------+
^ |
| |
+ v
D <---+ C <---+ E F
^ +
| |
+ v
H <---+ G
若不在第1）步中验证 l e f t \mathit{left} left和 r i g h t \mathit{right} right是否在同一cycle，则将end up undoing an equality constraint。以如下constraints为例：
- a ≡ b a \equiv b a≡b
- b ≡ c b \equiv c b≡c
- c ≡ d c \equiv d c≡d
- b ≡ d b \equiv d b≡d
若只使用上述算法中的步骤5）来add an equality constraint，则最终构造的cycle为 ( a b ) ( c d ) (a\ b)\ (c\ d) (a b) (c d)，而不是正确的cycle ( a b c d ) (a\ b\ c\ d) (a b c d)。
3. Argument specification如需check a permutation of cells in m m m columns，可使用Lagrange basis polynomial v 0 , … , v m − 1 v_0, \ldots, v_{m-1} v0,…,vm−1 来表示。
可将 m m m columns中的每个cell 以a unique element of F × \mathbb{F}^{\times} F×来标记。
假设有permutation： σ ( c o l u m n : i , r o w : j ) = ( c o l u m n : i ′ , r o w : j ′ ) \sigma(\mathsf{column}: i, \mathsf{row}: j) = (\mathsf{column}: i', \mathsf{row}: j') σ(column:i,row:j)=(column:i′,row:j′) 其中cycles 对应为 equality-constraint sets。
若针对 {
(
l
a
b
e
l
,
v
a
l
u
e
)
}
\{(\mathit{label}, \mathit{value})\} {(label,value)} pairs set，则the values within each cycle are equal if and only if permuting the label in each pair by σ
\sigma σ yields the same set：
由于 l
a
b
e
l
label label是不同的，则set equality 等价为 multiset equality，可使用product argument来check。
令：
- ω \omega ω为 a 2 k 2^k 2k root of unity
- δ \delta δ为 a T T T root of unity
其中 T ⋅ 2 S + 1 = p T\cdot 2^S+1=p T⋅2S+1=p， T T T为奇数， k ≤ S k\leq S k≤S。
使用 δ i ⋅ ω j ∈ F × \delta^i\cdot \omega^j\in\mathbb{F}^{\times} δi⋅ωj∈F× 来表示 permutation argument中第 i i i列第 j j j行的cell。
将 σ \sigma σ 表示为 a vector of m m m polynomials s i ( X ) s_i(X) si(X) 使得 s i ( ω j ) = δ i ′ ⋅ ω j ′ s_i(\omega^j) = \delta^{i'} \cdot \omega^{j'} si(ωj)=δi′⋅ωj′。
identity permutation可表示为 a vector of m m m polynomials I D i ( ω j ) \mathsf{ID}_i(\omega^j) IDi(ωj) 使得 I D i ( ω j ) = δ i ⋅ ω j \mathsf{ID}_i(\omega^j) = \delta^i \cdot \omega^j IDi(ωj)=δi⋅ωj。
使用challenge β \beta β 将pair ( l a b e l , v a l u e ) (\mathit{label}, \mathit{value}) (label,value) 压缩为 l a b e l + β ⋅ v a l u e \mathit{label}+\beta \cdot \mathit{value} label+β⋅value。类似于lookup argument中的product argument，也引入challenge γ \gamma γ 来randomize each term of the product。
此时，已知a permutation represented by s 0 , ⋯ , s m − 1 s_0,\cdots, s_{m-1} s0,⋯,sm−1 over columns represented by v 0 , ⋯ , v m − 1 v_0,\cdots,v_{m-1} v0,⋯,vm−1，需保证： ∏ i = 0 m − 1 ∏ j = 0 n − 1 ( v i ( ω j ) + β ⋅ δ i ⋅ ω j + γ v i ( ω j ) + β ⋅ s i ( ω j ) + γ ) = 1 \prod\limits_{i=0}^{m-1} \prod\limits_{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 i=0∏m−1j=0∏n−1(vi(ωj)+β⋅si(ωj)+γvi(ωj)+β⋅δi⋅ωj+γ)=1
【此时， v i ( ω j ) + β ⋅ δ i ⋅ ω j v_i(\omega^j) + \beta \cdot \delta^i \cdot \omega^j vi(ωj)+β⋅δi⋅ωj 表示的是 unpermuted pair ( l a b e l , v a l u e ) (\mathit{label}, \mathit{value}) (label,value), 而 v i ( ω j ) + β ⋅ s i ( ω j ) + γ v_i(\omega^j) + \beta \cdot s_i(\omega^j) + \gamma vi(ωj)+β⋅si(ωj)+γ 表示permuted pair ( σ ( l a b e l ) , v a l u e ) (\sigma(\mathit{label}), \mathit{value}) (σ(label),value)。 】
令 Z P Z_P ZP 满足 Z P ( ω 0 ) = Z P ( ω n ) = 1 Z_P(\omega^0) = Z_P(\omega^n) = 1 ZP(ω0)=ZP(ωn)=1 且对于 0 ≤ j < n 0 \leq j < n 0≤j<n有: Z P ( ω j + 1 ) = ∏ h = 0 j ∏ i = 0 m − 1 v i ( ω h ) + β ⋅ δ i ⋅ ω h + γ v i ( ω h ) + β ⋅ s i ( ω h ) + γ = Z P ( ω j ) ∏ i = 0 m − 1 v i ( ω j ) + β ⋅ δ i ⋅ ω j + γ v i ( ω j ) + β ⋅ s i ( ω j ) + γ \begin{array}{rl} Z_P(\omega^{j+1}) &= \prod\limits_{h=0}^{j} \prod\limits_{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\limits_{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} ZP(ωj+1)=h=0∏ji=0∏m−1vi(ωh)+β⋅si(ωh)+γvi(ωh)+β⋅δi⋅ωh+γ=ZP(ωj)i=0∏m−1vi(ωj)+β⋅si(ωj)+γvi(ωj)+β⋅δi⋅ωj+γ
然后足够enforce the rules： Z P ( ω X ) ⋅ ∏ i = 0 m − 1 ( v i ( X ) + β ⋅ s i ( X ) + γ ) − Z P ( X ) ⋅ ∏ i = 0 m − 1 ( v i ( X ) + β ⋅ δ i ⋅ X + γ ) = 0 ℓ 0 ⋅ ( 1 − Z P ( X ) ) = 0 Z_P(\omega X) \cdot \prod\limits_{i=0}^{m-1} \left(v_i(X) + \beta \cdot s_i(X) + \gamma\right) - Z_P(X) \cdot \prod\limits_{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 ZP(ωX)⋅i=0∏m−1(vi(X)+β⋅si(X)+γ)−ZP(X)⋅i=0∏m−1(vi(X)+β⋅δi⋅X+γ)=0ℓ0⋅(1−ZP(X))=0
4. 调整为具有zero-knowledge属性第3节中的证明不具有zero-knowledge 属性。类似于lookup argument，可将以上证明中每列的最后 t t t行都以随机值填充。
限制usable rows的数量为 u = 2 k − t − 1 u=2^k-t-1 u=2k−t−1，与lookup argument中类似，引入2个selector：
- 1） q b l i n d q_{blind} qblind is set to 1 1 1 on the last t t t rows, and 0 0 0 elsewhere；
- 2） q l a s t q_{last} qlast is set to 1 1 1 only on row u u u, and 0 0 0 elsewhere（即，设置usable rows和blinding rows之间的过渡row）。
对于usable rows的product rule为： ( 1 − ( q l a s t ( X ) + q b l i n d ( X ) ) ) ⋅ \big(1 - (q_\mathit{last}(X) + q_\mathit{blind}(X))\big) \cdot (1−(qlast(X)+qblind(X)))⋅ ( Z P ( ω X ) ⋅ ∏ i = 0 m − 1 ( v i ( X ) + β ⋅ s i ( X ) + γ ) − Z P ( X ) ⋅ ∏ i = 0 m − 1 ( v i ( X ) + β ⋅ δ i ⋅ X + γ ) ) = 0 \hspace{1em}\left(Z_P(\omega X) \cdot \prod\limits_{i=0}^{m-1} \left(v_i(X) + \beta \cdot s_i(X) + \gamma\right) - Z_P(X) \cdot \prod\limits_{i=0}^{m-1} \left(v_i(X) + \beta \cdot \delta^i \cdot X + \gamma\right)\right) = 0 (ZP(ωX)⋅i=0∏m−1(vi(X)+β⋅si(X)+γ)−ZP(X)⋅i=0∏m−1(vi(X)+β⋅δi⋅X+γ))=0 同理，对于row 0 0 0的约束仍然为： ℓ 0 ( X ) ⋅ ( 1 − Z P ( X ) ) = 0 \ell_0(X) \cdot (1 - Z_P(X)) = 0 ℓ0(X)⋅(1−ZP(X))=0
由于此处不再依赖wraparound来保证the product Z ( ω 2 k ) = 1 Z(\omega^{2^k})=1 Z(ω2k)=1，因此，可替换为constrain Z ( ω u ) = 1 Z(\omega^{u})=1 Z(ωu)=1，但是这存在潜在的难点： 若存在某 i ∈ [ 0 , u ) i\in[0,u) i∈[0,u)使得 A i + β A_i+\beta Ai+β或 S i + γ S_i+\gamma Si+γ为 0 0 0，则可能就没法满足permutation argument。 这种情况发生的概率相对于 β , γ \beta,\gamma β,γ可忽略，但是这将是实现 perfect zero knowledge 和 perfect completeness 的一个障碍——因为adversary可rule out witnesses that would cause this situation。
为了保证perfect completeness和perfect zero knowledge，可约束 Z ( ω u ) Z(\omega^u) Z(ωu)要么为 0 0 0要么为 1 1 1： q l a s t ( X ) ⋅ ( Z ( X ) 2 − Z ( X ) ) = 0 q_\mathit{last}(X) \cdot (Z(X)^2 - Z(X)) = 0 qlast(X)⋅(Z(X)2−Z(X))=0 此时，若存在某个 i i i使得 A i + β = 0 A_i+\beta=0 Ai+β=0或者 S i + γ = 0 S_i+\gamma=0 Si+γ=0，则可设置 Z j = 0 Z_j=0 Zj=0 for i < j ≤ u i
