Bulletproofs

Bulletproofs 是簡短、非互動且不需可信設定的零知識證明。它因把機密交易中的範圍證明縮小而成名，但其底層技術能證明任何算術電路的命題。它的招牌特性是對數級的證明大小：舊的 Borromean 範圍證明呈線性增長、重達數千位元組，而同樣 64 位元範圍的 Bulletproof 不到 700 位元組，且一次證明多個輸出只額外增加一點點。它由 Bünz、Bootle、Boneh、Poelstra、Wuille 與 Maxwell 於 2017 年提出——名字來自它「短、且不需設定」，宛如一顆子彈。

Bulletproof 的核心是內積論證。要證明像「這個被承諾值的各位元皆為 0/1 且加總等於該值」這類命題，證明者把它編碼成兩個向量之間的關係，再證明它們的內積正確。巧妙之處在於遞迴折半：每一輪把兩個長度 m 的向量折成一個長度 m/2 的向量，於是經 log2(m) 輪後，證明塌縮成常數個群元素。非互動性來自 Fiat-Shamir 啟發式，它用對謄本的雜湊取代驗證者的隨機挑戰。安全性只依賴離散對數假設——不需配對友善曲線、也不需任何儀式，這相對於 Groth16 式 SNARK 是一大實務優勢。

代價是驗證成本。Bulletproof 雖小，但其驗證者的工作量與電路大小成線性——它必須執行一個龐大的多重指數運算——因此驗證比常數時間的 SNARK 驗證者慢。這在鏈的規模下很要緊：節點要驗證每一個證明。緩解之道是批次驗證，把許多證明合併成一次大型多重指數運算來攤平成本，這正是 Monero 把整批 Bulletproofs 一起驗證、而非逐一驗證的原因。

Monero 於 2018 年 10 月部署 Bulletproofs，取代 Borromean 範圍證明，把典型交易大小削減約 80%、手續費也相應節省；後來一個改良版 Bulletproofs+ 進一步縮減大小與證明時間，並於 2022 年採用。除範圍證明外，Bulletproofs 也被用於機密智能合約、可驗證洗牌與其他通用命題，不過對於非常大的電路，具常數驗證的簡潔 SNARK 往往勝出。