自定义门

在设计zkvm电路时，由于需要确定很多自定义门，所以引入了很多二进制选择器（binary selector）。

以(场)划分门（（field）division gate））为例，我们计划设计一个门来验证q, x, y三个元素之间q = x/y的关系是成立的。

为方便起见，我们不会在电路层面进行场划分操作，而是通过验证以下逻辑关系来实现。

X * inv_y = q inv_y?y = 1 / /确保y≠0

在这两个要素之间，存在着平等的关系。因此，我们有如下的Trace表:

对w_0,w_1,w_2,w_3列定义多项式w_0(x)， w_1(x)， w_2(x)， w_3(x)，则除法运算对应的行应满足：

w_0(x) . w_3(x) - w_2(x) = 0 w_1(x) . w_3(x) - 1 = 0

为了确保在相应的行中可以满足上述关系，需要一个选择器进行相应的划分来约束验证。

因此，我们引入了一个新列 s= $。当它转换为多项式 s(x) 时，上式将是：

s_(x) ? (w_0(x) ? w_3(x) - w_2(x)) = 0

s_(x) ? (w_1(x) ? w_3(x) - 1) = 0

组合选择器 （Combined Selector）

从上面的例子中，我们可以看到当我们定义一个新的自定义门时，需要引入一个选择器列s*来对应这个门。

如果我们用t * (x)表示门对应的约束多项式，我们最终可以得到以下约束：

s(x) ? t(x) = 0

s(x) ? t(x) = 0

s(x) ? t(x) = 0

s(x) ? t(x) = 0

...

由于证明者在生成证明的过程中需要对所有多项式进行承诺，引入过多的selector polynomial会增加证明者和验证者的工作量。

因此，需要优化选择器个数，同时必须满足以下两个条件：

selector polynomial的含义没有损失，即只能使用特定的门;

更少的selector polynomial

在“Plonky2：快速递归参数与PLONK和FRI”(https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf)中，有一个优化方法“Binary-Tree Based Selector”，它将selector polynomial的数量减少到log(k)， k是自定义门的数量。

在Halo2的论文中，zcash团队提出了一种新的优化方法，可以实现更少量的多项式个数(与约束多项式 t?(x) 和为约束多项式 max_degree 设置的参数相关)。

为了更容易理解它，让我们举一个简单的例子(对于特定的算法，请参阅Selector combination - The halo2 Book)

我们可以看到，我们为4种自定义门设置了4个选择器列，就像前面提到的，这并不是我们想要的。

这将增加验证者和验证者的工作量。这里我们定义一个新的列q，满足:

如果我们为选择器s， s， s， s定义一个集合， s

， s， s(称为不相交，即使可能的行之间没有公共点)，那么根据列q的定义，我们有：