在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證明，包含在大規模集合（有數百萬甚至數十億元素）的高效證明。我們將在未來的文章中探討這壹點。
我們很感謝Bootle等人開發的內部產品參數，它引導了我們。同樣也感謝Benedikt Bünz和Dan Boneh，我們的合著者，他們做了大量的創造性工作。感謝Sean Bowe和Daira Hopwood為優化算術電路而做的研究。
翻譯作者: 許莉
原文地址: Bulletproofs Faster Rangeproofs and Much More