比特币范式下有诸多限制,但是能够使用各种巧妙方法或技术来突破这些限制。
原文标题:《Analysis of Bitcoin Layer2 Scaling Techniques: Validity Proofs and Fraud Proofs》
撰文:mutourend & lynndell, Bitlayer Labs
对于某个算法 f,两个互不信任的参与方 Alice 和 Bob,可通过如下方式建立信任:
对于以上 2,3,4,令 x 为 Layer2 交易和起始状态,f 为 Layer2 共识程序,y 为交易结束状态,则对应为区块链 Layer2 扩容方案。其中:
表 1: 信任建立方式
此外,需要注意:
当前,受益于 solidity 图灵完备智能合约,欺诈证明和有效性证明技术广泛用于以太坊 Layer2 扩容。但是,在比特币范式下,受限于比特币有限的操作码功能、1000 个 stack 元素等限制,这些技术应用仍处于探索阶段。本文针对比特币 Layer2 扩容场景下,总结了比特币范式下的限制和突围技术,研究有效性证明和欺诈证明技术,并梳理了比特币范式下所独有的脚本切分技术。
比特币范式下有诸多限制,但是能够使用各种巧妙方法或技术来突破这些限制。例如,比特承诺可突破 UTXO 无状态限制、taproot 可突破脚本空间限制、connector output 可突破 UTXO 花费方式限制、契约可突破预签限制。
比特币采用 UTXO 模型,每个 UTXO 都锁定在 locking 脚本中,该脚本定义了花费该 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 种实现方式:
目前,BitVM2 库中,基于 Blake3 的哈希函数实现了 Winternitz 签名。单个 bit 对应的签名长度约为 26 字节。由此可知,通过 bit commitment 来引入状态,成本是昂贵的。因此,在 BitVM2 工程实现中,首先对消息进行哈希运算获得 256bit 的哈希值,然后再对哈希值进行 bit commitment,从而节约开销,而不是直接对原始较长的消息的每个 bit 进行承诺。
自 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 结合使用,可通过约束各子函数输入输出之间的一致性,约束整个计算的完整性和正确性。
比特币目前提供的单个 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 可花费或超期后任何人可花费。
目前比特币脚本主要限制了解锁的条件,而没有限制该 UTXO 如何进一步被花费。其原因在于比特币脚本无法读取交易自身的内容,即无法实现交易自省。如果比特币脚本能够检查交易的任何内容(包括 output),就可实现契约功能。
当前的契约实现方式可分为两类:
有效性证明与欺诈证明均可用于比特币 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 中所示,多轮欺诈证明适于希望降低链上仲裁计算量,和(或)无法一步定位出问题计算片段的场景。多轮欺诈证明,顾名思义,证明者和验证者之间,需要多轮交互以定位出问题计算片段,然后再基于所定位出的计算片段进行仲裁。
Robin Linus 早期的 BitVM 白皮书(通常称为 BitVM1),使用的多轮欺诈证明。假设每轮挑战期为一周,采用二分查找法定位问题计算片段,则对 Groth16 Verifier 的链上挑战响应周期将高达 30 周,时效性极差。尽管当前有团队在研究比二分法更高效的 n-ary 查找法,但相比于一轮欺诈证明中的 2 周周期,其时效性仍低很多。
目前,比特币范式下的多轮欺诈证明均采用许可式挑战,而一轮欺诈证明实现了无需许可式挑战方式,降低了参与方串谋风险,从而安全性更高。为此,Robin Linus 充分利用了 taproot 的优势,对 BitVM1 进行优化。不仅将交互轮次降低至 1 轮,还将挑战方式扩展为无需许可式,但是其代价是增加了链上仲裁计算量。
在证明者和验证者之间仅通过一次交互,即可完成验证欺诈证明。该模型中,验证者仅需发起一次挑战,证明者只需做一次响应。在该响应中证明者需提供一个证据,声称其计算是正确的。如果验证者能够从该证据中找出不一致性,则挑战成功,否则挑战失败。一轮交互欺诈证明的特点如表 3 所示。
图 3: 一轮欺诈证明
Robin Linus 2024 年 8 月 15 日发布了 BitVM2: Bridging Bitcoin to Second Layers 技术白皮书中,采用类似图 3 的方式,以一轮欺诈证明方式,实现了 BitVM2 跨链桥。
OP_CAT 是比特币最初发布时脚本语言的一部分,因安全漏洞问题在 2010 年被禁用。但是,数年来,比特币社区一直在讨论将其激活。目前 OP_CAT 已被分配编号 347 且已在比特币 signet 上启用。
OP_CAT 主要功能是将堆栈中的两个元素结合起来,并将合并后的结果推回堆栈。这个功能特性,开启了比特币上的契约和 STARK Verifier:
尽管经 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 技术。
当进行脚本切分时,需平衡如下维度信息:
当前,脚本的切分方式主要分为以下 3 大类:
例如,Groth16 verifier 经过多轮优化,其 script size 由约 7GB 降低至约 1.26GB。除做这种总体计算优化外,还可对各个 chunk 单独优化,以充分利用 stack 空间。如可通过引入更优的基于 lookup table 的算法,并对 lookup table 进行动态加载卸载,可进一步降低每个 chunk 的 script size。
web2 编程语言计算成本和运行环境,与比特币脚本成本和运行环境完全不同,所以对于各种算法的比特币脚本实现,仅翻译现有实现是行不通的。因此,需针对比特币场景,考虑以下优化:
本文首先介绍了比特币脚本限制,并介绍使用比特币承诺突破 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
【免责声明】市场有风险,投资需谨慎。本文不构成投资建议,用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资,责任自负。