BitVM：在比特幣上計算任何東西

作者：Robin Linux 譯者：登鏈社區翻譯小組

摘要

BitVM 是一種計算範式，用於表達圖靈完備的比特幣合約。 這不需要對比特幣網路的共識規則進行任何更改。 與在比特幣上執行計算不同，它們僅僅是被驗證，類似於樂觀 Rollups。 證明者聲明某個給定的函數對某些特定的輸入求值得到了特定的輸出。 如果該聲明是錯誤的，那麼驗證者可以進行簡明的欺詐證明並懲罰證明者。 使用這種機制，任何可計算的函數都可以在比特幣上進行驗證。

在 Taproot 位址上承諾一個大型程式需要大量的鏈外計算和通信，然而其在鏈上的佔用空間很小。 只要雙方合作，他們可以進行任意複雜的、有狀態的鏈外計算，而不在鏈上留下任何痕跡。 只有在爭議的情況下才需要在鏈上執行。

1 簡介

按設計，比特幣的智能合約功能被限制為基本操作，如簽名、時間鎖和哈希鎖。 BitVM 為更具表達力的比特幣合約和鏈外計算創造了一個新的設計空間。 潛在的應用包括象棋、圍棋或撲克等遊戲，以及比特幣合約中有效性證明的驗證。 此外，可能還可以將比特幣橋接到外部鏈、構建預測市場或類比新的操作碼。

這裡提出的模型的主要缺點是它僅適用於有兩方的設定，即證明者和驗證者。 另一個限制是，對於證明者和驗證者，需要大量的鏈外計算和通信來執行程式。 然而，這些問題似乎有望通過進一步的研究得到解決。 在這項工作中，我們僅關注兩方 BitVM 的關鍵組成部分。

2 架構

與樂觀 Rollups 1[2] [3] 和MATT提案（Merkelize All The Things）2 類似，我們的系統基於欺詐證明和挑戰-回應協定。 然而，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 通過打開她的 Tap 葉子中的一個哈希鎖來選擇一個挑戰。 這將為 Paul 解鎖一個特定的 Tap，並迫使他執行它。 該腳本強制 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. 2022.

[2] 薩爾瓦多·英加拉。默克利化所有的東西。, 2022.

參考資料

[1] 翻譯小組：

[2] 樂觀 Rollups 1：

[3] MATT 提案（Merkelize All The Things）2：