定制门 在设计 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 ... 由于证明者需要在证明生成过程中对所有多项式进行承诺,引入过多的选择多项式会增加证明者和验证者的工作量。 因此,需要优化选择器数量,同时满足以下两个条件: 选择多项式的含义没有损失,即只能使用特定的门; 更少的选择多项式 在“Plonky2: Fast Recursive Arguments with PLONK and FRI”( )中,有一种优化方法“Binary-Tree Based Selector” ,这将选择多项式的数量减少到 log(k),k 是自定义门的数量。 https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf 在 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) 进行承诺。但值得注意的是,这种方法也增加了约束的程度。 至此,我们实现了上面提到的两点: 选择多项式的含义没有损失,即只能使用特定的门; 更少的选择多项式 当然,协议中对受约束的Degree有限制,所以参与组合的选择器数量是有界的,即单个组合选择器的数量取决于约束多项式t的Degree和max_degree的边界值*(x)。 所以需要更多的组合列,反正数量还是比原来的少很多。 更多处理案例和算法细节请参考 。 选择器组合-光环之书 参考 “光环2书”, https://zcash.github.io/halo2/design/implementation/selector-combining.html 多边形零团队,“Plonky2:使用 PLONK 和 FRI 的快速递归参数”, ://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf,访问时间:2022-02-06 https