DAOrayaki |zkPairing:椭圆曲线配对的 zkSNARKs

本文我们介绍circom-pairing,一种在 Circom 用于椭圆曲线配对的 zkSNARK 电路的概念验证实现。

DAOrayaki |zkPairing:椭圆曲线配对的 zkSNARKs

本文我们介绍circom-pairing,一种在 Circom 用于椭圆曲线配对的 zkSNARK 电路的概念验证实现。

DAOrayaki DAO研究奖金池:

资助地址:  DAOrayaki.eth

投票进展:DAO Reviewer  2/0 通 过

赏金总量:75 USD

研究种类:NFT

原文作者:  Jonathan W., Vincent H., and Yi Sun

创作者:Skyhigh Feng@DAOrayaki.org

审核者:DAoctor, Yofu@DAOrayaki.org

原文:  zkPairing: zkSNARKs for Elliptic Curve Pairings

作者:

配对是许多加密协议的核心组成部分。本文我们介绍circom-pairing,一种在 Circom 用于椭圆曲线配对的 zkSNARK 电路的概念验证实现。

简介

基于配对的密码学(Pairing-based cryptography) (PBC)建立在一个叫做椭圆曲线配对(elliptic curve pairing)的数学对象存在的椭圆曲线密码学(elliptic curve cryptography)之上。虽然配对的定义相对复杂,但它们是零知识密码学现代发展的许多加密对象的基础: BLS 数字签名、 KZG 多项式承诺和 zkSNARKs。

由于 ZK 生态系统中的这个关键角色,在 zkSNARKs  中实现配对极大地扩展了可寻址密码构造的范围,并增加了 SNARKs 的反射能力。特别是,我们设想的应用程序的ZK 身份(ZK Identity) ,区块链扩容,和可编程的 SNARKs 。最后的“解锁”可能会带来一个未来,任何人都可以在运行中自由组合和联合不同的 SNARKs 。

由于配对涉及许多复杂的椭圆曲线操作,在 zkSNARK 中实现它们会带来许多挑战。首先,对于非自然域上的椭圆曲线算法,我们必须使用zk-ECDSA 的大整数和 ECC 优化,但是要适应我们的曲线和 BLS12-381的配对涉及到在域扩展上操作的事实。其次,Miller 的计算配对算法Miller's algorithm允许在标准计算模型中进行许多优化,我们将这些优化移植到 zkSNARK  设置中。最后,由于配对计算的复杂性,即使最终优化的电路也可能相当大,这意味着需要一些基础设施的最佳实践来适应  Circom  工具栈。

在这一系列的文章中,我们提出了一个在 BLS12-381曲线上的最优 Ate 配对的概念验证 Circom 实现,以及一个在 BLS 签名验证中的应用实例。然后,我们概述了其他潜在的应用,如递归 SNARK 和多项式承诺验证,我们认为这种方法很容易推广应用。

循环配对

我们实现了循环配对 circom-pairing 代码库,它为 BLS12-381 曲线上的以下操作提供未经审核的 ZK 电路:

● Tate 配对是最简单的椭圆曲线配对之一。该算法满足双线性特性,适用于密码学领域,对椭圆曲线的计算和算法的正确实现起到了很好的检验作用。

● 最佳配对:最佳配对是实践中最常用的配对。计算类似于Tate配对(使用Miller的算法,我们将在以后的文章中讨论) ; 然而,涉及的步骤较少,而每一步的算法更加复杂,最终的结果是一个较短的总计算。

BLS 签名验证(短公钥) : 签名验证允许检查一个BLS 签名. 给定签名 s,生成元 G,公钥 xG,和哈希 hash ,验证电路转换 hash 到椭圆曲线点 H(m),   使用maptoG2 下面的电路,然后验证 s 确实是由给定的公钥和消息生成的签名。BLS 签名验证涉及到评估两个最优的 Ate 配对来验证这一点 e(s,G) = e(H(m), xG) , e 表示最佳的 Ate 配对

● 散列hash到曲线: maptoG2 的 BLS 签名验证操作通过计算椭圆曲线上的点对。正在签名的消息必须首先散列成一个数值。然后,这个散列值被转换成椭圆曲线上的一个点; 散列到曲线电路执行这种转换。

更详细的文件,我们的电路在这里可用。这些电路没有经过审核,也不打算用作生产级应用的库。

演示

为了说明我们的电路,我们在zkpairing.xyz 实现了一个演示,它允许用户生成任何 BLS 签名(以特定的输入格式)有效性的证明。如果用户没有一个特定的 BLS 签名他们可以指定以太坊信标链上的任何块号,并且演示会将块数据解析为适当的格式,并生成一个验证该验证者签名的证明区块。对于每个证明,我们提供所有的数据-在三个小文件中-任何人都可以用来在自己的计算机上验证证明!

基准

 

验证

优化

tate配对

maptoG2

限制

19.2M

11.4M

24.7M

2M

电路编译

3.2h

1.9h

4.2h

23m

见证生成 C + + 编译

2h

1.1h

2.3h

9.3m

见证服务器

2.6m

1m

2.5m

33s 33

可信安装阶段2密钥生成

58m

32m

1.6h

4.5m

可信设置阶段2的贡献

25m

13.6m

29m

2.9m

证明钥匙大小

12G

6.5G

15G

1.2G

证明密钥验证

1.5h

43m

2.5h

6.2m

 证明时间(rapidsnark)

2m

52s

2.1m

6s

所有基准测试都运行在32核3.1 GHz、256G RAM、1T 硬盘和400G 交换机(AWS r5.8 xlarge 实例)上。

运行大型电路

请注意,验证和Tate 配对是非常大的电路,因此它们需要特殊的硬件和设置来运行。特别是,必须使用 C++ 生成见证服务器,使用 rapidsnark 进行证明,使用补丁版本的 Node.js而不使用垃圾收集生成密钥。所有这些都必须在具有大容量内存的机器上完成; 我们的设置工作流程在《大电路最佳实践》( Best Practices for Large Circuits )文档中有详细说明。

我们能用 zkPairing 做什么?

因为配对是许多加密协议的核心组成部分,所以用于配对计算的 zkSNARKs 允许我们将以下高级原语放入 SNARK 中:

● BLS 签名验证: Boneh-Lynn-Shacham (BLS)数字签名是一种基于椭圆曲线配对的签名方案。由于能够使用 BLS 有效地计算聚合签名和阈值签名,它目前被用于区块链,如 Etherum 2.0、 ZCash  和  Dfinity 。验证 BLS 签名涉及到一个配对检查,检查两个椭圆曲线配对是否相等,因此通过 zkPairing 直接启用。这解锁了潜在的可伸缩应用程序,比如轻型客户机和桥接的签名聚合。

● 递归 SNARK 验证: 因为 Groth16证明验证只涉及配对检查,所以 SNARK-ing 配对允许 SNARK-ing 整个验证算法,称为递归验证。这使我们能够构建一个 zkSNARK 的 zkSNARK 的... 无限广告,使开发人员能够构建不同的 SNARK 证明,而不是构建一个单一的大型 SNARK 和大大增加可能的 SNARK 的复杂性。我们正在调整我们的电路,以递归 Groth16验证 BN254,并希望在不久的将来发布一个概念证明。

● KZG 多项式承诺验证: KZG 多项式承诺是 PlonK 的基础,PlonK 是具有通用可信设置的新一代 zkSNARK 之一。因为验证 KZG 承诺涉及到一个配对检查,zkSNARK-ing 配对使我们能够验证任何建立在 SNARK 中的 KZG 承诺之上的东西,包括 PlonK 验证本身!

很快就会看到第2部分讨论了 zkPairing 的实现技术!

致谢

该项目是在 ZKxZK Gitcoin 基金的支持下,在0xPARC 的 ZK 身份工作组期间构建的。

我们借鉴并分享了很多与 circom-ecdsa 相关的技术,特别是在大整数和椭圆曲线算法的优化方面。例如,我们使用 xJsnark 的大整数乘法优化。

我们也从最初的创作者 Jordi Baylina 和 snarkjs 的研究中获益匪浅。他教了我们很多关于 circom/snarkJS 工具栈的知识,并分享了很多关于如何有效地构建大型 ZK 电路的见解。


通过 DAO,研究组织和媒体可以打破地域的限制,以社区的方式资助和生产内容。DAOrayaki将会通过DAO的形式,构建一个代表社区意志并由社区控制的功能齐全的去中心化媒体。欢迎通过文末方式提交与DAO、量子计算、星际移民、DA相关的内容,瓜分10000USDC赏金池!欢迎加入DAOrayaki社区,了解去中心化自治组织(DAO),探讨最新话题!

官方网站:https://daorayaki.org

Media:https://media.daorayaki.org

Discord server: https://discord.gg/wNUPmsGsa4

Medium: https://medium.com/@daorayaki

Email: daorayaki@dorafactory.org

Twitter: @daorayaki_

微信助手:DAOrayaki-Media

小宇宙:DAOrayaki

详情请参考:

Dora Factory支持去中心化DAO研究组织DAOrayaki

对DAOrayaki第一阶段的回顾--去中心化媒体的先驱

DAOrayaki |DAOrayaki 开启去中心化治理2.0时代

DAOrayaki |风险投资的范式转移:无限主义基金和无限游戏

DAOrayaki |DAOrayaki dGov 模型:基于Futarchy的正和游戏

更多关于DAO的文章,关注Dorafactory,查看往期文章。

DAOrayaki

DAOrayaki is a decentralized media and research organization that is autonomous by readers, researchers, and funders.