t) 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. 来源：金色财经lg...
北美站
