在2015年我們宣布機(jī)密交易(CT)作為側(cè)鏈Elements Alpha的主要特征。該特征用Pedersen commitments取代了交易金額，這種一種隱藏金額的加密工具，同時保留了任何人驗(yàn)證在特定交易內(nèi)余額的能力。

CT面臨的主要難題是讓它交易變得非常大而且驗(yàn)證緩慢，因?yàn)樗竺總€交易輸出包含一個rangeproof，這是一種零知識證明，證明金額太小而不會溢出。普通數(shù)字簽名小于100個字節(jié)，并且只需不到100微秒的時間就可以驗(yàn)證，而 rangeproofs的大小是幾千個字節(jié)，并需要幾個毫秒才能驗(yàn)證。實(shí)際上，rangeproofs是使用它們的任何交易中絕大部分的交易數(shù)據(jù)。

盡管我們的rangeproofs，基于Borromean環(huán)形簽名，在文獻(xiàn)中是最快的和最小的，但對于我們需要的范圍大小(range sizes)和無信任的環(huán)境下，它們?nèi)匀环浅５拇蟆?/p>

自從2015年來，我們一直都在努力提高rangeproofs的效率。在2017年初，Adam Back發(fā)現(xiàn)rangeproofs減小了24%，不過驗(yàn)證速度并沒有提高。在這段期間，我們曾向我們的朋友和同事，密碼學(xué)家Dan Boneh和在斯坦福大學(xué)的BenediktBünz提到這個問題，他們對改善的空間都相當(dāng)?shù)挠行判摹?/p>

他們最終震驚了我們。

更小，更快，更強(qiáng)健

根據(jù)Bootle等人在2016年基于離散對數(shù)的零知識證明的空間效率方面的改進(jìn)，Bulletproofs是一種更加空間高效的零知識證明的形式。重要的是，為了我們的目的，這些證明還具有對提交值如Pedersen commitments和公鑰的原生支持。這讓我們可以在通用的零知識框架下實(shí)現(xiàn)諸如rangeproofs之類的功能，而不用在零知識中實(shí)現(xiàn)復(fù)雜的橢圓曲線算法。

更強(qiáng)健。為了限制交易大小，我們老版本的rangeproofs限制輸出范圍大小為2^32。這限制了輸出大約到43 BTC，不過這可以通過將證明的粒度從1聰減少到10聰或者100聰來增加，或者通過從零開始增加最小值來增加。這些調(diào)整是可能的，但是使用了顯示的金額，限制了系統(tǒng)提供的隱私。

這些32位的rangeproofs大小大約為2.5 KiB。使用Adam的優(yōu)化，它們將有2 KiB 的大小。使用Bulletproofs，它們應(yīng)該是610字節(jié)。有了這么小的大小，我們可以將范圍(range)加倍到64位，從而無需進(jìn)行任何的非隱私調(diào)整。這樣的話，就會將610字節(jié)增加到1220字節(jié)，是嗎？不是，實(shí)際上，64位的Bulletproof rangeproofs 僅僅只有674字節(jié)。

更小。我們將范圍(range)的大小增加了一倍，但證明的大小只增加了64個字節(jié)的原因是：它們以對數(shù)級增長。這是通過使用Bootle等人在2016年論文中的內(nèi)部產(chǎn)品參數(shù)的變體來完成的。（Jonathan Bootle也幫助了Benedikt和Dan開發(fā)Bulletproofs。 ）具體來說，論文中描述的對數(shù)大小的內(nèi)部產(chǎn)品參數(shù)在Bulletproofs中進(jìn)一步降低了，從6log(N)曲線點(diǎn)降到2log(N)。

相同的技巧可以將一個交易內(nèi)多個rangeproofs整合到一個中，同樣只會增加很少的字節(jié)數(shù)。2個rangeproofs的整合是738字節(jié)，4個則是802字節(jié)，8個是866字節(jié)。8個64位經(jīng)典rangeproofs將會超過40000字節(jié)。

更快。這種節(jié)省空間很大，但是我們對該技術(shù)的初步分析顯示驗(yàn)證速度會比老版的rangeproofs慢。似乎驗(yàn)證一個64位的證明需要超過200個標(biāo)量點(diǎn)乘法，每個都是繁重的50微秒事務(wù)，而老版的rangeproofs只需要128個標(biāo)量點(diǎn)乘法。

但是經(jīng)過進(jìn)一步的分析后，我們可以組合很多乘法，將總數(shù)減少到147個。更重要的是，我們意識到，與老版的rangeproofs不同，這些乘法都是不依賴對方的，所以我們可以在一個批量中完成它們。作為我們匯總簽名工作的一部分，我們知道如何快速批量相乘。 我和Pieter Wuille，Greg Maxwell，Jonas Nick，Peter Dettman在這個問題上花費(fèi)了幾個月的時間，最終將147個乘法的速度降低到每個只需15.5微秒，讓Bulletproof的總驗(yàn)證時間降到2.3 ms，而老版的證明需要5.8 ms。

在速度上已經(jīng)不僅增加了一倍，而且由于我們的批量乘法隨著你提供的點(diǎn)越多速度越快，所以整合的性能數(shù)字就更加令人印象深刻。8個64位Bulletproofs的整合可以在11.5 ms內(nèi)驗(yàn)證完，而對于老版的證明需要46.8 ms，速度超過了4倍。

不過它能變得更好。Bulletproofs支持非常高效的批量驗(yàn)證形式。在我們需要完成的147次乘法中，其中130次在每個Bulletproof中使用相同的點(diǎn)，這意味著在批量驗(yàn)證期間，這130次乘法是可以組合的，剩下只有17次是新的乘法。實(shí)際上，這種小成本僅僅以對數(shù)級增加：對于2個范圍(ranges)的整合，每個額外的證明需要19個額外的點(diǎn)，而4個范圍(ranges)的整合，每個證明需要21個點(diǎn)。

注意我們引入了兩個相似但是獨(dú)立的概念：整合(aggregation)是指證明程序?qū)⒍鄠€rangeproofs組合成1個；而批量處理(batching)是指驗(yàn)證程序同時檢測多個單獨(dú)的證明。

這意味著兩個64位的rangeproofs可以在2.7 ms內(nèi)完成驗(yàn)證，或者每個范圍(range)1.4 ms。500個rangeproofs可以在130 ms內(nèi)完成驗(yàn)證，或者每個范圍(range)0.26 ms，這比老版的證明提高了23倍。不過由于整合，它還可以變的更加可觀。500個8個一整合的rangeproofs（一共是4000個范圍(ranges)）可以在305 ms內(nèi)驗(yàn)證完，或者每個范圍 76 微秒，比老版的rangeproofs提高了75倍。

隨著日益高效的標(biāo)量點(diǎn)乘法不再是主導(dǎo)效應(yīng)，這種影響最終會圍繞64個證明的整合最大化。在這一點(diǎn)上，我們可以以每個范圍(range)46微秒來批量驗(yàn)證，速度提高了125倍。作為參考，橢圓曲線數(shù)字簽名算法（ECDSA）簽名大約需要55微秒，所以在這種級別的整合下，rangeproofs甚至不是交易驗(yàn)證的主要部分。當(dāng)然，我們不太可能在區(qū)塊鏈上看見64個輸出交易，不過這種速度在非區(qū)塊鏈環(huán)境中（如 Provisions
）是可能的。

這種驗(yàn)證同樣也是節(jié)約內(nèi)存的，驗(yàn)證單個rangeproof需要 100 KiB，隨著大小而增加減。

你可以證明任何事情（如果它是真的話）

Bulletproofs比rangeproofs更加的通用。它們可以被用來在零知識中證明任意的陳述。它們與SNARKs或STARKs相當(dāng)，不過它們原生支持橢圓曲線(EC)公鑰和Pedersen commitments（因此通常不需要在程序中實(shí)現(xiàn)EC算法）。此外，與SNARK不同的是，Bulletproofs在無信任環(huán)境的標(biāo)準(zhǔn)猜想下?lián)碛型暾?28位安全性。與STARK不同，它們在典型的計(jì)算機(jī)硬件上足以快速證明和驗(yàn)證合理大小的問題。

作為一個具體的例子，考慮SHA2壓縮功能的一次運(yùn)行。我們的證明程序需要少于 30 MiB的內(nèi)存和大約21秒來證明SHA2原像的知識。驗(yàn)證需要大約23 MiB的內(nèi)存和75 ms，但是我們可以用大約每個證明5 ms和13.4 KiB批量驗(yàn)證額外的證明。

我們的證明程序比SNARK更節(jié)省內(nèi)存：在相同的系統(tǒng)中，SHA2的一個SNARK證明只需要4秒但是要75 MiB內(nèi)存。驗(yàn)證時，每個電路需要大量的一次性預(yù)計(jì)算（需要被證明的陳述），然后只需要3-5 ms和很少的內(nèi)存就可以驗(yàn)證。這些數(shù)字不會隨著電路的增加而增加，所以對于超過幾千門的電路，即使與我們的批量驗(yàn)證相比，SNARK也明顯是贏家。不幸的是，這是以可信賴的環(huán)境和新的加密猜想為代價的。

在證明程序和驗(yàn)證程序上，Bulletproofs仍有很大的優(yōu)化空間。

驗(yàn)證任意陳述句的能力——不管是Bulletproofs，SNARKs或者STARKs，都有很多的應(yīng)用。它可以用于實(shí)現(xiàn)普通的數(shù)字簽名，包括（可追蹤的）環(huán)形簽名和閾值簽名，對于大型環(huán)來說，在驗(yàn)證時間和證明大小方面它都比傳統(tǒng)方案要高效。它的使用不限于此，它還可以用來可靠的銷售數(shù)獨(dú)問題，可以用于多方計(jì)算，即使有秘密數(shù)據(jù)的情況下還是可以證明每方都是誠實(shí)行事。（特別是在MuSig這樣的多重簽名方案中，這允許使用確定性的隨機(jī)數(shù)生成，而不需要簽名者維護(hù)狀態(tài)或容易受到隨機(jī)重用攻擊。）它還可以用來證明哈希原像(preimages)。

后一種應(yīng)用，哈希原像，是特別有趣的，因?yàn)樗梢杂脕韯?chuàng)建零知識Merkle證明，包含在大規(guī)模集合（有數(shù)百萬甚至數(shù)十億元素）的高效證明。我們將在未來的文章中探討這一點(diǎn)。

總結(jié)

• Bulletproofs是通用零知識證明（類似SNARKs）
• 它們可以用來擴(kuò)展多方協(xié)議，如多重簽名或零知識應(yīng)急支付
• Bulletproofs提供了一個更加高效的CT rangeproofs版本（批量驗(yàn)證時，速度提高超過23倍）
• 這些rangeproofs可以在交易中進(jìn)行整合，然而大小只以對數(shù)級增長
• 通過充分的整合，例如Provisions，批量驗(yàn)證的速度比老版的證明快了超過130倍

我們很感謝Bootle等人開發(fā)的內(nèi)部產(chǎn)品參數(shù)，它引導(dǎo)了我們。同樣也感謝Benedikt Bünz和Dan Boneh，我們的合著者，他們做了大量的創(chuàng)造性工作。感謝Sean Bowe和Daira Hopwood為優(yōu)化算術(shù)電路而做的研究。

鏈接

• Full paper
• Bulletproofs - Stanford Applied Crypography
• Benedikt Bünz talk at BPASE ‘18
• Andrew Poelstra talk at Milano Bitcoin meetup (slides)

翻譯作者: 許莉
原文地址: Bulletproofs Faster Rangeproofs and Much More

作者：Lilymoana
鏈接：https://www.jianshu.com/p/47c105f356f5
來源：簡書

著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

總結(jié)

以上是生活随笔為你收集整理的一个更优的零知识证明：Bulletproofs的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。