在设计zkvm电路时,由于需要确定很多自定义门,所以引入了很多二进制选择器(binary selector)。
在设计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
从上面的例子中,我们可以看到当我们定义一个新的自定义门时,需要引入一个选择器列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会增加证明者和验证者的工作量。
因此,需要优化选择器个数,同时必须满足以下两个条件:
在“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)进行承诺即可。但值得注意的是,这种方法也增加了约束的程度。
到目前为止,我们已经做到了两点:
当然,协议中对约束的度是有限制的,因此参与组合的选择器数量是有界的,即单个组合选择器的数量取决于约束多项式t的Degree和max_degree的边界值*(x)。
因此,需要更多的组合列,反正数量还是比原来的少很多。
Source:https://hackernoon.com/how-to-design-the-zkvm-circuit
ChinaDeFi - ChinaDeFi.com 是一个研究驱动的DeFi创新组织,同时我们也是区块链开发团队。每天从全球超过500个优质信息源的近900篇内容中,寻找思考更具深度、梳理更为系统的内容,以最快的速度同步到中国市场提供决策辅助材料。
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!