BSV上的高效 zk-SNARK技术解释
最近,我们在 sCrypt 中实现了 zk-SNARKs,并在 BSV 上运行它。更具体地说,我们实现了 Groth16 算法的验证器,它允许直接在链上验证零知识证明。本文深入探讨了一些细节,阐明了如何在 BSV 上有效地实施其他高级加密技术。
椭圆曲线上的双线性对
Groth16 证明尺寸极小,并且可以快速验证。我们选择了最佳的 Ate 配对,因为它的效率已在实践中得到证明。
我们在配对友好的椭圆曲线 BN256(也称为 ALT_BN128 和 BN254)上实现它。我们使用 BN256 是因为
- 有流行的 ZKP 工具(如 ZoKrates 和 Circom)支持;
- 与以太坊等其他区块链兼容。
米勒算法用于有效计算最优 Ate 配对。在高层次上,它由两部分组成:
- 米勒循环:递归计算两个输入点
f(P, Q)
的中间函数 - 最终取幂:将
f
提高到大幂c
减少到3个配对
验证者需要检查以下等式是否成立。
元组 (A, B, C)
是证明,(α, β, ϒ, δ)
是验证密钥,L
来自公共输入。我们总共有 4 对 配对。我们注意到 α
和 β
在设置时是已知的,因此我们预先计算了第二对,并将 α
和 β
替换为验证密钥的一部分,从而减少了一对配对的技算。
一个单一的最终幂
等式 1 可以改写为:
它又可以写成如下,因为 e
是双线性的,我们可以将指数 (-1)
移动到括号中。
插入等式 2,我们得到:
我们不需要计算 4
次最终的幂运算,幂运算是计算密集型的,我们最终只需要执行一次。
循环展开
在 sCrypt/Script 中,所有 if
分支都包含在交易中并产生交易费用,无论它们稍后是否执行。在米勒循环中,sᵢ
在编译时是已知的。我们展开循环并避免在第 5
行和第 7
行分支。
扩展域 twist
直接计算两点的配对需要在扩展域 Fq¹²
上进行椭圆曲线算法,这非常复杂且效率低下。我们使用 twist 将其映射到 Fq²
,从而大大提高了效率。请参阅这篇文章以获得更详细的解释。
概括
经过所有这些优化,我们能够将配对的脚本大小减少 100
倍至 5MB
。我们正在探索更多优化以进一步减少它。完整版本的代码可以在 GitHub 上找到。
传统上,优化程序的目标是最小化其 CPU 和/或内存使用量。在 BSV 中,交易费用与包含脚本的交易大小成正比,目标是最小化脚本大小。如何针对这一目标进行优化是一个有趣的开放课题,值得进行新的研究。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgjhgcc
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13