Bulletproofs 学习笔记

虽然区块链目前还没有重量级的落地应用,但最近几年的火热确实催生出了一些不错的密码学研究,bulletproofs 就是一例。

零知识证明在区块链领域因交易隐私而受到关注,最著名的应用是 Zerocash,后来演变成了 加密货币 ZCash,又被称为“零币”。Monera 也是一种具有隐私保护功能的加密货币,但是其核心是环签名,故这里不在赘述。

ZCash 中应用到的零知识证明协议叫做 zk-SNARKs,这是一种非常新的零知识证明技术,最近几年才发展起来。它的特点是,可以对任意的约束进行证明,因为理论上说,任何计算,都可以转化为有限域上的加法和乘法。zk-SNARKs 的特点是,生成零知识证明的时间非常长,但是验证所需要的时间非常短,只需要常数时间。因此,zk-SNARKs 非常适合应用于区块链(因为交易验证是区块链应用的重要瓶颈)。

但是,zk-SNARKs 需要一个可信的初始化(trusted setup),甚至是安全多方计算,来生成公共参数。这是一个非常麻烦的步骤。Bulletproofs 就是为解决这个问题而生的。Bulletproofs 不需要麻烦的初始化,但是它的证明尺寸随着待证明电路的复杂度而对数上升。虽然相比起 zk-SNARKs 来,没有那么高效,但是也在可以接受的范围内。

Bulletproofs 的论文发表在了 IEEE S&P 2018 上,论文在 IACR 的网站上有预印版,可以方便地获取。论文主要由三部分组成。

MimbleWimble 项目基于比特币的 secp256k1 实现了 bulletproofs 中的范围证明。但是,没有实现对任意算术电路的证明。如果只需要范围证明的话可以拿来一用。此外,Dalek 有一个 Rust 实现的 Bulletproofs 库,这个库的算术电路证明模块还处在实验阶段,尚未达到生产阶段,不过我大致看了一下代码,基本是可用的。最后还有一个 Haskell 的库,不过 Haskell 语言不适合生产,而且这个库的完成度和生态环境也不是很完善,感觉比不上 Rust 语言的那个库。

如果想让 bulletproofs 的项目落地的话,感谢开源,证明部分已经有成熟的算法库了,最大的难点在于怎么把需求写成电路。

我目前搜集到的相关资料有这些:

最后是一点题外话。SHA-256 用算术电路实现起来非常复杂,因此有人就想到了可不可以用其他的哈希蛤数。目前我看到的有两个这样类似的哈希函数,一个是 MiMC,一个是 Poseidon。这两个哈希函数都是特意为零知识证明而优化过的。虽然目前这些哈希函数还没有被大量应用,不过,如果今后零知识证明相关的项目真的能遍地开花的话,那么这些对零知识证明友好的哈希函数,其未来可期。


©️ 2017-2019 奈卜拉

go back