BitVM中英文白皮書

2024-01-24 16:01:48

BitVM: Compute Anything on Bitcoin

BitVM：在比特幣上進行任何計算

作者：Robin Linus [email protected] www.bitvm.org 2023.12.12

中文翻譯：Bitlayer bitlayer.org 2023.12.12

摘要(Abstract)

BitVM is a computing paradigm to express Turing-complete Bitcoin contracts. This requires no changes to the network's consensus rules. Rather than executing computations on Bitcoin, they are merely verified, similarly to optimistic rollups. A prover makes a claim that a given function evaluates for some particular inputs to some specific output. If that claim is false, then the verifier can perform a succinct fraud proof and punish the prover. Using this mechanism, any computable function can be verified on Bitcoin.

BitVM 是一種計算範式，用於表達圖靈完備的比特幣合約。這不需要對網絡的共識規則進行任何更改。與其在比特幣上執行計算，不如僅進行驗證，類似於樂觀Rollup。證明者提出一個聲明，稱給定的函數對某些特定輸入計算出某個特定輸出。如果該聲明是假的，那么驗證者可以進行簡潔的欺詐證明並懲罰證明者。使用這種機制，任何可計算的函數都可以在比特幣上驗證。

Committing to a large program in a Taproot address requires significant amounts of off-chain computation and communication, however the resulting on-chain footprint is minimal. As long as both parties collaborate, they can perform arbitrarily complex, stateful off-chain computation, without leaving any trace in the chain. On-chain execution is required only in case of a dispute.

在 Taproot 地址中提交一個大型程序需要大量的鏈下計算和通信，然而產生的鏈上足跡卻很小。只要雙方合作，他們可以執行任意復雜的、有狀態的鏈下計算，而不在鏈上留下任何痕跡。僅在發生爭議時才需要鏈上執行。

1簡介 (Introduction)

By design, the smart contract capabilities of Bitcoin are reduced to basic operations, such as signatures, timelocks, and hashlocks. The BitVM creates a novel design space for more expressive Bitcoin contracts and also off-chain computation. Potential applications include games like Chess, Go, or Poker, and particularly, verification of validity proofs in Bitcoin contracts. Additionally, it might be possible to bridge BTC to foreign chains, build a prediction market, or emulate novel opcodes.

按設計，比特幣的智能合約功能僅限於基本操作，如籤名、時間鎖和哈希鎖。BitVM 為更具表現力的比特幣合約和鏈下計算創造了新的設計空間。潛在的應用包括國際象棋、圍棋或撲克等遊戲，特別是在比特幣合約中驗證有效性證明。此外，可能還能將 BTC 橋接到外部鏈條、構建預測市場或模擬新的操作碼。

The main drawback of the model proposed here is that it is limited to the two-party setting with a prover and a verifier. Another limitation is that, for both the prover and the verifier, significant amounts of off-chain computation and communication is required to execute programs. However, these issues seem likely to be solved by further research. In this work, we focus solely on the key components of the two-party BitVM.

這裏提出的模型的主要缺點是它僅限於具有證明者和驗證者的兩方設置。另一個限制是，對於證明者和驗證者而言，執行程序需要大量的鏈下計算和通信。然而，這些問題似乎很可能通過進一步的研究得到解決。在這項工作中，我們僅專注於兩方 BitVM 的關鍵組成部分。

2 架構 (Architecture)

Similar to Optimistic Rollups[1] and the MATT proposal (Merkelize All The Things)[2], our system is based on fraud proofs and a challenge-response protocol. However, BitVM requires no changes to Bitcoin's consensus rules. The underlying primitives are relatively simple. It's mostly based on hashlocks, timelocks, and large Taproot trees.

與樂觀Rollup[1]和MATT提案（Merkelize All The Things）[2]類似，我們的系統基於欺詐證明和挑战-響應協議。然而，BitVM不需要對比特幣的共識規則進行任何更改。底層原語相對簡單。它主要基於哈希鎖、時間鎖和大型 Taproot 樹。

The prover commits to the program literally bit-by-bit, however verifying all of that on-chain would be too computationally expensive, so the verifier performs a sequence of carefully crafted challenges to succinctly disprove a false claim of the prover. Prover and verifier jointly pre-sign a sequence of challenge-and-response transactions, which they can later use to resolve any dispute.

證明者逐字節地承諾程序，但在鏈上驗證所有這些將過於計算昂貴，因此驗證者執行一系列精心設計的挑战，以簡潔地駁斥證明者的虛假主張。證明者和驗證者共同預籤一系列挑战和響應交易，可用於解決以後的任何爭議。

The model is designed to simply illustrate that this approach allows for universal computations on Bitcoin. For practical applications we should consider more efficient models.

該模型旨在簡單地說明，這種方法允許在比特幣上進行通用計算。對於實際應用，我們應該考慮更高效的模型。

The protocol is simple: Firstly, prover and verifier compile the program into a huge binary circuit. The prover commits to that circuit in a Taproot address which has a leaf script for every logic gate in the circuit. Additionally, they pre-sign a sequence of transactions, enabling a challenge-response game between the prover and the verifier. Now they have exchanged all of the required data, so they can make their on-chain deposits to the resulting Taproot address.

該協議很簡單：首先，證明者和驗證者將程序編譯成一個巨大的二進制電路。證明者在一個 Taproot 地址中承諾該電路，該地址對電路中的每個邏輯門都有一個葉子腳本。此外，他們預籤一系列交易，實現證明者和驗證者之間的挑战-響應遊戲。現在他們已經交換了所有必需的數據，所以他們可以對生成的 Taproot 地址進行鏈上存款。

This activates the contract and they can start exchanging off-chain data to trigger state changes in the circuit. If the prover makes any incorrect claim, the verifier can take their deposit. This guarantees attackers always lose their deposits.

這激活了合約，他們可以开始交換鏈下數據以觸發電路中的狀態變化。如果證明者提出任何不正確的聲明，驗證者可以拿走他們的存款。這保證了攻擊者總是會損失他們的存款。

3 比特值承諾 (Bit Value Commitment)

The bit value commitment is the most elementary component of the system. It allows the prover to set the value of a particular bit to either "0" or "1" . Especially, it allows the prover to set the value of a variable across different Scripts and UTXOs. This is key, as it extends the execution runtime of Bitcoin's VM by splitting it across multiple transactions. 比特值承諾是系統中最基本的組件之一。它允許證明者將特定比特的值設置為"0"或"1"。特別是，它允許證明者在不同的腳本和未使用的交易輸出（UTXO）之間設置變量的值。這是關鍵的，因為它通過將執行運行時拆分成多個交易來擴展比特幣的虛擬機（VM）。

Similar to Lamport signatures[3], the commitment contains two hashes, hash0 and hash1. At some later point, the prover sets the bit's value either to "0" by revealing preimage0, the preimage of hash0 – or the prover sets the bit's value to "1" by revealing preimage1, the preimage of hash1. If, at some point, they reveal both preimages preimage0 and preimage1, then the verifier can use them as a fraud proof, and take the prover's deposit. That is called equivocation. Being able to punish equivocation is what makes the commitment binding – it is an "incentive-based commitment" .

類似於Lamport籤名[3]，該承諾包含兩個哈希，hash0和hash1。在稍後的某個時刻，證明者通過揭示preimage0，即hash0的原像，將比特的值設置為"0"；或者證明者通過揭示preimage1，即hash1的原像，將比特的值設置為"1"。如果在某個時刻他們同時揭示了preimage0和preimage1，那么驗證者可以將它們用作欺詐證明，並拿走證明者的存款。這被稱為equivocation（含糊其辭）。能夠懲罰含糊其辭是使承諾具有約束力的原因 - 這是一種"基於激勵的承諾"。

Combining bit value commitments with timelocks allows the verifier to force the prover

to decide the value of a particular bit within some given time frame.

將比特值承諾與時間鎖相結合，允許驗證者在某個給定的時間範圍內強制證明者決定特定比特的值。

Figure 1: A concrete implementation for a 1-bit commitment. To unlock this script, the prover has to reveal either the preimage of hash0 or of hash1. In this example execution, the prover reveals hash1, and sets the bit's value to "1" . We can have copies of this commitment to enforce a specific value across different scripts.

圖1：一個用於1比特承諾的具體實現。為了解鎖此腳本，證明者必須揭示hash0或hash1的原像中的一個。在此示例執行中，證明者揭示了hash1，並將比特的值設置為"1"。我們可以擁有這個承諾的副本，以強制在不同腳本之間執行特定值。

For simplicity, from here on, we assume there's an opcode OP BITCOMMITMENT, which is shorthand for the script above. The opcode consumes two hashes and a preimage of one of the hashes. It puts a bit value on the stack, according to which hash is matched by the preimage.

為簡單起見，從這裏开始，我們假設存在一個名為OP_BITCOMMITMENT的操作碼，它是上述腳本的縮寫。該操作碼消耗兩個哈希和其中一個哈希的原像。根據原像匹配的哈希，它將比特值放在堆棧上。

4 邏輯門承諾 (Logic Gate Commitment)

Any computable function can be represented as a Boolean circuit. The NAND gate is a universal logic gate, so any Boolean function can be composed from them. To keep our model simple, we show that our method works for simple NAND gates. Additionally, we show how to compose gates arbitrarily. Together this demonstrates BitVM can express any circuit.

任何可計算函數都可以表示為布爾電路。與非門（NAND）是一種通用邏輯門，所以任何布爾函數都可以由它組成。為保持模型簡單，展示了我們的方法適用於簡單的與非門。此外，我們展示了如何任意組合門。這一起證明了 BitVM 可以表達任何電路。

The implementation of a NAND gate commitment is simple. It contains two bit commit- ments representing the two inputs and a third bit commitment representing the output. The Script computes the NAND value of the two inputs to ensure that it matches the committed output bit.

與非門承諾的實現很簡單。它包含代表兩個輸入的兩個位承諾和代表輸出的第三個位承諾。腳本計算兩個輸入的與非值，以確保它與承諾的輸出位相匹配。

Figure 2: Logic gate commitment for a NAND operation. Executing this script requires to reveal values for the bit commitments A, B, and C, such that A NAND B = C holds.

圖2：NAND操作的邏輯門承諾。執行此腳本需要揭示比特承諾A、B和C的值，使得A NAND B = C成立。

(Here, we assume for simplicity, that an opcode for OP_NAND exists . Actually it does not exist, however, it can be easily implemented using OP_BOOLAND and OP_NOT.)

（在這裏，我們為簡單起見假設存在用於OP_NAND的操作碼。實際上它並不存在，然而，可以使用OP_BOOLAND和OP_NOT輕松實現。）

5 二進制電路承諾 (Binary Circuit Commitment)

In the previous section we defined NAND gate commitments. We can express any circuit by composing gate commitments. Every step of the execution is committed to in a Tapleaf. They're are all combined into the same Taproot address, such that the prover could execute any gate in the circuit. Executing a gate requires the prover to open the corresponding gate commitment and set values for its inputs and output bits.

The Taptree might become huge and have a billion Tapleaf Scripts, but its on-chain footprint is minimal.

上一節，定義了與非門承諾。通過組合門承諾來表達任何電路。執行的每一步都在一個 Tapleaf 中提交。它們都合並到同一個 Taproot 地址中，使得證明者可以執行電路中的任何門。執行一個門需要證明者打开相應的門承諾，並為其輸入和輸出位設置值。 Taptree 可能變得非常龐大，擁有十億個 Tapleaf 腳本，但它在鏈上的足跡卻很小。

Figure 3: A random example circuit which has 8 different NAND gates, and 4 inputs A,B,C, and D. Using billions of gates would allow us to define basically any function.

圖3：一個隨機示例電路，有8個不同的與非門和4個輸入A、B、C和D。使用數十億個門將允許我們定義基本上任何函數。

Figure 4: For each gate, the prover's Taproot address contains a leaf script with a corresponding gate commitment. This allows the prover to set the values of the circuit's inputs, (here, A,B ,C, and D), at any point later in time.

圖4：對於每個門，證明者的 Taproot 地址包含一個帶有相應門承諾的葉腳本。這使證明者可以在以後的任何時候設置電路的輸入值（這裏是A、B、C和D）。

6 挑战與響應 (Challenges and Responses)

Committing to a circuit is not enough. To disprove an incorrect claim, the verifier has to be able to challenge the prover's statement. This is possible by them pre-signing a sequence of transactions during setup. The transactions are linked like challenge → response → challenge → response → .... If one of the parties stops engaging then, after some timeout, the other party wins the challenge and can take both deposits. As long as both parties are cooperative, they can jointly settle any contract with a 2-of-2 signature. The following mechanism is required only in case of fraud.

承諾一個電路是不夠的。為了駁斥一個不正確的主張，驗證者必須能夠挑战證明者的聲明。這是通過他們在設置期間預先籤署一系列交易來實現的。這些交易像挑战 → 響應 → 挑战 → 響應……這樣鏈接起來。如果雙方中的一方停止參與，那么在一定的超時後，另一方將贏得挑战並可以拿走雙方的存款。只要雙方合作，他們可以用2-of-2籤名共同解決任何合約。以下機制僅在欺詐情況下需要。

Figure 5: A pre-signed sequence of transactions to perform multiple rounds of challenge-and-response. This sequence is generated during setup.

圖5：在設置期間生成的一系列預籤交易，用於執行多輪挑战和響應。

Vicky chooses a challenge by opening one of the hashlocks in her Tapscript leaves. This unlocks for Paul a specific Tapscript and forces him to execute it. The script forces Paul to reveal the gate commitment challenged by Vicky. Any inconsistent claim can be disproven quickly by repeating this procedure for a few rounds of queries.

Vicky通過打开她的Tapscript葉中的一個哈希鎖來選擇一個挑战。這為Paul解鎖了一個特定的 Tapscript，並迫使他執行它。腳本迫使 Paul 揭示 Vicky 所挑战的門承諾。通過重復這個程序幾輪查詢，任何不一致的主張都可以迅速被駁斥。

If the prover stops collaborating with the verifier off-chain, the verifier needs a way to force his hand on-chain. The verifier does this by unlocking a hashlock: each of the NAND Tapleaves in the prover's UTXO can only be spent if the prover knows a preimage held by the verifier. Therefore, the prover can prove that a given Tapleaf executes correctly by revealing its inputs and outputs, but only if the verifier "unlocks" it for him by revealing the preimage to the hash that guards that Tapleaf. Applying binary search, the verifier can quickly identify the prover's error after just a few rounds of challenge-and-response.

如果證明者停止與驗證者的鏈下合作，驗證者需要一種方法在鏈上強迫他的行動。驗證者通過解鎖一個哈希鎖來做到這一點：證明者的UTXO中的每個與非 Tapleaf 只有在證明者知道驗證者持有的一個原像時才能被消費。因此，證明者可以通過揭示其輸入和輸出來證明給定的 Tapleaf 正確執行，但僅當驗證者通過揭示守衛該 Tapleaf 的哈希的原像為他"解鎖"時才能這樣做。應用二分查找，驗證者在log(N)輪挑战和響應後就可以快速識別證明者的錯誤。

Figure 6: After each response, Vicky can punish equivocation. If Paul ever reveals two conflicting values for a variable, then Vicky immediately wins the challenge and is allowed to take his deposit. Vicky proves Paul's equivocation by revealing for any of his bit commitments both of the preimages.

圖6：在每次響應後，Vicky可以懲罰含糊其辭。如果 Paul 曾經為變量揭示兩個矛盾的值，那么 Vicky 立即贏得挑战，並被允許拿走他的存款。Vicky 通過揭示 Paul 的任何一個位承諾的兩個原像來證明 Paul 的含糊其辭。

7 輸入與輸出 (Inputs and Outputs)

The prover can set inputs by revealing the corresponding bit commitments. Ideally, they reveal the commitments off-chain to minimize their on-chain footprint. In the noncooperative case the verifier can force the prover to reveal their inputs on-chain.

證明者可以通過揭示相應的比特承諾來設置輸入。理想情況下，他們會在鏈外揭示這些承諾，以最小化在鏈上的佔用。在非合作情況下，驗證者可以強制證明者在鏈上揭示他們的輸入。

It is possible to process large amounts of data by exchanging it upfront, but encrypted. This way the prover can reveal the decryption key at a later point in time.

通過預先交換數據但加密的方式，可以處理大量數據。這樣證明者可以在之後的某個時刻揭示解密密鑰。

Multi-party inputs are also possible. Gates can have bit commitments from both parties.

多方輸入也是可能的。門可以有來自雙方的位承諾。

8 局限性與展望 (Limitations and Outlook)

It is inefficient to express functions in simple NAND circuits. Programs can be expressed more efficiently by using more high-level opcodes. E.g., Bitcoin script supports adding 32-bit numbers, so we need no binary circuit for that. We could also have larger bit commitments, e.g. it is possible to commit to 32 bits in a single hash. Additionally, scripts can be up to about 4 MB in size. Thus, we can implement substantially more than a single NAND instruction per leaf script.

在簡單的NAND電路中表達函數是低效的。通過使用更高級的操作碼，程序可以更有效地表達。例如，比特幣腳本支持添加32位數字，因此我們無需為此使用二進制電路。我們還可以擁有更大的比特承諾，例如，可以在單個哈希中承諾32位。此外，腳本的大小可以達到約4 MB。因此，我們可以在每個葉子腳本中實現遠遠超過一個NAND指令。

The model proposed here is limited to two parties. However, it might be possible to have two-way channels, and chain them to form a network similar to Lightning. Exploring the two-party setting might yield interesting possibilities for generalization. For example, we can explore a 1-to-n star topology for the network. Another research question is if we can apply our model to the n-of-n setting and create more sophisticated channel factories. Furthermore, we could combine our system with different off-chain protocols, e.g., the Lightning Network or rollups.

這裏提出的模型僅限於兩方。然而，可能可以建立雙向通道，並將它們鏈式連接以形成類似於閃電網絡的網絡。探索雙方設置可能會產生一些有趣的泛化可能性。例如，我們可以探索網絡的1對n星型拓撲結構。另一個研究問題是我們是否可以將我們的模型應用於n-of-n設置，並創建更復雜的通道工廠。此外，我們還可以將我們的系統與不同的鏈下協議結合使用，例如閃電網絡或rollups。

Other directions of research include cross-application memory, how to make statements about arbitrary data inscribed into the chain, or off-chain programmable circuits, i.e. an off-chain VM. It also might be possible to apply more sophisticated sampling techniques, similar to STARKs, to check a circuit in a single round.

其他研究方向包括跨應用內存、如何對刻在鏈上的任意數據進行陳述，或鏈下可編程電路，即鏈下虛擬機。還有可能應用更復雜的採樣技術，類似於STARKs，以在單一輪中檢查電路。

The next major milestone is to complete a design and an implementation of a concrete BitVM and also of Tree++, a high-level language to write and debug Bitcoin contracts.

下一個重要的裏程碑是完成具體的BitVM設計和實現，以及Tree++，一個用於編寫和調試比特幣合約的高級語言。

9 結論(Conclusion)

Bitcoin is Turing-complete in the sense that encoding fraud proofs in large Taptrees allows to verify the execution of any program. A major constraint of the model outlined here is that it is limited to the two-party setting. Hopefully, this can be generalized in further works.

比特幣在編碼欺詐證明的大型 Taptrees 中可以驗證任何程序的執行，因此在某種意義上是圖靈完備的。這裏概述的模型的一個主要限制是它僅限於兩方設置。希望這可以在後續工作中得到泛化。

致謝(Acknowledgments)

Special thanks to Super Testnet and Sam Parker, who always kept refusing to believe that Bitcoin would not be Turing-complete.

特別感謝Super Testnet和Sam Parker，他始終拒絕相信比特幣不會是圖靈完備的。

參考文獻(References)

[1] Ethereum Research. Optimistic 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.

[3] Jeremy Rubin. CheckSigFromStack for 5 Byte Values. https://rubin.io/blog/2021/07/02/signing-5-bytes, 2021.