定制门 在设计 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

Trace

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Architecture

2022 - HackerNoon Contributor of the Year - Blockchain

2022 - HackerNoon Contributor of the Year - Optimization

2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

該音頻是用故事的原始語言製作的！

太長; 讀書

如何设计 ZKVM 电路

如何设计 ZKVM 电路

About Author

註釋

標籤

这篇文章刊登在

Related Stories

架构师指南：构建 AI/ML 数据湖参考架构

使用这 18 种开发工具来提高你的工作效率 🚀🔥

Telegram：加密岛通往大陆的桥梁

释放人工智能的力量。前沿技术的系统评价：摘要与介绍

架构师指南：构建 AI/ML 数据湖参考架构

使用这 18 种开发工具来提高你的工作效率 🚀🔥

Telegram：加密岛通往大陆的桥梁

释放人工智能的力量。前沿技术的系统评价：摘要与介绍

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps