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 的网站上有预印版,可以方便地获取。论文主要由三部分组成。

  • 第一部分是 Inner-Product Argument, 这部分几乎没有实用价值,但是它是后面两个零知识证明的基础部分。其中,用到了一个技巧,可以递归地将证明的尺寸压缩到对数级别,证明的验证时间亦然。
  • 第二部分是范围证明(range proof),其作用是证明一个数在 0 到 2^n-1 的范围内。这个协议的功能很有限,但是在某些应用场景下很有价值。例如,在 MimbleWimble 协议中,交易者通过 Pedersen 承诺来实现加减法同态,这个时候,就只需要用到范围证明来保证交易金额非负。
  • 第三部分就是对任意算术电路证明。包括 SHA-256 函数在内的任意函数,都可以转化为由有限域上的加法和乘法组成的电路。然后,把电路转化为 R1CS 的形式,就可以进行零知识证明了。
  • 最后,通过 Fiat-Shamir heuristic,范围证明和算术电路证明都可以很方便地写成非交互式。

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

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

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

  • Module bulletproofs::r1cs
    Module bulletproofs::notes::r1cs_proof
    这两篇文章来自 Dalek 的 bulletproofs 开发人员。第一篇是一个例子,讲了一个最简单的 bulletproofs 的算术电路应该怎么写、怎么证明、怎么验证。第二篇则是介绍 R1CS 的原理,以及实现过程。相比原论文,这两篇文章从工程角度出发,读起来应该轻松一些。
  • Programmable Constraint Systems for Bulletproofs
    这篇文章也来自 Dalek 的开发人员,是一个比较简略的文档。基本可以看成是上面两篇文章的小结。
  • Zero knowledge proofs using Bulletproofs
    这篇文章中给出了一个更详尽的构建电路的例子,这篇文章还有一个配套的代码仓库,给出了哈希函数、Merkel 树等模块。
  • Designing efficient R1CS Circuit
    一个介绍 R1CS 的 ppt。这个文档站的角度比较高,没有涉及到太多的细节。
  • ZkVM
    这个项目我没有细看,但是看上去是一个很有野心的项目,想要做出用于零知识证明的”交易虚拟机“。
  • MimbleWimble 和 Grin 简介
    这篇文章本身和 bulletproofs 关系不大,主要是介绍了 MimbleWimble 的原理。可以看看 MimbleWimble 是怎么把范围证明应用起来的。
  • libsnark tutorial
    libsnark/gadgetlib1/gadgets/hashes/sha256/
    这两个代码都是关于 zk-SNARKs 的一个实现: libsnark。第一个是教程,第二个是 SHA-256 哈希的实现。虽然 zk-SNARK 和 bulletproofs 原理不尽相同,但是都是基于算术电路和 R1CS,因此具有参考价值。

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注