作者: lynndell, mutourend；來源：Bitlayer研究組
比特幣是一種去中心化、安全且值得信賴的數字資產。但是，它存在重大限制，無法成為支付和其他應用的可擴展網絡。比特幣的擴容問題自誕生以來就一直備受關注。比特幣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的效率和安全性。
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，從實現電路承諾。
挑戰和響應：證明者和驗證者預簽一系列交易來實現挑戰-響應游戲。理想情況下，這種互動是在鏈下進行的，當證明者不配合時，也可在鏈上執行。
模棱兩可懲罰：如果證明者提出任何不正確的聲明，則驗證者挑戰成功后可拿走證明者存款，挫敗證明者的作惡行為。
當前有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的計算成本。
比特幣網絡中，遵循共識規則的交易是有效交易，但除共識規則之外，還額外引入了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比特幣腳本實現進行優化的同時，可探索以比特幣腳本表達的更緊湊的一次性簽名方案。
根據共識規則，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等哈希函數，從中選出最比特幣友好的哈希函數，并探索其它新的比特幣友好哈希函數。
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功能模塊內。
當前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無需許可多方挑戰模型。
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
喜來順財經
