撰文: lynndell, mutourend
1. 引言
比特币是一种去中心化、安全且值得信赖的数字资产。但是，它存在重大限制，无法成为支付和其他应用的可扩展网络。比特币的扩容问题自诞生以来就一直备受关注。比特币 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 的效率和安全性。
2.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，从实现电路承诺。
- 挑战和响应：证明者和验证者预签一系列交易来实现挑战 - 响应游戏。理想情况下，这种互动是在链下进行的，当证明者不配合时，也可在链上执行。
- 模棱两可惩罚：如果证明者提出任何不正确的声明，则验证者挑战成功后可拿走证明者存款，挫败证明者的作恶行为。
3.BitVM 优化
3.1 基于 ZK 降低 OP 交互次数
当前有 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 的计算成本。
3.2 比特币友好的一次性签名
比特币网络中，遵循共识规则的交易是有效交易，但除共识规则之外，还额外引入了 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 比特币脚本实现进行优化的同时，可探索以比特币脚本表达的更紧凑的一次性签名方案。
3.3 比特币友好的哈希函数
根据共识规则，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 等哈希函数，从中选出最比特币友好的哈希函数，并探索其它新的比特币友好哈希函数。
3.4 Scriptless Scripts BitVM
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 功能模块内。
3.5 无需许可的多方挑战
当前 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 无需许可多方挑战模型。
4. 结论
BitVM 技术探索才刚刚开始，未来将探索和实践更多的优化方向，以实现对比特币的扩容，繁荣比特币生态。
参考文献
1.BitVM: Compute Anything on Bitcoin
2.BitVM：Off-chain Bitcoin Contracts
3.Robin Linus on BitVM
4.[bitcoin-dev] BitVM: Compute Anything on Bitcoin
5.The Odd Couple: ZK and Optimistic Rollups on a Scalability Date
6.What are Bitcoin's transaction and script limits?
7.BIP-342: Validation of Taproot Scripts
8.https://twitter.com/robin_linus/status/1765337186222686347
9.A Graduate Course in Applied Cryptography
10.BLAKE3: one function, fast everywhere
11.[bitcoin-dev] Implementing Blake3 in Bitcoin Script
12.https://github.com/BlockstreamResearch/scriptless-scripts
13.Introduction to Scriptless Scripts
14.BitVM using Scriptless Scripts
15.Solutions to Delay Attacks on Rollups
16.Introducing DAVE. Cartesi's Permissionless Fault-Proof System.
17.Delay Attacks on Rollups
18.Solutions to Delay Attacks on Rollups - Arbitrum Research
19.Multiplayer Interactive Computation Games Notes
20.BoLD: Bounded Liquidity Delay in a Rollup Challenge Protocol
21.Permissionless Refereed Tournaments
