本文提出一些優化思路，進一步提高 BitVM 的效率和安全性。
原文：BitVM And Its Optimization Considerations
作者：lynndell，mutourend
出品：Bitlayer 研究組
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 腳本是有狀態的，如可強制 script1 和 script2 中的 x 為相同值。 如果參與方簽署了相互衝突的 x 值，則可對其進行懲罰。 BitVM 程式計算發生在鏈下，而計算結果驗證發生在鏈上。 當前 Bitcoin 區塊有 1MB 限制，當驗證計算過於複雜時，可藉助 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 位元組，約 17GB。 在最壞情況下，需要約 40 輪挑戰和回應，約半年時間，總腳本約 150KB。 該情況下激勵嚴重不足，但實際情況下幾乎不發生。
考慮使用零知識證明降低 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 為 1MB，即占滿整個區塊。 但 legacy 交易的 standardness 上限為 100kB。 根據共識規則，Segwit 交易的最大 size 為 4MB，即 weight limit。 但 Segwit 交易的 standardness 上限為 400kB。
Lamport 簽名是 BitVM 的基礎元件，降低簽名和公鑰長度，有助於降低交易數據，從而降低手續費。 Lamport 一次性簽名需使用哈希函數（如 one way permutation 函數 f）。 Lamport 一次性簽名方案中，消息長度為 v 比特，公鑰長度為 2v 比特，簽名長度也為 2v 比特。 簽名和公鑰較長，需要消耗大量的存儲 gas。 因此，需要尋找類似功能的簽名方案，以降低簽名和公鑰長度。 相比 Lamport 一次性簽名，Winternitz 一次性簽名的簽名和公鑰長度大幅降低，但是增加了簽名和驗簽的計算複雜度。
在 Winternitz 一次性簽名方案中，使用特殊函數 P 將 v 比特的消息映射為長度為 n 的向量 s。 s 中每個元素的取值為 {0,...,d}。 Lamport 一次性簽名方案是 d=1 特殊情況下的 Winternitz 一次性簽名方案。 在 Winternitz 一次性簽名方案中，n，d，v 之間的關係滿足：n≈v/log2（d+1）。 當 d=15 時，有 n≈（v/4）+1。 對於包含 n 個元素的 Winternitz 簽名而言，比 Lamport 一次性簽名方案中的公鑰長度和簽名長度短 4 倍。 但是，驗簽的複雜度提高了 4 倍。 在 BitVM 中使用 d=15，v=160，f=ripemd160（x）實現 Winternitz 一次性簽名，可將 bit commitment size 降低 50%，從而將 BitVM 的交易費降低至少 50%。 未來，在對現有 Winternitz 比特幣腳本實現進行優化的同時，可探索以比特幣腳本表達的更緊湊的一次性簽名方案。
3.3 比特幣友好的哈希函數
根據共識規則，P2TR script 的最大 size 為 10kB，P2TR script witness 的最大 size 與最大 Segwit 交易 size 一樣，為 4MB。 但 P2TR script witness 的 standradness 上限為 400kB。
當前比特幣網路還不支援 OP_CAT，無法拼接字串做 Merkle path 驗證。 因此，需用現有比特幣腳本，以 script size 和 script witness size 最優的方式，實現一種比特幣友好的哈希函數，從而支援 merkle inclusion proof 驗證功能。
BLAKE3 為 BLAKE2 哈希函數的優化版，並引入了 Bao tree 模式。 相比於 BLAKE2s-based，其壓縮函數的輪數由 10 降至 7。 BLAKE3 哈希函數會將其輸入切分為 1024 位元組大小的連續 chunks，最後一個 chunk 可能更短但不為空。 當只有一個 chunk 時，則該 chunk 為 root node，且為該樹的唯一節點。 將這些 chunks 排布為二進位樹的葉子節點，然後對每個 chunk 獨立壓縮。
當將 BitVM 用於驗證 Merkle inclusion proof 場景時，哈希運算的輸入由 2 個 256-bit 哈希值拼接而成，即哈希運算的輸入為 64 位元組。 使用 BLAKE3 哈希函數時，這 64 位元組可分配於單個 chunk 內，整個 BLAKE3 哈希運算僅需要對單個 chunk 應用一次壓縮函數。 BLAKE3 的壓縮函數中，需要運行 7 次輪函數和 6 次置換函數。
目前 BitVM 中已完成基於 u32 值的 XOR、模加、位右移等基礎運算，可以很容易組裝出比特幣腳本實現的 BLAKE3 哈希函數。 使用 stack 中 4 個分開的位元組來表示 u32 words，來實現 BLAKE3 所需的 u32 addition、u32 bitwise XOR 和 u32 bitwise rotations。 目前 BLAKE3 哈希函數比特幣腳本共約 100kB，足以用於構建一個 toy 版本的 BitVM。
此外，可拆分這些 BLAKE3 代碼，使得 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 无需许可多方挑战模型。
4. 结论
BitVM 技术探索才刚刚开始，未来将探索和实践更多的优化方向，以实现对比特币的扩容，繁荣比特币生态。
参考文献
- BitVM: Compute Anything on Bitcoin
- BitVM：Off-chain Bitcoin Contracts
- Robin Linus on BitVM
- [bitcoin-dev] BitVM: Compute Anything on Bitcoin
- The Odd Couple: ZK and Optimistic Rollups on a Scalability Date
- What are Bitcoin’s transaction and script limits?
- BIP-342: Validation of Taproot Scripts
- https://twitter.com/robin_linus/status/1765337186222686347
- A Graduate Course in Applied Cryptography
- BLAKE3: one function, fast everywhere
- [bitcoin-dev] Implementing Blake3 in Bitcoin Script
- https://github.com/BlockstreamResearch/scriptless-scripts
- Introduction to Scriptless Scripts
- BitVM using Scriptless Scripts
- Solutions to Delay Attacks on Rollups
- Introducing DAVE. Cartesi’s Permissionless Fault-Proof System.
- Delay Attacks on Rollups
- Solutions to Delay Attacks on Rollups – Arbitrum Research
- Multiplayer Interactive Computation Games Notes
- BoLD: Bounded Liquidity Delay in a Rollup Challenge Protocol
- Permissionless Refereed Tournaments
免責聲明：作為區塊鏈資訊平臺，本站所發佈文章僅代表作者及嘉賓個人觀點，與 Web3Caff 立場無關。 文章內的資訊僅供參考，均不構成任何投資建議及要約，並請您遵守所在國家或地區的相關法律法規。
