译自 halo2 book:https://zcash.github.io/halo2/design/implementation/selector-combining.html

选择子合并(Selector combining)

大量使用自定义门(custom gate)会导致一个电路定义出许多二元选择子(binary selector),这会增加证明大小和验证时间。

本节描述一种由 halo2 自动应用的优化,它把二元选择子列合并为更少的固定列(fixed column)。

其基本思想是:如果我们有 $\ell$ 个标记为 $1,\dots ,\ell$ 的二元选择子,且它们在互不相交的行集合上被启用(enabled),那么在某些附加条件下,我们可以把它们合并为单个固定列,记作 $q$,使得: $$q=\{\begin{array}{ll}k,& \text{如果标记为 }k\text{ 的选择子取值为 }1\\ 0,& \text{如果所有这些选择子都取值为 }0.\end{array}$$

然而,魔鬼藏在细节之中。

halo2 的 API 允许把某些选择子定义为「简单选择子(simple selectors)」,但须满足以下条件:

每一个涉及简单选择子 $s$ 的多项式约束(polynomial constraint)都必须具有 $s\cdot t=0$ 的形式,其中 $t$ 是一个不涉及任何简单选择子的多项式。

假设 $s$ 在某组 $\ell$ 个简单选择子中标记为 $k$,这组选择子如上所述被合并为 $q$。那么上述条件可确保,把 $s$ 替换为 $q\cdot {\prod }_{1\le h\le \ell ,h\ne k}(h-q)$ 不会改变任何约束的含义。

也可以通过确保对二元选择子的每一次使用都被替换为它的值由相应合并选择子精确插值(interpolation)得到的表达式,来放宽这个条件。然而,

• 这条限制简化了实现、开发者工具链,以及人类对所得约束系统的理解与调试;
• 对于典型电路而言,这条限制并未很大程度上妨碍该优化的适用范围。

注意,把 $s$ 替换为 $q\cdot {\prod }_{1\le h\le \ell ,h\ne k}(h-q)$ 会使由 $s$ 选中的约束的次数(degree)增加 $\ell -1$,因此我们必须以不超过最大次数界(maximum degree bound)的方式来选取要合并的选择子。

识别可被合并的选择子

我们需要对整个选择子集合 $s_0,\dots ,s_{m-1}$ 进行一个划分,分成若干子集(称为「组合,combinations」),使得同一组合中没有两个选择子在同一行上被启用。

标记(label)在一个组合内必须唯一,但跨组合并不唯一。不要把选择子的索引(index)与它的标记混淆。

假设我们已给定 $max\_degree$,即电路的次数界。

我们使用以下算法:

1. 不优化非简单选择子,即把它们每一个都映射到一个单独的固定列。
2. 检查(或通过构造确保)涉及每个简单选择子 $s_i$ 的所有多项式约束都具有 $s_i\cdot t_{i,j}=0$ 的形式,其中 $t_{i,j}$ 不涉及任何简单选择子。对每个 $i$,把任意 $t_{i,j}$ 的最大次数记为 $d_i^{\mathsf{max}}$。
3. 计算一个二元的「排斥矩阵(exclusion matrix)」$X$,使得当 $i\ne j$ 且 $s_i$ 与 $s_j$ 在同一行上被启用时 $X_{j,i}$ 为 $1$;否则为 $0$。

   由于 $X$ 是对称的且对角线为零,我们可以只用它的上三角或下三角项来表示它。算法的其余部分保证只访问 $j>i$ 的那些项 $X_{j,i}$。

4. 把一个布尔数组 ${\mathsf{added}}_{\mathrm{0..}k-1}$ 初始化为全 $\mathsf{false}$。

   ${\mathsf{added}}_i$ 将记录 $s_i$ 是否已被纳入任何组合。

5. 遍历那些尚未被加入任何组合的 $s_i$:
   • a. 把 $s_i$ 加入一个全新的组合 $c$,并令 ${\mathsf{added}}_i=\mathsf{true}$。
   • b. 令 mut $d:=d_i^{\mathsf{max}}-1$。

     $d$ 用于跟踪到目前为止组合 $c$ 中所涉及的任何门的最大次数,不包括选择子表达式。

   • c. 遍历所有 $j>i$ 且有可能加入 $c$ 的选择子 $s_j$,即 ${\mathsf{added}}_j$ 为 false 的那些:
     • i.(优化)如果 $d+\mathsf{len}(c)=max\_degree$,跳出到外层循环,因为不能再向 $c$ 添加更多选择子。
     • ii. 令 $d^{\mathsf{new}}=\mathsf{max}(d,d_j^{\mathsf{max}}-1)$。
     • iii. 如果对 $c$ 中任意 $i^{\prime }$ 有 $X_{j,i^{\prime }}$ 为 $\mathsf{true}$,或者 $d^{\mathsf{new}}+(\mathsf{len}(c)+1)>max\_degree$,跳出到外层循环。

       $d^{\mathsf{new}}+(\mathsf{len}(c)+1)$ 是把 $s_j$ 加入组合 $c$ 后所产生的任何约束的最大次数,包括选择子表达式。

     • iv. 令 $d:=d^{\mathsf{new}}$。
     • v. 把 $s_j$ 加入 $c$ 并令 ${\mathsf{added}}_j:=\mathsf{true}$。
   • d. 分配一个固定列 $q_c$,初始化为全零。
   • e. 对每个选择子 $s^{\prime }\in c$:
     • i. 用一个互不相同的索引 $k$ 标记 $s^{\prime }$,其中 $1\le k\le \mathsf{len}(c)$。
     • ii. 记录:在所有门约束中,$s^{\prime }$ 应被替换为 $q_c\cdot {\prod }_{1\le h\le \mathsf{len}(c),h\ne k}(h-q_c)$。
     • iii. 对每一个使 $s^{\prime }$ 在该行被启用的行 $r$,把值 $k$ 赋给该行 $r$ 上的 $q_c$。

上述算法实现于 halo2_proofs/src/plonk/circuit/compress_selectors.rs。 它由 halo2_proofs/src/plonk/circuit.rs 的 compress_selectors 函数使用,后者执行实际的替换。

编写电路以最大程度利用选择子合并

对于这项优化而言,一个电路尽可能使用简单选择子而非固定列是有益的。手动合并选择子通常没有好处,因为所得到的固定列无法参与自动合并。这意味着,要得到可比的结果,你将需要手动进行全局优化,而这会干扰可组合小工具(composable gadgets)的编写。

两个选择子是否在同一行上被启用(从而被阻止合并),取决于布局规划器(floor planner)如何排布各个区域(region)。当前已实现的布局规划器并不尝试把这一点纳入考虑。我们建议不要在此过分纠结——通过哄劝布局规划器来回挪动区域以改善合并所能获得的收益,很可能相对较小。