作者：Robin Linux 譯者：登鏈社群翻譯小組
摘要
BitVM 是一種計算範式，用來表達圖靈完整的比特幣合約。這不需要對比特幣網路的共識規則進行任何更改。與在比特幣上執行計算不同，它們只是被驗證，類似於樂觀Rollups。證明者宣告某個給定的函數對某些特定的輸入求值得到了特定的輸出。如果該聲明是錯誤的，那麼驗證者可以進行簡潔的詐欺證明並懲罰證明者。使用這種機制，任何可計算的函數都可以在比特幣上進行驗證。
在Taproot 位址上承諾一個大型程式需要大量的鏈外計算和通信，然而其在鏈上的佔用空間很小。只要雙方合作，他們可以進行任意複雜的、有狀態的鏈外計算，而不在鏈上留下任何痕跡。只有在爭議的情況下才需要在鏈上執行。
1 簡介
按設計，比特幣的智慧合約功能被限制為基本操作，如簽名、時間鎖和哈希鎖。 BitVM 為更具表達力的比特幣合約和鏈外運算創造了一個新的設計空間。潛在的應用包括象棋、圍棋或撲克等遊戲，以及比特幣合約中有效性證明的驗證。此外，可能還可以將比特幣橋接到外部鏈、建立預測市場或模擬新的操作碼。
這裡提出的模型的主要缺點是它只適用於有兩方的設定，即證明者和驗證者。另一個限制是，對於證明者和驗證者，需要大量的鏈外計算和通訊來執行程式。然而，這些問題似乎有望透過進一步的研究得到解決。在這項工作中，我們僅關注兩方BitVM 的關鍵組成部分。
2 架構
與樂觀Rollups 1[2] 和MATT 提案（Merkelize All The Things）2[3] 類似，我們的系統基於欺詐證明和挑戰-響應協議。然而，BitVM 不需要對比特幣的共識規則進行任何更改。底層的原語相對簡單。它主要基於哈希鎖、時間鎖和大Taproot 樹。
證明者逐位地將程式提交到鏈上，但是在鏈上驗證所有內容將會消耗過多的計算資源，因此驗證者會執行一系列精心設計的挑戰來簡潔地證偽證明者的錯誤主張。證明者和驗證者共同預簽名一系列挑戰-回應交易，以便日後解決任何爭議。
該模型旨在簡單地說明這種方法允許在比特幣上進行通用計算。對於實際應用，我們應考慮更有效率的模型。
協議很簡單：首先，證明者和驗證者將程式編譯成一個巨大的二進位電路。證明者將該電路提交到一個Taproot 位址中，該位址的每個邏輯閘都有一個葉子腳本。此外，他們預先簽署一系列交易，為證明者和驗證者之間的挑戰-反應遊戲提供支援。現在，他們已經交換了所有所需的數據，因此可以將他們的鏈上存款轉入產生的Taproot 位址。
這將啟動合約，他們可以開始交換鏈下數據，以觸發電路中的狀態變化。如果證明者提出了任何錯誤的聲明，驗證者可以拿走他們的存款。這確保了攻擊者總是會損失他們的存款。
3 位元值承諾（Bit Value Commitment）
位值承諾是這個系統中最基本的組件。它允許證明者將特定位的值設為“0”或“1”。特別地，它允許證明者在不同的腳本和UTXO 之間設定變數的值。這是關鍵的，因為它透過將比特幣的虛擬機器執行時間分割成多個交易來擴展執行運行時。
承諾包含兩個哈希值，hash0 和hash1。在稍後的某個時刻，證明者透過揭示preimage0（hash0 的原像）將位元的值設為“0”，或透過揭示preimage1（hash1 的原像）將位元的值設為“1”。如果在某個時刻，他們同時揭露了preimage0 和preimage1，那麼驗證者可以將它們用作欺詐證明，並拿走證明者的存款。這被稱為矛盾陳述。能夠懲罰矛盾陳述是使承諾具有約束力的原因-它是一種「基於激勵的承諾」。
將位值承諾與時間鎖結合，使驗證者能夠強制證明者在給定的時間範圍內決定特定位元的值。
圖1：位值承諾的具體實現
圖1：1 位承諾的具體實現。為了解鎖此腳本，證明者必須揭示hash0 或hash1 的原像之一。在此範例執行中，證明者揭示了hash1，並將位元的值設為「1」。我們可以複製此承諾以在不同的腳本中強制執行特定的值。
為了簡化起見，從這裡開始，我們假設有一個名為OP BITCOMMITMENT 的操作碼，它是上述腳本的簡寫。該操作碼消耗兩個雜湊和一個雜湊的原像。根據與原像相符的哈希，它將一個位元值放在堆疊上。
4 邏輯閘承諾
任何可計算的函數都可以表示為布林電路。 NAND 閘是一種通用邏輯閘，因此任何布林函數都可以由它們組成。為了保持我們的模型簡單，我們展示了我們的方法如何適用於簡單的NAND 閘。此外，我們也展示瞭如何任意組合門。這一切都證明了BitVM 可以表示任何電路。
NAND 閘承諾的實作很簡單。它包含兩個表示兩個輸入的位元承諾和一個表示輸出的位元承諾。腳本計算兩個輸入的NAND 值，以確保它與承諾的輸出位元相符。
圖2：NAND 操作的邏輯閘承諾
圖2：NAND 操作的邏輯閘承諾。執行此腳本需要揭示位元承諾A、B 和C 的值，使得A NAND B = C 成立。
（在這裡，為了簡化起見，我們假設存在一個名為OP NAND 的操作碼。實際上，它並不存在，但可以使用OP BOOLAND 和OP NOT 輕鬆實現。）
5 二進位電路承諾
在前一節中，我們定義了NAND 閘承諾。我們可以透過組合閘承諾來表示任何電路。執行的每一步都在Tapleaf 中進行承諾。它們都合併到同一個Taproot 位址中，以便證明者可以執行電路中的任何閘。執行門需要證明者打開相應的門承諾，並為其輸入和輸出位元設定值。
Taptree 可能會變得龐大，並且擁有十億個Tapleaf 腳本，但其鏈上佔用空間很小。
圖3：一個隨機範例電路
圖3：一個隨機範例電路，其中包含8 個不同的NAND 閘和4 個輸入A、B、C 和D。使用數十億個閘門可以定義基本上任何函數。
圖 4
圖4：對於每個門，證明者的Taproot 位址包含一個具有相應門承諾的葉腳本。這使得證明者可以在任何時間點上設定電路的輸入值（這裡是A、B、C 和D）。
6 挑戰與回應
僅僅承諾一個電路是不夠的。為了反駁錯誤的聲明，驗證者必須能夠挑戰證明者的陳述。這可以透過在設定過程中預先簽名一系列交易來實現。這些交易按照挑戰→回應→挑戰→回應→…的方式連結。如果其中一方停止參與，那麼在一段超時時間後，另一方將贏得挑戰並可以拿走雙方的存款。只要雙方合作，他們可以透過2-of-2 簽名共同解決任何合約。以下機制僅在存在詐欺行為時才需要。
圖5：預簽名的一系列交易
圖5：預簽名的一系列交易，用於執行多輪挑戰和回應。此序列在設定過程中產生。
Vicky 透過打開她的Tapscript 葉子中的一個哈希鎖來選擇一個挑戰。這將為Paul 解鎖一個特定的Tapscript，並迫使他執行它。該腳本強制Paul 揭示Vicky 挑戰的門承諾。透過對幾輪查詢重複此過程，可以快速反駁任何不一致的聲明。
如果證明者停止與驗證者進行鏈下合作，驗證者需要一種方法來迫使證明者在鏈上採取行動。驗證者透過解鎖雜湊鎖來實現這一點：證明者的UTXO 中的每個NAND Tapleaf 只能在證明者知道驗證者持有的原像的情況下花費。因此，證明者可以透過揭示其輸入和輸出來證明給定的Tapleaf 正確執行，但前提是驗證者透過揭示保護該Tapleaf 的雜湊的原像來為其「解鎖」。透過應用二分搜索，驗證者可以在僅經過幾輪挑戰和回應後快速確定證明者的錯誤。
圖6：在每次回應後，Vicky 可以懲罰模稜兩可的行為。如果Paul 對一個變數公開了兩個衝突的值，那麼Vicky 立即贏得挑戰，並被允許拿走他的押金。 Vicky 透過揭示任何他的位承諾的兩個原來來證明Paul 的模糊性。
7 輸入和輸出
證明者可以透過揭示相應的位承諾來設定輸入。理想情況下，他們在鏈下揭示承諾以最小化鏈上的佔用。在非合作情況下，驗證者可以強制證明者在鏈上揭示他們的輸入。
可以透過提前交換加密的方式來處理大量資料。這樣，證明者可以在以後的某個時間點上揭露解密金鑰。
多方輸入也是可能的。門可以有來自雙方的位承諾。
8 限制和展望
用簡單的NAND 電路來表示函數是低效率的。透過使用更高級的操作碼，可以更有效地表示程式。例如，比特幣腳本支援添加32 位數字，因此我們不需要二進位電路。我們還可以有更大的位元承諾，例如，可以在單一雜湊中承諾32 位元。此外，腳本的大小可以達到約4 MB。因此，我們可以在每個葉子腳本中實現遠遠超過一個NAND 指令。
這裡提出的模型僅限於兩方。然而，可能可以有雙向通道，並將它們連結起來形成類似閃電網路的網路。探索兩方設定可能會產生有趣的泛化可能性。例如，我們可以為網路探索1 對n 的星形拓樸。另一個研究問題是，我們是否可以將我們的模型應用於n 對n 的設置，並創建更複雜的通道工廠。此外，我們可以將我們的系統與不同的鏈下協定（例如閃電網路或rollups）結合。
其他研究方向包括跨應用內存，如何對刻在鏈上的任意數據進行陳述，或者鏈下可編程電路，即鏈下虛擬機。也可能應用更複雜的取樣技術，類似STARKs，在單回合中檢查電路。
下一個重要的里程碑是完成一個具體的BitVM 設計和實現，以及Tree++，一種用於編寫和調試比特幣合約的高級語言。
9 結論
比特幣在某種意義上是圖靈完備的，因為在大型Taptrees 中編碼詐欺證明可以驗證任何程式的執行。這個模型的一個主要限制是它僅適用於兩方的情況。希望在進一步的工作中可以進行泛化。
致謝
特別感謝Super Testnet 和Sam Parker，他們始終堅信比特幣不會是圖靈完備的。
參考資料
[1] Ethereum Research. 樂觀Rollups. https://ethereum.org/en/developers/docs/scaling/optimistic-rollups/ 2022.
[2] Salvatore Ingala. Merkleize all the things. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-November/021182.html , 2022.
參考資料
[1]翻譯小組: https://learnblockchain.cn/people/412
[2]樂觀Rollups 1: https://ethereum.org/en/developers/docs/scaling/optimistic-rollups/
[3]MATT 提案（Merkelize All The Things）2: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-November/021182.html
