在 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)

英文版原文：
https://blockstream.com/2018/02/21/bulletproofs-faster-rangeproofs-and-much-more.html

本文鏈接較多，可以點擊原文查看。