技术:如何设计zkVM电路

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

1.jpg

自定义门

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

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

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

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

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

2.jpg

对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)

3.jpg

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

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

4.jpg

如果我们为选择器s {add}, s {div}, s {cube}, s {sqrt}定义一个集合{s {add}, s {div}, s {cube}, s {sqrt}(称为不相交,即使可能的行之间没有公共点),那么根据列q的定义,我们有:

5.jpg

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

6.jpg

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

7.jpg

将上述公式展开为:

8.jpg

9.jpg

则得到真值图:

10.jpg

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

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

...

我们可以将约束重写为:

11.jpg

对于上面的约束条件,我们只需要对多项式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

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

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