技术：如何设计zkVM电路

自定义门

在设计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 {div} = {0,0,...1,...0}$。当它转换为多项式 s {div}(x) 时，上式将是：

s_{div}(x) ⋅ (w_0(x) ⋅ w_3(x) - w_2(x)) = 0

s_{div}(x) ⋅ (w_1(x) ⋅ w_3(x) - 1) = 0

组合选择器 （Combined Selector）

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

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

s {add}(x) ⋅ t {add}(x) = 0

s {div}(x) ⋅ t {add}(x) = 0

s {cube}(x) ⋅ t {cube}(x) = 0

s {sqrt}(x) ⋅ t {sqrt}(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 {add}， s {div}， s {cube}， s {sqrt}定义一个集合{s {add}， s {div}， s {cube}， s {sqrt}(称为不相交，即使可能的行之间没有公共点)，那么根据列q的定义，我们有：

在这里，基于列q定义一个新的selector polynomial形式，对于数字kselector polynomial，我们有:

例如，对于约束：s_add⋅t_add(x) = 0，可以改写为:

将上述公式展开为:

则得到真值图:

可以看到，它所做的事情与原始选择器相同。因此，对于约束:

s {add}(x) ⋅ t {add}(x) = 0

s {div}(x) ⋅ t {add}(x) = 0

s {cube}(x) ⋅ t {cube}(x) = 0

s {sqrt}(x) ⋅ t {sqrt}(x) = 0

...

我们可以将约束重写为：

对于上面的约束条件，我们只需要对多项式q(x)进行承诺即可。但值得注意的是，这种方法也增加了约束的程度。

到目前为止，我们已经做到了两点：

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

当然，协议中对约束的度是有限制的，因此参与组合的选择器数量是有界的，即单个组合选择器的数量取决于约束多项式t的Degree和max_degree的边界值*(x)。

因此，需要更多的组合列，反正数量还是比原来的少很多。

Source：https://hackernoon.com/how-to-design-the-zkvm-circuit

关于

ChinaDeFi - ChinaDeFi.com 是一个研究驱动的DeFi创新组织，同时我们也是区块链开发团队。每天从全球超过500个优质信息源的近900篇内容中，寻找思考更具深度、梳理更为系统的内容，以最快的速度同步到中国市场提供决策辅助材料。

本文首发于：https://mp.weixin.qq.com/s/oBdkQHczb5cS6vBBkreeUg