如何设计 ZKVM 电路

定制门

在设计 zkvm 电路时，由于确定了很多自定义门，所以引入了很多二元选择器。

以（场）划分门为例，我们计划设计一个门来验证关系 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

组合选择器

从上面的例子可以看出，当我们定义一个新的自定义门时，需要引入一个选择器列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

...

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

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

1. 选择多项式的含义没有损失，即只能使用特定的门；

   
   

2. 更少的选择多项式

在“Plonky2: Fast Recursive Arguments with PLONK and FRI”（ https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf ）中，有一种优化方法“Binary-Tree Based Selector” ，这将选择多项式的数量减少到 log(k)，k 是自定义门的数量。

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

为了更容易理解，我们举个简单的例子（具体算法请参考Selector combination - The halo2 Book ）

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

因此，这会增加证明者和验证者的工作量。这里我们定义一个新列 q，满足：

如果我们为选择器 s_{add} 定义一个集合 {s_{add}, s_{div}, s_{cube}, s_{sqrt}}（称为不相交，即使可能的行之间没有公共点） , s_{div}, s_{cube}, s_{sqrt} 然后根据列 q 的定义，我们有：

在这里，基于列 q 定义一个新的选择多项式形式，对于数字 k 选择多项式，我们有：

例如，对于约束： 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) 进行承诺。但值得注意的是，这种方法也增加了约束的程度。

至此，我们实现了上面提到的两点：

1. 选择多项式的含义没有损失，即只能使用特定的门；

   
   

2. 更少的选择多项式

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

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

更多处理案例和算法细节请参考选择器组合-光环之书。

参考

1. “光环2书”，

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

   
   

2. 多边形零团队，“Plonky2：使用 PLONK 和 FRI 的快速递归参数”， https ://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf，访问时间：2022-02-06