BitVM原理解析及其優化思考

2024-03-26 11:03:10

原文來源：Bitlayer 研究組

原文作者：lynndell, mutourend.

1.引言

比特幣是一種去中心化、安全且值得信賴的數字資產。但是，它存在重大限制，無法成為支付和其他應用的可擴展網絡。比特幣的擴容問題自誕生以來就一直備受關注。比特幣 UTXO 模型將每筆交易視為一個獨立事件，導致一個無狀態的系統，缺乏執行復雜的、依賴狀態的計算能力。因此，雖然比特幣可以執行簡單腳本和多籤交易，但它難以促進在有狀態的區塊鏈平臺上常見的復雜和動態的合約交互。這一問題顯著限制了在比特幣上構建的去中心化應用（dApps）和復雜金融工具的範疇，而狀態模型平臺提供了一個更加多樣化的環境，用於部署和執行功能豐富的智能合約。

對於比特幣擴容，主要有狀態通道、側鏈、客戶端驗證等技術。其中，狀態通道提供了安全且多樣化的支付解決方案，但其在驗證任意復雜計算的能力上有限。這種限制減少了其在需要復雜、條件性邏輯和交互的各種場景中的應用。側鏈雖然支持廣泛的應用，並提供超越比特幣功能的多樣性，但是具有較低的安全性。這種安全上的差異源於側鏈採用的是獨立的共識機制，這些機制遠不如比特幣共識機制的健壯性。客戶端驗證，使用比特幣 UTXO 模型，可以處理更多復雜的交易，但是與比特幣沒有雙向校驗和約束能力，導致其安全性低於比特幣。客戶端驗證協議的鏈下設計依賴於服務器或雲基礎設施，這可能導致集中化或通過妥協服務器進行潛在審查。客戶端驗證的鏈下設計還給區塊鏈基礎設施引入了更多復雜性，可能導致可擴展性問題。

2023 年 12 月，ZeroSync 項目負責人 Robin Linus 發表了一篇名為《 BitVM：Compute Anything On Bitcoin 》的白皮書，引發了大家對於提升比特幣可編程性的思考。該論文提出一種在不改變比特幣網絡共識的情況下可實現圖靈完備的比特幣合約解決方案，使得任何復雜計算都可以在比特幣上驗證，而無需改變比特幣基本規則。BitVM 充分利用比特幣腳本和 Taproot，實現樂觀 Rollup。基於 Lamport 籤名（又名 bit commitment），讓比特幣兩個 UTXO 之間建立聯系，實現有狀態的比特幣腳本。在 Taproot 地址中承諾一個大型程序，operator 和驗證方進行大量的鏈下交互，在鏈上產生的足跡很小。如果雙方合作，則可以執行任意復雜的、有狀態的鏈下計算，而不在鏈上留下任何痕跡。如果雙方不合作，則發生爭議時，需要鏈上執行。因此，BitVM 極大地拓寬了比特幣的潛在用例，使比特幣不僅可以作為一種貨幣，還可以作為各種去中心化應用和復雜計算任務的驗證平臺。

但是，雖然 BitVM 技術在比特幣擴容方面極具優勢，但仍處於早期階段，在效率和安全方面還存在一些問題。如：（1）挑战與響應需要多次交互，導致手續費昂貴，挑战周期長；（2）Lamport 一次性籤名數據較長，需要降低數據長度；（3）哈希函數復雜度較高，需要 Bitcoin friendly 哈希函數，降低費用；（4）現有 BitVM 合約龐大而比特幣區塊容量有限，可借助 scriptless scripts 來實現 Scriptless Scripts BitVM，節約比特幣區塊空間，同時提升 BitVM 效率；（5）現有 BitVM 採用的是許可模型，僅聯盟成員可發起挑战，且限定為僅兩方之間，應擴展至 permissionless 多方挑战模式，將信任假設進一步減小。為此，本文提出一些優化思路，進一步提高 BitVM 的效率和安全性。

2.BitVM 原理

BitVM 定位為 Bitcoin 的鏈下合約，致力於推動 Bitcoin 合約功能。當前比特幣腳本是完全無狀態的，所以比特幣腳本執行時，其執行環境在每個腳本之後都會重置。令腳本 1 和腳本 2 擁有相同 x 值的原生方式是不存在的，比特幣腳本原生不支持該方式。但仍可以借助現有 opcodes，通過 Lamport 一次性籤名讓 Bitcoin 腳本是有狀態的，如可強制 script 1 和 script 2 中的 x 為相同值。如果參與方籤署了相互衝突的 x 值，則可對其進行懲罰。BitVM 程序計算發生在鏈下，而計算結果驗證發生在鏈上。當前 Bitcoin 區塊有 1 MB 限制，當驗證計算過於復雜時，可借助 OP 技術，採用挑战響應模式，支持更高復雜度的計算驗證。

與 Optimistic Rollup 和 MATT 提案（Merkelize All The Things）類似，BitVM 系統基於欺詐證明和挑战-響應協議，但不需要修改比特幣的共識規則。BitVM 底層原語簡單，主要基於哈希鎖、時間鎖和大型 Taproot 樹。

證明者逐字節承諾，但在鏈上驗證所有計算將過於昂貴。所以，驗證者執行一系列精心設計的挑战，以簡潔地駁斥證明者的虛假主張。證明者和驗證者共同預籤一系列挑战和響應交易，用於解決爭議，從而允許在比特幣上進行通用計算驗證。

BitVM 關鍵組件有：

電路承諾： 證明者和驗證者將程序編譯為大型二進制電路。證明者在一個 Taproot 地址中承諾該電路，該地址下的每個葉子腳本，對應該電路中的每個邏輯門。核心是基於 bit commitment 來實現 logic gate commitment，從實現電路承諾。
挑战和響應： 證明者和驗證者預籤一系列交易來實現挑战-響應遊戲。理想情況下，這種互動是在鏈下進行的，當證明者不配合時，也可在鏈上執行。
模棱兩可懲罰： 如果證明者提出任何不正確的聲明，則驗證者挑战成功後可拿走證明者存款，挫敗證明者的作惡行為。

3.BitVM 優化

3.1 基於 ZK 降低 OP 交互次數

當前有 2 大主流 Rollups：ZK Rollups 和 OP Rollups。其中，ZK Rollups 依賴於 ZK Proof 的有效性驗證，即正確執行的密碼學證明，其安全性依賴於計算復雜度假設；OP Rollups 依賴於 Fraud Proof，假設所提交的狀態均是正確的，設定挑战周期通常為 7 天，其安全性假定系統內至少有一個誠實方能探測到不正確的狀態，並提交欺詐證明。假設 BitVM 挑战程序最大步數為 2 ^{ 32 }，需要內存為 2 ^{ 32 }* 4 字節，約 17 GB。在最壞情況下，需要約 40 輪挑战和響應，約半年時間，總腳本約 150 KB。該情況下激勵嚴重不足，但實際情況下幾乎不發生。

考慮使用零知識證明降低 BitVM 的挑战次數，從而提高 BitVM 的效率。根據零知識證明理論，如果數據 Data 滿足算法 F，則證明 proof 滿足驗證算法 Verify，即驗證算法輸出 True；如果數據 Data 不滿足算法 F，則證明 proof 也不滿足驗證算法 Verify，即驗證算法輸出 False。在 BitVM 系統中，如果挑战者不認可證明方提交的數據，則發起挑战。

對於算法 F，使用二分法拆开，假設需要 2 ^n 次，則能找到錯誤點；如果算法復雜度太高，則 n 較大，需要很久才能完成。但是，零知識證明的驗證算法 Verify 的復雜度是固定的，公开證明 proof 和驗證算法 Verify 全過程，發現輸出為 False。零知識證明的優勢在於打开驗證算法 Verify 所需的計算復雜度，相比於二分法打开原始算法 F，要低得多。因此，借助零知識證明，讓 BitVM 挑战的不再是原始算法 F，而是驗證算法 Verify，降低挑战輪數，縮短挑战周期。

最後，雖然零知識證明有效性和欺詐證明依賴於不同的安全假設，但是可將二者結合，可構建 ZK Fraud Proof，實現 On-Demand ZK Proof。不同於 full ZK Rollup，不再需要為每個單個狀態變換生成 ZK proof，On-Demand 模型使得，僅在有挑战時才需要 ZK Proof，而整個 Rollup 設計仍是樂觀的。因此，仍默認所生成的狀態是有效的，直到有人挑战該狀態。如果某個狀態無挑战，則無需生成任何 ZK Proof。但是，如果參與方發起挑战，則需為挑战區塊內所有交易的正確性生成 ZK Proof。未來，可探索為單個有爭議指令生成 ZK Fraud Proof，避免一直生成 ZK Proof 的計算成本。

3.2 比特幣友好的一次性籤名

比特幣網絡中，遵循共識規則的交易是有效交易，但除共識規則之外，還額外引入了 standardness 規則。比特幣節點僅轉發廣播標准交易，有效但非標准的交易被打包的唯一方法直接是與礦工合作。

根據共識規則，legacy（即 non-Segwit）交易的最大 size 為 1 MB，即佔滿整個區塊。但 legacy 交易的 standardness 上限為 100 kB。根據共識規則，Segwit 交易的最大 size 為 4 MB，即 weight limit。但 Segwit 交易的 standardness 上限為 400 kB。

Lamport 籤名是 BitVM 的基礎組件，降低籤名和公鑰長度，有助於降低交易數據，從而降低手續費。Lamport 一次性籤名需使用哈希函數（如 one way permutation 函數 f）。Lamport 一次性籤名方案中，消息長度為 v 比特，公鑰長度為 2 v 比特，籤名長度也為 2 v 比特。籤名和公鑰較長，需要消耗大量的存儲 gas。因此，需要尋找類似功能的籤名方案，以降低籤名和公鑰長度。相比 Lamport 一次性籤名，Winternitz 一次性籤名的籤名和公鑰長度大幅降低，但是增加了籤名和驗籤的計算復雜度。

在 Winternitz 一次性籤名方案中，使用特殊函數 P 將 v 比特的消息映射為長度為 n 的向量 s。s 中每個元素的取值為{ 0,..., d}。Lamport 一次性籤名方案是 d= 1 特殊情況下的 Winternitz 一次性籤名方案。在 Winternitz 一次性籤名方案中，n, d, v 之間的關系滿足：n≈v/log 2(d+ 1)。當 d= 15 時，有 n≈(v/4)+ 1 。對於包含 n 個元素的 Winternitz 籤名而言，比 Lamport 一次性籤名方案中的公鑰長度和籤名長度短 4 倍。但是，驗籤的復雜度提高了 4 倍。在 BitVM 中使用 d= 15, v= 160, f=ripemd 160(x)實現 Winternitz 一次性籤名，可將 bit commitment size 降低 50% ，從而將 BitVM 的交易費降低至少 50% 。未來，在對現有 Winternitz 比特幣腳本實現進行優化的同時，可探索以比特幣腳本表達的更緊湊的一次性籤名方案。

3.3 比特幣友好的哈希函數

根據共識規則，P 2 TR script 的最大 size 為 10 kB，P 2 TR script witness 的最大 size 與最大 Segwit 交易 size 一樣，為 4 MB。但 P 2 TR script witness 的 standradness 上限為 400 kB。

當前比特幣網絡還不支持 OP_CAT，無法拼接字符串做 Merkle path 驗證。因此，需用現有比特幣腳本，以 script size 和 script witness size 最優的方式，實現一種比特幣友好的哈希函數，從而支持 merkle inclusion proof 驗證功能。

BLAKE 3 為 BLAKE 2 哈希函數的優化版，並引入了 Bao tree 模式。相比於 BLAKE 2 s-based，其壓縮函數的輪數由 10 降至 7 。BLAKE 3 哈希函數會將其輸入切分為 1024 字節大小的連續 chunks，最後一個 chunk 可能更短但不為空。當只有一個 chunk 時，則該 chunk 為 root node，且為該樹的唯一節點。將這些 chunks 排布為二進制樹的葉子節點，然後對每個 chunk 獨立壓縮。

當將 BitVM 用於驗證 Merkle inclusion proof 場景時，哈希運算的輸入由 2 個 256-bit 哈希值拼接而成，即哈希運算的輸入為 64 字節。使用 BLAKE 3 哈希函數時，這 64 字節可分配於單個 chunk 內，整個 BLAKE 3 哈希運算僅需要對單個 chunk 應用一次壓縮函數。BLAKE 3 的壓縮函數中，需要運行 7 次輪函數和 6 次置換函數。

目前 BitVM 中已完成基於 u 32 值的 XOR、模加、位右移等基礎運算，可以很容易組裝出比特幣腳本實現的 BLAKE 3 哈希函數。使用 stack 中 4 個分开的字節來表示 u 32 words，來實現 BLAKE 3 所需的 u 32 addition、u 32 bitwise XOR 和 u 32 bitwise rotations。目前 BLAKE 3 哈希函數比特幣腳本共約 100 kB，足以用於構建一個 toy 版本的 BitVM。

此外，可拆分這些 BLAKE 3 代碼，使得 Verifier 和 Prover 可通過將挑战-響應遊戲中的執行一分為二而不是完全執行來顯著降低所需的鏈上數據。最後，使用比特幣腳本實現 Keccak-256、Grøstl 等哈希函數，從中選出最比特幣友好的哈希函數，並探索其它新的比特幣友好哈希函數。

3.4 Scriptless Scripts BitVM

Scriptless Scripts 是一種通過使用 Schnorr 籤名，在鏈下執行智能合約的方法。Scripless Scripts 概念誕生自 Mimblewimble，除了 kernel 及其籤名之外，不存儲永久數據。

Scriptless Scripts 的優點是功能、隱私和效率。

功能： Scriptless Scripts 可增加智能合約的範圍和復雜性。比特幣腳本能力受限於網絡中已啓用的 OP_CODES 數量，而 Scriptless Scripts 將智能合約的規範和執行從鏈上轉移到僅設計合約參與方的討論，無需等待比特幣網絡的分叉來啓用新的操作碼。
隱私： 將智能合約的規範和執行從鏈上轉移到鏈下，可增加隱私。在鏈上，合約的很多細節都會共享到整個網絡，這些詳細信息包括參與者的數量和地址以及轉账金額等。通過將智能合約移至鏈下，網絡只知道參與者同意其合約條款已得到滿足且相關交易有效。
效率： Scriptless Scripts 最大限度地降低鏈上驗證和存儲的數據量。通過將智能合約移至鏈下，全節點的管理費用會減少，用戶的交易費用也會降低。

Scriptless scripts 是一種在比特幣上設計密碼學協議的方法，可避免執行顯式智能合約。核心思想是使用密碼算法實現期望功能，而不是使用腳本實現功能。適配器籤名和多重籤名，是 Scriptless scripts 的原始構建基石。使用 Scriptless scripts，可實現比常規交易更小的交易，降低交易手續費。

可借助 Scriptless Scripts，使用 Schnorr 多重籤名和適配器籤名，不再像 BitVM 方案那樣提供哈希值和哈希原像，也可實現 BitVM 電路中的邏輯門承諾，從而可節約 BitVM 腳本空間，提高 BitVM 效率。雖然現有的 Scriptless Scripts 方案能降低 BitVM 腳本空間，但是需要證明者和挑战者有大量交互來組合公鑰。未來將對該方案進行改進，同時嘗試將 Scripless Scripts 引入到具體 BitVM 功能模塊內。

3.5 無需許可的多方挑战

當前 BitVM 挑战默認需要許可的原因在於：Bitcoin 的 UTXO 僅能執行一次，導致惡意的 verifier 可通過挑战誠實 prover 來“浪費”該合約。當前 BitVM 限定為兩方挑战模式。試圖作惡的 prover，可同時用自己控制的 verifier 發起挑战，從而“浪費”該合約，使得作惡成功，而其它 verifier 無法阻止該行為。因此，在 Bitcoin 基礎之上，需要研究無需許可的多方 OP 挑战協議，可將 BitVM 的現有 1-of-n 信任模型，擴展至 1-of-N。其中，N 遠大於 n。此外，需要研究解決挑战者與 prover 串謀或惡意挑战“浪費”合約的問題。最終實現信任更小的 BitVM 協議。

無需許可的多方挑战，允許任何人在沒有許可名單的情況下參與。這就意味着，用戶可在沒有任何可信第三方參與的情況下，從L2提幣。此外，任何想要參與 OP 挑战協議的用戶均可質疑和刪除無效提款。

將 BitVM 擴展為無需許可多方挑战模型，需解決如下攻擊：

女巫攻擊： 即使攻擊者僞造多個身份參與爭議挑战，單個誠實參與方仍能夠贏得爭議。如果誠實參與方捍衛正確結果的成本，與對攻擊者的數量呈线性關系時，則當涉及大量攻擊者時，誠實參與方為贏得爭議所需付出的成本將變得不切實際，且容易受到女巫攻擊。論文 Permissionless Refereed Tournaments 中，提出一種改變遊戲規則的爭議解決算法，單個誠實參與方贏得爭議的成本隨着對手的數量呈對數增長，而不是线性增長。
延遲攻擊： 某個或一群惡意方，遵循某種策略來阻止或延遲正確結果（如將資產提取到L1）在L1上的確認，並迫使誠實的 prover 花費L1手續費。可要求挑战者需提前質押來緩解該問題。如果挑战者發起延遲攻擊，則沒收其質押。但是，如果攻擊者愿意在一定限度內犧牲質押來追求延遲攻擊，則應該有應對策略來降低延遲攻擊的影響。論文 BoLD: Bounded Liquidity Delay in a Rollup Challenge Protocol 提出的算法，使得無論攻擊者愿意失去多少質押，最壞情況下的攻擊只能導致一定上限的延遲。

未來，將探索適用於比特幣特性的，可抵抗以上攻擊問題的 BitVM 無需許可多方挑战模型。