作者: mutourend & lynndell, Bitlayer Labs
原文标题：《Analysis of Bitcoin Layer2 Scaling Techniques: Validity Proofs and Fraud Proofs》
原文链接：https://blog.bitlayer.org/Analysis_of_Bitcoin_Layer2_Scaling_Techniques_Validity_Proofs_and_Fraud_Proofs/
1 引言
对于某个算法 f，两个互不信任的参与方 Alice 和 Bob，可通过如下方式建立信任：
Alice 输入 x，运行算法 f，获得结果 y。Bob 基于相同的输入 x，也运行算法 f，结果为 y′。如果 y = y′，则 Bob 认可 Alice 提供的输入 x 和输出 y。这是一种特殊的有效性证明机制，常用于区块链共识。其中，Alice 为打包区块的节点，Bob 为参与共识的节点。
Alice 输入 x，对算法 f 运行 zk.prove 程序，获得结果 y 和证明 proof。Bob 根据 f、y 和 proof，运行 zk.verify 程序。如果结果为 true，则 Bob 认可 Alice 的结果 y；如果结果为 false，则 Bob 不认可 Alice 的结果 y。这是有效性证明。其中，Bob 可以是链上合约。
Alice 输入 x，运行算法 f，获得结果 y。Bob 基于相同的输入 x，也运行算法 f，结果为 y′。如果 y = y′，则什么也不做；如果 y ≠ y′，则 Bob 对 Alice 发起挑战，所挑战的程序为 f。Alice 与 Bob 的交互次数可为一次或多次。根据挑战响应流程来实现仲裁。这是欺诈证明。其中，Bob 为挑战者，在链下监听，在链上挑战。
Alice 输入 x，对算法 f 运行 zk.prove 程序，获得结果 y 和证明 proof。Bob 根据 f、y 和 proof，运行 zk.verify 程序。如果结果为 true，则什么也不做；如果结果为 false，则 Bob 对 Alice 发起挑战，所挑战的程序为 zk.verify。Alice 与 Bob 的交互次数可为一次或多次。Alice 与 Bob 的交互次数可为一次或多次。根据挑战响应流程来实现仲裁。这是欺诈证明。其中，Bob 为挑战者，在链下监听，在链上挑战。
对于以上 2,3,4，令 x 为 Layer2 交易和起始状态，f 为 Layer2 共识程序，y 为交易结束状态，则对应为区块链 Layer2 扩容方案。其中：
有效性证明（Validity Proof）：基于悲观假设，必须证明有效后才接纳，且即时生效。在有效性证明中，需提供 L2 状态转换正确的证据，反应了对世界的悲观看法——当且仅当证明某状态正确时，才会接纳该状态。
欺诈证明（Fraud Proof）：基于乐观假设，默认接纳，除非有人证明有误才拒绝。具有挑战窗口期，挑战窗口期过后才生效。在欺诈证明中，需提供 L2 状态转换不正确的证据，反应了对世界的乐观看法——某状态转换默认是正确的，除非证明其不正确。
表 1: 信任建立方式
此外，需要注意：
区别欺诈证明和有效性证明的关键不是判断是否使用了 SNARK/STARK 等 ZK 证明系统。ZK 证明系统所表达的是所用的证明方式，而欺诈还是有效性，则代表的是所证明的内容。这也是为何说表1中场景 1 所表示的为有效性证明。
有效性证明时效性更佳，但链上验证复杂度相对高；欺诈证明链上验证复杂度更低，但时效性相对差。
对于表1中 2 和 4 情况，借助 ZK 递归和组合技术，可对多个 f 进行计算压缩，大幅分摊降低链下计算在链上的验证成本。
当前，受益于 solidity 图灵完备智能合约，欺诈证明和有效性证明技术广泛用于以太坊 Layer2 扩容。但是，在比特币范式下，受限于比特币有限的操作码功能、1000 个 stack 元素等限制，这些技术应用仍处于探索阶段。本文针对比特币 Layer2 扩容场景下，总结了比特币范式下的限制和突围技术，研究有效性证明和欺诈证明技术，并梳理了比特币范式下所独有的脚本切分技术。
2 比特币范式下的限制和突围
比特币范式下有诸多限制，但是能够使用各种巧妙方法或技术来突破这些限制。例如，比特承诺可突破 UTXO 无状态限制、taproot 可突破脚本空间限制、connector output 可突破 UTXO 花费方式限制、契约可突破预签限制。
2.1 UTXO 模型与脚本限制
比特币采用 UTXO 模型，每个 UTXO 都锁定在 locking 脚本中，该脚本定义了花费该 UTXO 所必须满足的条件。比特币脚本具有如下局限性：
比特币脚本是无状态的；
对于P2TR输出类型，单笔交易中可容纳的操作码总数最多约为 400 万个，会填满整个区块，而对于其他输出类型则仅有 1 万个操作码；
单个 UTXO 的花费方式有限，缺少组合花费方式的探索；
不支持灵活的契约功能；
栈大小最多限制为 1000 个元素（altstack + stack），且单个元素最大 size 为 520 字节；
算术运算（如加法、减法）仅限于 4 字节元素。无法修改为长元素，如 20 字节或更大的元素，但这是密码学运算所必需的；
OP_MUL和OP_CAT等操作码均已被禁用，若使用现有操作码进行模拟，成本极高，如模拟 one-round BLAKE3 哈希，script size 约为 75K。
2.2 比特承诺：突破 UTXO 无状态限制
当前比特币脚本是完全无状态的。当执行比特币脚本时，其执行环境在每个脚本之后都会被重置。这导致比特币脚本无法原生支持约束脚本 1 和脚本 2 拥有相同的 x 值。但是，可通过一些方法来绕过该问题，其核心思想是以某种方式对一个值进行签名。如果可对一个值创建签名，则能够实现有状态的比特币脚本。即需通过在脚本 1 和脚本 2 中检查 x 值的签名，就可强制脚本 1 和脚本 2 中使用相同的 x 值。如果存在冲突签名，即对同一变量 x 签署了 2 个不同的值，则可对其进行惩罚。该解决方案即为 bit commitment（比特承诺）。
Bit commitment 的原理相对简单。所谓 bit，是指对待签名消息中的每个 bit，设置 2 个不同的哈希值，即 hash0 和 hash1。如果需要签署的 bit 值为 0，则揭露 hash0 的原像 preimage0；如果需要签署的 bit 值为 1，则揭露 hash1 的原像 preimage1。
以单个 bit 消息 m ∈{0,1}为例，相应的 bit commitment 解锁脚本只是一些原像：如果该 bit 值为0，则对应的解锁脚本为preimage0——”0xfa7fa5b1dea37d71a0b841967f6a3b119dbea140”；如果该bit值为1，则相应的解锁脚本为 preimage1——”0x47c31e611a3bd2f3a7a42207613046703fa27496”。因此，借助 bit commitment，可突破 UTXO 无状态限制，实现有状态的比特币脚本，从而使得各种有趣的新特性变得可能。
OP_HASH160
OP_DUP
<0xf592e757267b7f307324f1e78b34472f8b6f46f3> // This is hash1
OP_EQUAL
OP_DUP
OP_ROT
<0x100b9f19ebd537fdc371fa1367d7ccc802dc2524> // This is hash0
OP_EQUAL
OP_BOOLOR
OP_VERIFY
// Now the value of the bit commitment is on the stack. Either ”0” or ”1”.
比特承诺目前有 2 种实现方式：
Lamport 一次性签名：原理相对简单，仅需要使用哈希函数，所以是比特币友好的。对于消息中的每一位，均需要承诺 2 个哈希值，导致签名数据相对较大。换言之，对于一个长度为 v bits 的消息，公钥长度为 2v bits，签名长度为 v bits。
Winternitz 一次性签名：相比于 Lamport 签名，可大幅降低签名和公钥长度，但是增加了签署和验签复杂度。该方案可灵活设置不同的 hash chain 长度 d 值，从而在长度和复杂度方面进行权衡。例如，设置 d =15时，则公钥长度和签名长度均要短约 4 倍，但是验签复杂度将提高 4 倍。这本质上是在比特币栈空间和 script size 之间的取舍。Lamport 签名可视为 Winternitz 签名中 d =1时的特例。
目前，BitVM2 库中，基于 Blake3 的哈希函数实现了 Winternitz 签名。单个 bit 对应的签名长度约为 26 字节。由此可知，通过 bit commitment 来引入状态，成本是昂贵的。因此，在 BitVM2 工程实现中，首先对消息进行哈希运算获得 256bit 的哈希值，然后再对哈希值进行 bit commitment，从而节约开销，而不是直接对原始较长的消息的每个 bit 进行承诺。
2.3 Taproot：突破脚本空间限制
自 2021 年 11 月激活的比特币 Taproot 软分叉升级中包含 3 个提案：Schnorr 签名（BIP 340），Taproot （BIP 341）和TapScript（BIP 342）。引入了一种新的交易类型——Pay-to-Taproot（P2TR）交易。P2TR 交易通过结合 Taproot、MAST（默克尔抽象语法树）和 Schnorr 签名的优点，可创建更私密、灵活和可扩展的交易格式。
P2TR 支持两种花费方式：根据 key path 或 script path 实现花费。
根据Taproot（BIP 341）中的规定，当按 script path 花费时，对应的 Merkle path 最大长度不超过 128。这意味着 taptree 中 tapleaf 个数不超过2128 个。自 2017 年 segwit 升级以来，比特币网络以 weight units 来衡量区块大小，最大支持 400 万 weight units（即约 4MB）。某 P2TR output 通过 script path 被花费时，实际只需要揭露某单个 tapleaf 脚本，即区块打包的为单个 tapleaf 脚本。这意味着，对于 P2TR 交易，对应每个 tapleaf 的脚本 size 最大约为 4MB。不过比特币默认策略中，许多节点只转发小于 400K 的交易，更大的交易若想被打包，则需跟矿工合作。
Taproot 所带来的脚本空间溢价，使得用现有 opcode 模拟乘法、哈希等密码学运算更具价值。
当基于 P2TR 构建可验证计算时，所对应的 script size 可不再受限于 4MB 的限制，而是可将该计算切分为多个子函数，将其分布在多个 tapleaf 上，从而突破 4MB 的脚本空间限制。事实上，当前 BitVM2 中所实现的 Groth16 verifier 算法，其 size 高达 2GB。但是，能够对其切分并分布在约 1000 个 tapleaf 中，通过与 bit commitment 结合使用，可通过约束各子函数输入输出之间的一致性，约束整个计算的完整性和正确性。
2.4 Connector output：突破 UTXO 花费方式限制
比特币目前提供的单个 UTXO 原生花费方式有：按脚本花费，或按公钥花费。因此，只要提供了对应正确的公钥签名或满足脚本条件，则能够花费该 UTXO。两个 UTXO 是可独立花费的，不能添加限定措施以约束两个 UTXO，使得需满足一些额外条件才可被花费。
但是，Ark 协议的创始人 Burak，通过巧妙借助 SIGHASH flag，实现了 connector output。具体而言，Alice 可创建一个签名，将其 BTC 发送给 Bob。但是，由于签名可对多个 Inputs 进行 commit，Alice 可设置其签名是有条件的：该签名对 Take_tx 交易是有效的，当且仅当该交易消耗了第二个 input。第二个 input 就称为connector，连接了 UTXO A 和 UTXO B。换言之，Take_tx 交易有效，当且仅当 UTXO B 未被 Challenge_tx 花费掉。因此，通过销毁 connector output，即可阻断 Take_tx 交易生效。
图 1: connector output 示意
在 BitVM2 协议中，connector output 充当 if...else 功能。一旦 connector output 被某交易花费，就不能被另一笔交易花费，以确保其独占性花费。在实际部署中，为预留挑战响应周期，额外引入了具有 timelock 的 UTXO。此外，相应的 connector output 也可根据需要设置不同的花费策略，如对挑战交易可设置为任何人可花费，而对响应交易可设置为仅 operator 可花费或超期后任何人可花费。
2.5 契约：突破预签限制
目前比特币脚本主要限制了解锁的条件，而没有限制该 UTXO 如何进一步被花费。其原因在于比特币脚本无法读取交易自身的内容，即无法实现交易自省。如果比特币脚本能够检查交易的任何内容（包括 output），就可实现契约功能。
当前的契约实现方式可分为两类：
预签：基于现有比特币脚本能力，通过预签构建功能有限的预先确定的契约。即提前设计和签署所有可能的未来交易，将参与方锁定在特定的私钥和费率中。一些方案甚至要求参与方生成用于所有预签名交易的短期私钥。当预签完成后，则安全地删除这些短期私钥，使得攻击者无法获得短期私钥，从而盗走资金。但是，每次新增参与方，或更新操作时，均需要重复以上过程，导致维护成本繁重。例如，闪电网络通过预签实现了 2 方契约，并借助哈希时间锁（HTLC）技术，实现了多个 2 方契约的路由功能，从而实现信任最小化的扩容策略。但是，闪电网络需预签多笔交易，且仅限于两方，略显笨重；在 BitVM1 中，每次初始化时均需要预签数百笔交易，而优化后的 BitVM2 中，每次初始化时需要预签的交易数也达数十笔。无论是 BitVM1 还是 BitVM2，只有参与预签的 operator，才有资格进行报销。如果有 n 个参与方参与预签，每个参与方需预签 m 笔交易，则每个参与方的预签复杂度将为 n ∗ m。
引入契约操作码：引入新的契约功能操作码，可大幅降低契约参与方之间的通信复杂度和维护成本，从而为比特币引入更灵活的契约实现方式。例如，OP_CAT：用于拼接字节字符串。尽管其功能非常简单，但是功能非常强大，能够大幅降低 BitVM 复杂度；OP_TXHASH：能够以更好的粒度控制契约内的动作。如果在 BitVM 中使用，则能够支持更大的 operator 集合，从而大幅改进 BitVM 的安全假设，让其信任最小化。此外，预签方式注定了 BitVM 设计中，operator 只能采用垫付报销流程，资金利用效率较低；而通过新的契约操作码，有可能实现直接从 peg-in 资金池付款给出金用户，进一步提高资金效率。因此，灵活的契约模式，将有效突破传统预签限制。
3 比特币Layer2扩容：有效性证明与欺诈证明
有效性证明与欺诈证明均可用于比特币L2扩容，二者的主要区别如表2所示。
表 2: 有效性证明与欺诈证明
基于比特承诺、taproot、预签和 connector output，可构建基于比特币的欺诈证明。基于 taproot，同时通过引入契约操作码，如 OP_CAT，可构建基于比特币的有效性证明。此外，根据 Bob 是否有准入制度，欺诈证明可分为许可式欺诈证明和无需许可式欺诈证明。其中，许可式欺诈证明中，仅特定群体才能作为 Bob 发起挑战，而无需许可式欺诈证明中，任意第三方均可作为 Bob 发起挑战。无需许可式的安全性要优于许可式，可降低各许可参与方窜谋作恶的风险。
根据 Alice 和 Bob 挑战响应交互的次数，欺诈证明可分为一轮欺诈证明和多轮欺诈证明，如图2所示。
图 2: 一轮欺诈证明与多轮欺诈证明
如表3所示，欺诈证明可以通过不同的交互模型来实现，包括一轮交互模型和多轮交互模型。
表 3: 一轮交互与多轮交互
在比特币 Layer2 扩容范式下，BitVM1 采用多轮欺诈证明机制，BitVM2 采用一轮欺诈证明机制，bitcoincircle stark采用有效性证明。其中，BitVM1 和 BitVM2 可在不对比特币协议做任何修改的情况下实施，而bitcoin-circle stark 需要引入新的操作码 OP_CAT。
对于大多数计算任务，比特币 signet,testnet 和 mainnet 均无法以 4MB 的脚本来完整表示，需要使用脚本Split 技术——即将表达完整计算的脚本，切分为小于 4MB 的 chunk，分布到各个 tapleaf 中。
3.1 比特币上的多轮欺诈证明
如表3中所示，多轮欺诈证明适于希望降低链上仲裁计算量，和（或）无法一步定位出问题计算片段的场景。多轮欺诈证明，顾名思义，证明者和验证者之间，需要多轮交互以定位出问题计算片段，然后再基于所定位出的计算片段进行仲裁。
Robin Linus 早期的BitVM 白皮书（通常称为 BitVM1），使用的多轮欺诈证明。假设每轮挑战期为一周，采用二分查找法定位问题计算片段，则对 Groth16 Verifier 的链上挑战响应周期将高达 30 周，时效性极差。尽管当前有团队在研究比二分法更高效的 n-ary 查找法，但相比于一轮欺诈证明中的 2 周周期，其时效性仍低很多。
目前，比特币范式下的多轮欺诈证明均采用许可式挑战，而一轮欺诈证明实现了无需许可式挑战方式，降低了参与方串谋风险，从而安全性更高。为此，Robin Linus 充分利用了 taproot 的优势，对 BitVM1 进行优化。不仅将交互轮次降低至 1 轮，还将挑战方式扩展为无需许可式，但是其代价是增加了链上仲裁计算量。
3.2 比特币上的一轮欺诈证明
在证明者和验证者之间仅通过一次交互，即可完成验证欺诈证明。该模型中，验证者仅需发起一次挑战，证明者只需做一次响应。在该响应中证明者需提供一个证据，声称其计算是正确的。如果验证者能够从该证据中找出不一致性，则挑战成功，否则挑战失败。一轮交互欺诈证明的特点如表3所示。
图 3: 一轮欺诈证明
Robin Linus 2024 年 8 月 15 日发布了BitVM2: Bridging Bitcoin to Second Layers技术白皮书中，采用类似图3的方式，以一轮欺诈证明方式，实现了 BitVM2 跨链桥。
3.3 比特币 +OP_CAT 实现有效性证明
OP_CAT 是比特币最初发布时脚本语言的一部分，因安全漏洞问题在 2010 年被禁用。但是，数年来，比特币社区一直在讨论将其激活。目前OP_CAT 已被分配编号 347且已在比特币 signet 上启用。
OP_CAT 主要功能是将堆栈中的两个元素结合起来，并将合并后的结果推回堆栈。这个功能特性，开启了比特币上的契约和 STARK Verifier：
契约：Andrew Poelstra 提出CAT and Schnorr Tricks I，使用 OP_CAT 和 Schnorr 技巧在比特币上实现契约。其中，Schnorr 算法是 P2TR 输出类型的数字签名；对于其他输出类型，可以使用类似的 ECDSA 技巧，见Covenants with CAT and ECDSA。借助 OP_CAT 契约，可协助将 STARK Verifier 算法拆分为多笔交易，逐步验证整个 STARK proof。
STARK Verifier：STARK Verifier 本质上是将数据连接在一起并对其进行哈希运算。与代数运算不同，哈希运算是一种原生比特币脚本操作，可以节省大量开销。以 OP_SHA256 为例，原生方式仅为一个操作码，而模拟方式则需要数百 K 个。STARK 中的主要哈希运算是 Merkle 路径的验证和 Fiat-Shamir 变换。因此，OP_CAT 对 STARK Verifier 算法非常友好。
3.4 比特币脚本 Split 技术
尽管经 SNARK/STARK 证明后，运行相应 verifier 算法验证 proof 所需的计算量要远小于直接运行原始计算 f 所需的计算量。但是，将其转换为以比特币脚本实现 verifier 算法时，所需的脚本量仍然是巨大的。当前，基于现有比特币操作码，经优化后，所实现 Groth16 verifier 脚本 size 和 Fflonk verifier 脚本 size 仍均大于 2GB。然而，比特币单个区块 size 仅为 4MB，无法在单个区块内运行整个 verifier 脚本。但是，比特币自taproot 升级后，支持按 tapleaf 执行脚本，可将 verifier 脚本切分为多个 chunks，然后以每个 chunk 为 tapleaf，构建 taptree。各个 chunk 之间，借助 bit commitment 来保证 chunk 之间值的一致性。
在有 OP_CAT 契约情况下，可将 STARK Verifier 拆分为多笔小于 400KB 的标准交易，从而可在无需与矿工协作的情况下，完成整个 STARK 有效性证明的验证。
本节，重点关注的是未引入激活任何新操作码的现有情况下，比特币脚本的相关 Split 技术。
当进行脚本切分时，需平衡如下维度信息：
单个 chunk script size 不超过 4MB，需包含 input bit commitment 脚本、交易签名等空间。
单个 chunk stack size 最大不超过 1000。所以应让各个 chunk stack 上仅保留所需的元素，从而预留足够的 stack 空间来为 script size 优化服务。因为比特币交易手续费不取决于所用 stack size。
比特币上的 bit commitment 是昂贵的。所以当前 1 个 bit 对应 26 字节，应让相邻 2 个 chunk 间的输入输出的 bits 数量最小化。
为便于审计，每个 chunk 的功能应尽可能明确。
当前，脚本的切分方式主要分为以下 3 大类：
自动切分：根据 stack size 和 script size，寻找 script size 为 3MB 左右而 stack size 最小的切分方式。这种方式的优点在于：与具体的 verifier 算法无关，可扩展为任意计算的脚本切分。缺点在于：（1）需单独标记整块逻辑，如 OP_IF 代码块不可被切分，否则切分后的脚本执行结果将不正确；（2）chunk 执行结果可能对应 stack 上的多个元素，需根据实际计算逻辑来标记需应用 bit commitment 的栈元素个数；（3）每个 chunk 脚本所实现逻辑功能可读性差，不利于审计；（4）stack 上可能包含下一 chunk 不需使用的元素，浪费栈空间。
功能性切分：根据计算中的各个功能子函数来切分，子函数的输入输出值明确，在脚本切分的同时，也实现了各个 chunk 所需的 bit commitment 脚本，使最终的 chunk 总脚本 size 小于 4MB，stack size 小于 1000 即可。优点在于：功能清晰，单个 chunk 逻辑明确，可读性好，便于审计。缺点在于：原始计算逻辑的表达，与脚本级逻辑的表达，是不匹配的，原始计算子函数可能最优，并不代表脚本级最优。
人工切分：脚本切分点不在于功能子函数，而是人工设置切分点。尤其适合于单个子函数 size 大于4MB 的情况。优点在于：可对 heavy script size 子函数，如 Fq12 相关计算子函数进行人工切分；单个 chunk 逻辑明确，可读性好，便于审计。缺点在于：受限于人工调优能力，当总体脚本做了优化后，之前设置的各个人工切分点可能不是最优，需重新调整。
例如，Groth16 verifier 经过多轮优化，其 script size 由约 7GB 降低至约 1.26GB。除做这种总体计算优化外，还可对各个 chunk 单独优化，以充分利用 stack 空间。如可通过引入更优的基于 lookup table 的算法，并对 lookup table 进行动态加载卸载，可进一步降低每个 chunk 的 script size。
web2 编程语言计算成本和运行环境，与比特币脚本成本和运行环境完全不同，所以对于各种算法的比特币脚本实现，仅翻译现有实现是行不通的。因此，需针对比特币场景，考虑以下优化：
寻找内存局部性最优的算法，哪怕牺牲部分计算量，可降低 chunk 间输入输出 bits 数，从而降低 BitVM2 设计中的 assertTx 交易所需承诺的数据量。
利用相关运算（如逻辑运算）的可交换性，x&y = y&x，节约几乎一半的查找表。
当前，Fq12 运算对应的脚本量很大，可考虑借助 Fiat-Shamir、Schwartz-Zipple 和多项式承诺方案，大幅降低 Fq12 扩域运算的计算复杂度。
4 小结
本文首先介绍了比特币脚本限制，并介绍使用比特币承诺突破 UTXO 无状态限制、使用 Taproot 突破脚本空间限制、使用 connector output 突破 UTXO 花费方式限制，使用契约突破预签限制。然后对欺诈证明和有效性证明的特点、许可式欺诈证明和无需许可式欺诈证明的特点、一轮欺诈证明和多轮欺诈证明的特点、比特币脚本切分技术进行了全面的梳理和总结。
参考文献
OP_IF, OP_CAT, OP_SHA256
Lamport one-time signature
Winternitz one-time signature
BitVM: Compute Anything on Bitcoin
BitVM2: Bridging Bitcoin to Second Layers
CAT and Schnorr Tricks I
Covenants with CAT and ECDSA
Validity Rollups on Bitcoin
StarkWare, Validity Proofs vs. Fraud Proofs, 2019.01.23
StarkWare, Validity Proofs vs. Fraud Proofs, 2024.05.09
StarkWare, The path to general computation on Bitcoin, 2024.07.24
BitVMX, Optimizing Algorithms for Bitcoin Script, 2024.06.27
Alchemy, How Do Optimistic Rollups Work (The Complete Guide), 2023.08.09
Ethereum, Optimistic Rollups Fraud proving, 2024.07.17
ZeroSync: Introducing Validity Proofs to Bitcoin
Robin Linus on BitVM, 2024.01.16
SNARK Verifier in Bitcoin Script
