最近,我们在 sCrypt 中实现了 zk-SNARKs,并在比特币上运行它。更具体地说,我们实现了Groth16算法的验证器,它允许直接在链上验证零知识证明。本文深入探讨了一些细节,阐明了如何在比特币上有效地实施其他高级加密货币技术。
椭圆曲线上的双线性对
Groth16 具有极小的证明尺寸和快速验证。配对是 Groth16 验证器算法中最昂贵的部分。我们选择了最优的 Ate 配对,因为它的效率已经在实践中得到证明。
我们在配对友好的椭圆曲线 BN256(也称为 ALT_BN128 和 BN254)上实现它。我们使用 BN256 是因为 1) 受流行的 ZKP 工具(如 ZoKrates 和 Circom)支持;2) 与以太坊等其他区块链兼容。
米勒算法用于有效计算最优 Ate 配对。在高层次上,它由两部分组成:
- 米勒循环:递归计算两个输入点f(P, Q)的中间函数
- 最终取幂:将f提高到大幂c
等式 1最佳配对
减少到3对
验证者需要检查以下等式是否成立。
等式 2
我们总共有 4 对。我们注意到α和β在设置时是已知的,因此我们预先计算了第二对并将其添加为验证密钥的一部分,从而保存了一对。
一个单一的最终幂
方程。1 可以改写为:
它又可以写成如下,因为e是双线性的,我们可以将指数 ( -1)移动到括号中。
双线性
插入方程式。2,我们得到:
我们不需要计算4次最终的幂运算,这是计算密集型的,我们最终只需要执行一次。
循环展开
在 sCrypt/Script 中,所有if分支都包含在交易中并产生交易费用,无论它们是否稍后执行。在米勒循环中,sᵢ在编译时是已知的。我们展开循环并避免在第 5 行和第 7 行分支。
扩展场扭曲
直接计算两点的配对需要在扩展域Fq¹²上进行椭圆曲线算法,这非常复杂且效率低下。我们使用扭曲将其映射到Fq²,从而大大提高了效率。请参阅这篇文章以获得更详细的解释。
概括
经过所有这些优化,我们能够将配对的脚本大小减少100 倍至5MB。我们正在探索更多优化以进一步减少它。代码的完整版本可以在GitHub上找到。
传统上,优化程序的目标是最小化其 CPU 和/或内存使用量。在比特币中,交易费用与包含脚本的交易大小成正比,目标是最小化脚本大小。如何针对这一目标进行优化是一个有趣的开放课题,值得进行新的研究。
资讯来源:由a0资讯编译自THECOINREPUBLIC。版权归作者A0资讯所有,未经许可,不得转载