BitVM原理解析及其優化思考

作者: 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技術探索才剛剛开始，未來將探索和實踐更多的優化方向，以實現對比特幣的擴容，繁榮比特幣生態。

參考文獻

1. BitVM: Compute Anything on Bitcoin

2. BitVM：Off-chain Bitcoin Contracts

3. Robin Linus on BitVM

4. [bitcoin-dev] BitVM: Compute Anything on Bitcoin

5. The Odd Couple: ZK and Optimistic Rollups on a Scalability Date

6. What are Bitcoin's transaction and script limits?

7. BIP-342: Validation of Taproot Scripts

8. https://twitter.com/robin_linus/status/1765337186222686347

9. A Graduate Course in Applied Cryptography

10. BLAKE3: one function, fast everywhere

11. [bitcoin-dev] Implementing Blake3 in Bitcoin Script

12. https://github.com/BlockstreamResearch/scriptless-scripts

13. Introduction to Scriptless Scripts

14. BitVM using Scriptless Scripts

15. Solutions to Delay Attacks on Rollups

16. Introducing DAVE. Cartesi's Permissionless Fault-Proof System.

17. Delay Attacks on Rollups

18. Solutions to Delay Attacks on Rollups - Arbitrum Research

19. Multiplayer Interactive Computation Games Notes

20. BoLD: Bounded Liquidity Delay in a Rollup Challenge Protocol

21. Permissionless Refereed Tournaments