一个更优的零知识证明:Bulletproofs
发布于 3 个月前 作者 liuchengxu 202 次浏览 来自 其他链技术

翻译作者: 许莉

原文地址: Bulletproofs Faster Rangeproofs and Much More

在2015年我们宣布机密交易(CT)作为侧链Elements Alpha的主要特征。该特征用Pedersen commitments取代了交易金额,这种一种隐藏金额的加密工具,同时保留了任何人验证在特定交易内余额的能力。

CT面临的主要难题是让它交易变得非常大而且验证缓慢,因为它要求每个交易输出包含一个rangeproof,这是一种零知识证明,证明金额太小而不会溢出。普通数字签名小于100个字节,并且只需不到100微秒的时间就可以验证,而 rangeproofs的大小是几千个字节,并需要几个毫秒才能验证。实际上,rangeproofs是使用它们的任何交易中绝大部分的交易数据。

尽管我们的rangeproofs,基于Borromean环形签名,在文献中是最快的和最小的,但对于我们需要的范围大小(range sizes)和无信任的环境下,它们仍然非常的大。

自从2015年来,我们一直都在努力提高rangeproofs的效率。在2017年初,Adam Back发现rangeproofs减小了24%,不过验证速度并没有提高。在这段期间,我们曾向我们的朋友和同事,密码学家Dan Boneh和在斯坦福大学的BenediktBünz提到这个问题,他们对改善的空间都相当的有信心。

他们最终震惊了我们。

更小,更快,更强健

根据Bootle等人在2016年基于离散对数的零知识证明的空间效率方面的改进,Bulletproofs是一种更加空间高效的零知识证明的形式。重要的是,为了我们的目的,这些证明还具有对提交值如Pedersen commitments和公钥的原生支持。这让我们可以在通用的零知识框架下实现诸如rangeproofs之类的功能,而不用在零知识中实现复杂的椭圆曲线算法。

更强健。为了限制交易大小,我们老版本的rangeproofs限制输出范围大小为2^32。这限制了输出大约到43 BTC,不过这可以通过将证明的粒度从1聪减少到10聪或者100聪来增加,或者通过从零开始增加最小值来增加。这些调整是可能的,但是使用了显示的金额,限制了系统提供的隐私。

这些32位的rangeproofs大小大约为2.5 KiB。使用Adam的优化,它们将有2 KiB 的大小。使用Bulletproofs,它们应该是610字节。有了这么小的大小,我们可以将范围(range)加倍到64位,从而无需进行任何的非隐私调整。这样的话,就会将610字节增加到1220字节,是吗?不是,实际上,64位的Bulletproof rangeproofs 仅仅只有674字节。

更小。我们将范围(range)的大小增加了一倍,但证明的大小只增加了64个字节的原因是:它们以对数级增长。这是通过使用Bootle等人在2016年论文中的内部产品参数的变体来完成的。(Jonathan Bootle也帮助了Benedikt和Dan开发Bulletproofs。 )具体来说,论文中描述的对数大小的内部产品参数在Bulletproofs中进一步降低了,从6log(N)曲线点降到2log(N)。

相同的技巧可以将一个交易内多个rangeproofs整合到一个中,同样只会增加很少的字节数。2个rangeproofs的整合是738字节,4个则是802字节,8个是866字节。8个64位经典rangeproofs将会超过40000字节。

更快。这种节省空间很大,但是我们对该技术的初步分析显示验证速度会比老版的rangeproofs慢。似乎验证一个64位的证明需要超过200个标量点乘法,每个都是繁重的50微秒事务,而老版的rangeproofs只需要128个标量点乘法。

但是经过进一步的分析后,我们可以组合很多乘法,将总数减少到147个。更重要的是,我们意识到,与老版的rangeproofs不同,这些乘法都是不依赖对方的,所以我们可以在一个批量中完成它们。作为我们汇总签名工作的一部分,我们知道如何快速批量相乘。 我和Pieter Wuille,Greg Maxwell,Jonas Nick,Peter Dettman在这个问题上花费了几个月的时间,最终将147个乘法的速度降低到每个只需15.5微秒,让Bulletproof的总验证时间降到2.3 ms,而老版的证明需要5.8 ms。

在速度上已经不仅增加了一倍,而且由于我们的批量乘法随着你提供的点越多速度越快,所以整合的性能数字就更加令人印象深刻。8个64位Bulletproofs的整合可以在11.5 ms内验证完,而对于老版的证明需要46.8 ms,速度超过了4倍。

不过它能变得更好。Bulletproofs支持非常高效的批量验证形式。在我们需要完成的147次乘法中,其中130次在每个Bulletproof中使用相同的点,这意味着在批量验证期间,这130次乘法是可以组合的,剩下只有17次是新的乘法。实际上,这种小成本仅仅以对数级增加:对于2个范围(ranges)的整合,每个额外的证明需要19个额外的点,而4个范围(ranges)的整合,每个证明需要21个点。

注意我们引入了两个相似但是独立的概念:整合(aggregation)是指证明程序将多个rangeproofs组合成1个;而批量处理(batching)是指验证程序同时检测多个单独的证明。

这意味着两个64位的rangeproofs可以在2.7 ms内完成验证,或者每个范围(range)1.4 ms。500个rangeproofs可以在130 ms内完成验证,或者每个范围(range)0.26 ms,这比老版的证明提高了23倍。不过由于整合,它还可以变的更加可观。500个8个一整合的rangeproofs(一共是4000个范围(ranges))可以在305 ms内验证完,或者每个范围 76 微秒,比老版的rangeproofs提高了75倍。

随着日益高效的标量点乘法不再是主导效应,这种影响最终会围绕64个证明的整合最大化。在这一点上,我们可以以每个范围(range)46微秒来批量验证,速度提高了125倍。作为参考,椭圆曲线数字签名算法(ECDSA)签名大约需要55微秒,所以在这种级别的整合下,rangeproofs甚至不是交易验证的主要部分。当然,我们不太可能在区块链上看见64个输出交易,不过这种速度在非区块链环境中(如 Provisions)是可能的。

这种验证同样也是节约内存的,验证单个rangeproof需要 100 KiB,随着大小而增加减。

你可以证明任何事情(如果它是真的话)

Bulletproofs比rangeproofs更加的通用。它们可以被用来在零知识中证明任意的陈述。它们与SNARKs或STARKs相当,不过它们原生支持椭圆曲线(EC)公钥和Pedersen commitments(因此通常不需要在程序中实现EC算法)。此外,与SNARK不同的是,Bulletproofs在无信任环境的标准猜想下拥有完整的128位安全性。与STARK不同,它们在典型的计算机硬件上足以快速证明和验证合理大小的问题。

作为一个具体的例子,考虑SHA2压缩功能的一次运行。我们的证明程序需要少于 30 MiB的内存和大约21秒来证明SHA2原像的知识。验证需要大约23 MiB的内存和75 ms,但是我们可以用大约每个证明5 ms和13.4 KiB批量验证额外的证明。

我们的证明程序比SNARK更节省内存:在相同的系统中,SHA2的一个SNARK证明只需要4秒但是要75 MiB内存。验证时,每个电路需要大量的一次性预计算(需要被证明的陈述),然后只需要3-5 ms和很少的内存就可以验证。这些数字不会随着电路的增加而增加,所以对于超过几千门的电路,即使与我们的批量验证相比,SNARK也明显是赢家。不幸的是,这是以可信赖的环境和新的加密猜想为代价的。

在证明程序和验证程序上,Bulletproofs仍有很大的优化空间。

验证任意陈述句的能力——不管是Bulletproofs,SNARKs或者STARKs,都有很多的应用。它可以用于实现普通的数字签名,包括(可追踪的)环形签名和阈值签名,对于大型环来说,在验证时间和证明大小方面它都比传统方案要高效。它的使用不限于此,它还可以用来可靠的销售数独问题,可以用于多方计算,即使有秘密数据的情况下还是可以证明每方都是诚实行事。(特别是在MuSig这样的多重签名方案中,这允许使用确定性的随机数生成,而不需要签名者维护状态或容易受到随机重用攻击。)它还可以用来证明哈希原像(preimages)。

后一种应用,哈希原像,是特别有趣的,因为它可以用来创建零知识Merkle证明,包含在大规模集合(有数百万甚至数十亿元素)的高效证明。我们将在未来的文章中探讨这一点。

总结

  • Bulletproofs是通用零知识证明(类似SNARKs)

  • 它们可以用来扩展多方协议,如多重签名或零知识应急支付

  • Bulletproofs提供了一个更加高效的CT rangeproofs版本(批量验证时,速度提高超过23倍)

  • 这些rangeproofs可以在交易中进行整合,然而大小只以对数级增长

  • 通过充分的整合,例如Provisions,批量验证的速度比老版的证明快了超过130倍

我们很感谢Bootle等人开发的内部产品参数,它引导了我们。同样也感谢Benedikt Bünz和Dan Boneh,我们的合著者,他们做了大量的创造性工作。感谢Sean Bowe和Daira Hopwood为优化算术电路而做的研究。

链接

Full paper

Bulletproofs - Stanford Applied Crypography

Benedikt Bünz talk at BPASE ‘18

Andrew Poelstra talk at Milano Bitcoin meetup (slides)

回到顶部