BitVM:通过电路抽象解锁比特币上的任意计算 - ZKSECURITY

本文深入探讨了BitVM及其变体如何通过在比特币的UTXO模型上构建电路抽象,实现对比特币上任意计算的验证。通过模拟 covenant、利用一次性签名实现状态性,以及结合时间锁等技术,BitVM 在不修改比特币核心协议的前提下,扩展了其功能,并为高效验证复杂计算开辟了道路。

btc on the moon

长期以来,人们认为比特币在验证任意计算(包括验证零知识证明!)方面的能力有限。然而,BitVM 变体的最新发展表明,无需修改比特币的核心协议,就有可能在比特币上验证任意计算。

BitVM1 在一篇 eprint 论文 中进行了形式化,它引入了电路概念,从而能够在比特币上进行任意计算。它采用了一种乐观协议,其中计算可以在链下完成,并且当对计算存在争议时,可以在提议者和挑战者之间在链上解决。但是,它具有固定的验证者,这意味着只有预定义的各方可以挑战声明。

在这一概念的基础上,BitVM2 论文引入了一种桥协议,该协议允许跨链资产验证,例如在比特币和其他区块链之间以最小的信任转移资产。它通过 SNARK 验证器(编码在比特币脚本中)压缩和验证计算来推广该过程。

BitVMX 是 BitVM1 的另一种变体,但旨在降低复杂性,并成为 BitVM2 的高效替代方案。

在这篇文章中,我们将探讨比特币未花费交易输出(UTXO)编程模型的基础知识,并研究 BitVM1 中引入的构建块如何克服固有的局限性,从而实现任意计算。有了这个背景,我们希望这篇文章为更深入地理解类似的 BitVM 系统铺平道路。

理解比特币的 UTXO 模型

以太坊使用基于帐户的编程模型,其中交易更新帐户的全局状态。每个区块记录状态转换的影响,随后的交易进一步修改这些帐户状态。这与传统的编程模型非常吻合,在传统的编程模型中,程序会随着时间的推移维护和更新其状态。

相比之下,比特币的 UTXO(未花费交易输出)模型更具限制性。每笔比特币交易都会“花费”现有的 UTXO 并创建新的 UTXO。花费 UTXO 涉及执行锁定脚本(UTXO 的一部分)和相应的解锁脚本(交易见证数据)。这些脚本是无状态的:一旦花费了 UTXO,除了创建新的 UTXO 之外,全局状态就不会有任何更新。

一笔比特币交易包含以下内容:

  • 输入:要花费的 UTXO
  • 输出:新创建的 UTXO
  • 见证:解锁输入的数据

在花费 UTXO 时,交易中的见证数据必须满足其锁定脚本。此外,输入中 BTC 的总价值必须超过输出中的总价值,差额将作为交易费用。

以下动画演示了如何解锁由“需要签名”脚本锁定的 UTXO:

来源:https://learnmeabitcoin.com/

Bitcoin Script 是一种基于堆栈的语言。按照 FIFO(先进先出)的顺序,脚本执行操作码并将结果推送到堆栈上。如果堆栈上仅剩余的元素为值 1,则认为执行有效;否则,它将被视为无效。

执行过程充当验证过程。只有当提供的见证成功通过锁定脚本的执行时,才能花费 UTXO。

从理论上讲,锁定脚本语言可以对任意程序进行编码。但是,它不支持循环等功能,也不提供对外部存储器的访问。此外,脚本的最大大小受到 4 MB 区块大小限制的约束。这些限制使得大型、复杂的脚本不切实际。

在比特币上构建电路抽象

一个很自然的问题是:我们如何在规避限制的同时仍然启用复杂的程序逻辑?

一种方法是将较大的程序划分为多个 UTXO,每个 UTXO 编码一小部分指令(通常称为“电路小工具”)。然后,交易充当连接这些小工具的“导线”。执行整个程序涉及一系列交易,这些交易共同实现所需的逻辑。

考虑一个由以下执行组成的程序:

f1(v1) = v2
f2(v2) = v3
f3(v3) = v4

通过将其分解为较小的锁定脚本,我们可以形成一个电路,该电路可以实现与整个程序相同的状态转换。此方法规避了脚本大小限制。

下图说明了这个概念:

alt text

  • 在左侧,如果提供了正确的参数 v1v2,则可以解锁具有 f1 锁定脚本的 UTXO。它表示程序执行的部分验证,其作用类似于电路中的门或小工具。
  • 交易可以通过提供满足锁定脚本的见证来解锁多个 UTXO,从而同时验证 f1(v1)=v2f2(v2)=v3,并为下一个状态转换创建新的 UTXO。这类似于电路中小工具之间的接线。
  • 在右侧,UTXO 可以通过不同的路径花费,例如由 f3(v3)=v4 或时间锁脚本 TL 解锁。这类似于电路中的分支。

但是,我们不能直接使用比特币脚本在比特币 UTXO 模型之上实现这种电路抽象。这是由于两个主要问题:

  • 锁定脚本是独立的。虽然锁定脚本可以强制状态转换为正确(例如 f1(z1) = v2),但我们无法强制花费它的交易创建一个新的 UTXO 来强制电路的继续(例如,生成的 UTXO 中的 f3 锁定脚本,强制电路继续其评估而不是直接解锁资金)。

  • 锁定脚本是无状态的。即使我们可以强制执行某个“线路”,另一个问题是状态包含在见证(或解锁脚本)中,因此无法在 UTXO 之间“传递”。本质上,比特币脚本是无状态的,不允许在它们之间传递数据。例如,我们无法强制 f1 产生的见证 v2 与 f2 使用的见证 v2 相同,因为 f1 和 f2 位于不同的锁定脚本/UTXO 中。另一个例子是,无法强制解锁 f3 的见证使用在前面交易中见证的同一 v3。

接下来,让我们看看 BitVM 系列的工作如何应对这些挑战。

克服 UTXO 限制:导线和信号约束

这些挑战可以通过结合两个关键构建块来解决:模拟盟约和通过一次性签名实现有状态性。

使用多重签名设置模拟盟约

盟约是比特币的一个概念,它限制了 UTXO 的花费方式。它们类似于电路中的导线,决定了信号如何在小工具之间流动。

锁定脚本定义了解锁 UTXO 所需的要求(见证)。但是,它并不知道使用 UTXO 的整个交易结构。为了确保在后续交易中的正确放置和交互,我们需要一种限制 UTXO 重复使用的方式。这种限制是通过盟约实现的。

在撰写本文时,比特币尚未支持原生盟约功能。比特币社区正在努力支持 原生盟约功能。其中之一是 OP_CHECKTEMPLATEVERIFYCTV)操作码。这些操作码使 UTXO 的锁定脚本能够验证交易模板,但它们需要进行硬分叉。其他创新方法包括 StarkWare 的 ColliderScriptUn-FE’d Covenants 等。

BitVM 论文 提出了一种使用多重签名来约束 UTXO 的未来花费规则的模拟盟约解决方案,方法是预先签署交易。在这篇文章中,我们将解释模拟盟约的概念。

多重签名如何工作

具有多重签名的锁定脚本允许仅当预定义数量的参与者同意时才能花费 UTXO,这通常称为阈值。与仅需要一个签名的典型交易不同,该脚本可以指定需要来自一组公钥的多少个签名。所需的确切签名数量由 OP_1OP_2 等操作码指定,整体验证由 OP_CHECKMULTISIG 执行。

多重签名要求通常表示为“M-of-N”,这意味着需要来自总共 N 个提供的公钥的 M 个签名才能授权花费。例如,“1-of-2”多重签名设置需要来自两个指定公钥中任何一个的签名:

OP_1                      # 至少需要 1 个签名 (M=1)
<PUBKEY_A> <PUBKEY_B>     # 两个可能的公钥
OP_2                      # 公钥的总数 (N=2)
OP_CHECKMULTISIG          # 检查是否至少有一个签名与提供的密钥匹配

另一方面,“N-of-N”多重签名(例如 2-of-2 或 3-of-3)需要来自所有指定公钥的签名,以确保所有参与者之间达成共识。

由于多重签名要求直接在锁定脚本中指定,因此它们可以构成花费条件的更复杂逻辑的一部分。

使用 Sighash 锁定交易模板

sighash 类型定义了签名应绑定的交易结构。通过指定 sighash 类型,签名者可以将他们的签名绑定到特定的交易元素,例如输入和输出的安排。

常见的 sighash 类型 SIGHASH_ALL 会在交易的任何部分被更改时使签名无效。当与多重签名结合使用时,签名可以共同强制执行对交易模板的协议。因此,参与者不能在不使签名无效的情况下修改约定的模板。

通过对这些交易可以产生的 UTXO 强制执行要求,可以为可能因花费原始 UTXO 而产生的整个交易子树强制执行路径。

使用多重签名模拟盟约

盟约允许我们通过编码希望花费该 UTXO 的交易必须如何操作来塑造 UTXO 采取的轨迹。以锁定脚本 f1 为例。通过使用多重签名条件扩展脚本 f1(v1)=v2,参与者可以确保交易严格遵守约定的模板。此设置利用多重签名来绑定交易结构并对 UTXO 强制执行类似盟约的限制:

  • 甲方提供一个部分签名 s1_a,将交易专门绑定到具有锁定脚本 f1 的输入 UTXO 和具有锁定脚本 f3 的输出 UTXO。

  • 乙方也提供另一个部分签名 s1_b,绑定相同的交易结构。

  • 两个签名组合起来形成一个预先签署的交易模板,以确保 UTXO 流中的一致性。

通过以递归方式应用此方法,可以类似地控制每个新创建的 UTXO(例如那些具有锁定脚本 f3 的 UTXO),从而创建预先签署的交易模板的链或图。此链接机制可确保交易严格遵守约定的条件,从而有效地在 UTXO 模型上形成“用户电路”的骨架。

alt text

请注意,这些预先签署的交易只有在提供额外的参数(例如交易的 v1v2)时才会完整,我们将使用这些参数来填充骨架。这些参数代表电路信号。这种有状态的方面将在后续章节中详细介绍。

使用一次性签名强制执行静态单赋值

在盟约到位后,可以通过提供可变见证(例如锁定脚本 f1v1v2)以及预填充的多重签名来按顺序在链上发布预先签署的交易。

问题在于锁定脚本是无状态的。它无法约束不同 UTXO 中参数(例如 v1v2)的一致性:

alt text

例如,如果不强制执行锁定脚本参数的不可变性,则可以在不同的锁定脚本中为参数 v2 分配两个不同的值。这不能保证由 f1f2 锁定脚本表示的状态转换,因为它可能会为 v2 编造不同的值,从而仅通过锁定脚本的执行。

为了强制变量的不可变性,BitVM 系列的工作结合了使用一次性签名和削减协议。这个技巧最初是在 2021 年 这里 提出的。一次性签名是一种只能使用一次的签名方案。虽然这非常有限,但它们的特殊之处在于,如果它们被使用两次来签署不同的值,则可以很容易地检测到。 因此,我们可以为我们拥有的每个变量创建一个一次性公钥,并在我们为变量分配的值上使用其关联的一次性签名。

事实上,这种方法非常类似于编译器设计中使用的静态单赋值 SSA 模型。通过强制每个变量的单次赋值,系统可以实现可预测和可验证的状态转换。

来源:https://en.wikipedia.org/wiki/Static_single-assignment_form

Lamport 签名如何工作

在深入探讨它如何在我们的电路模型中实现有状态性的细节之前,让我们回顾一下 Lamport 签名方案。

下表说明了 Lamport 签名的公钥、私钥和要签名的 1 位 之间的关系。

公钥是一对哈希值 H(x)H(y)

要签名消息,请根据其对应的位值 01 显示签名(私钥)xy

要验证,可以使用函数 H 对签名进行哈希处理,以检查它是否与公钥中的相应哈希值匹配。

类似地,对于 n 位 消息,将有 n 对私钥。假设它是用于 256 位消息,则应有 256 对:

使用 Lamport 签名模拟有状态性

设置 Lamport 签名的方式取决于协议。Lamport 签名的设置阶段涉及准备公钥和私钥。在 UTXO 模型之上的电路模型中,这些私钥应该只为生成变量公钥的参与者所知。为了简化这篇文章,我们假设该协议基于提议者-挑战者模型,其中提议者设置 Lamport 签名并提交变量值,而挑战者则被激励去检测和证明含糊不清之处。

alt text

在上图中,绿色参数(例如 v1v2)表示用于解锁 f1 的有状态变量是元组。每个元组都包含 (val, sig),表示变量值和签名(私钥)——对变量值的承诺。通过应用于 Lamport 签名方案,锁定脚本可以针对为变量硬编码的公钥验证承诺:

现在到了使用一次性签名(如 Lamport 签名)进行承诺强制以模拟有状态性的最关键部分:含糊不清。如果没有检测和惩罚含糊不清的方法,就没有强制提议者提交正确的变量值的方法。

证明含糊不清的想法相对简单。只要挑战者发现提议者对变量值含糊不清,至少必须显示该变量值的一对完整签名。挑战者可以发布含糊不清的交易,其中包含变量的一对完整签名(例如 (x1,y1)),以证明提议者对变量值含糊不清:

至于如何惩罚含糊不清,则取决于实际的协议。据推测,盟约还应包括一组预先签署的交易,这些交易可用于证明电路模型中每个变量的含糊不清。

时间锁作为脚本内分支

某些协议(例如乐观协议)在很大程度上依赖参与者之间的互动来推进其状态。在每个互动轮次中,参与者应迅速做出回应。为防止参与者停止或停滞协议,时间锁脚本可以通过充当备用消费路径来强制执行严格的响应截止日期:

OP_IF
    <默认消费条件(例如,多重签名)>
OP_ELSE
    <未来时间戳或区块高度> OP_CHECKLOCKTIMEVERIFY OP_DROP
    <备用消费条件(例如,来自另一方的签名)>
OP_ENDIF

在此示例中,如果未满足默认消费条件,则另一方的参与者可以在时间锁期限后消费 UTXO。这种脚本内分支可确保即使一个参与者无响应,协议也可以推进。

预先签署的交易之间的额外脚本分支

虽然脚本内分支处理单个锁定脚本中的条件逻辑,但额外脚本分支会在花费 UTXO 后使交易图中某些路径无效。用于额外脚本分支的一种常见模式是 连接器输出,这是 BitVM 桥接论文 中描述的一种技术。

在计算电路中,状态遵循导致不同结果的条件分支。类似地,连接器输出允许一个预先签署的交易完全消费一个 UTXO,从而自动使备用预先签署的交易无效。这确保了交易路径中的相互排斥性,从而反映了电路逻辑中发现的条件分支。

使用 Taproot 压缩大型脚本

由于区块大小的限制,比特币脚本具有固有的尺寸限制,从而限制了可以直接嵌入到单个 UTXO 中的逻辑的复杂性。Taproot 可以通过使多个脚本压缩成单个紧凑的 Taproot 输出来解决此限制。

原始 BitVM1 论文 说明了允许将电路门表示为承诺的想法,因为它将多个消费条件(脚本)编码到紧凑的 Merkle 树结构中。每个电路门表示为一个单独的消费条件(Tapleaf),经过哈希处理并作为 Merkle 树中的叶子包含在内。此 Merkle 树的根哈希提交到 Taproot 输出中。

这允许将复杂的交易逻辑,甚至整个计算电路,封装在单个 UTXO 中。Taproot 不是显式嵌入大量的锁定脚本,而是将这些脚本聚合到脚本承诺中,仅在消费时根据需要显示每个脚本。它对于实现更灵活的额外脚本分支特别有用,其中 Taproot 允许连接器输出来携带更多的脚本内分支。

用户电路编译和执行

利用前面描述的构建块,我们可以有效地在 UTXO 模型上“编译”和“执行”用户定义的计算电路。此方法的核心组件包括:

  • 盟约:确保对表示用户电路的交易图达成协议。

  • 一次性签名:强制执行变量的单次赋值,类似于编译器设计中的静态单赋值 (SSA) 概念。

  • 脚本内和额外脚本分支:模拟执行复杂电路设计所必需的复杂条件逻辑。

通过组合这些元素,可以将用户定义的计算电路系统地编译为基于 UTXO 的表示形式并以确定性的方式执行。

以下是用于提议者-挑战者模型的工作流示例:

  1. 编码变量:提议者为电路中的每个变量生成唯一的公钥-私钥对。这些变量的公钥直接硬编码到锁定脚本中,从而有效地将电路变量编码到 UTXO 中。

  2. 预先签署交易(提议者):提议者创建带有这些编码变量的原始交易,并预先使用多重签名对其进行签名以进行盟约。

  3. 预先签署交易(挑战者):挑战者审查并预先签署交易以进行盟约,验证公钥是否在不同的 UTXO 中一致地准确编码变量。在此阶段,用户电路在 UTXO 模型上编译。

  4. 执行电路:为了推进电路的状态,提议者发布包含对变量值的承诺的交易。这些承诺使用先前商定的预先签署的多重签名交易解锁相应的 UTXO,从而执行电路并向前推进其状态。

用于卸载计算的协议概述

通过前面章节中描述的构建块,我们现在准备好解决优化问题。很容易看出,直接将一个大型程序建模为一个电路并将整个电路发布在链上将太慢且在经济上不可行。

有几种方法可以解决此问题。BitVM1 提出了一个乐观协议,该协议激励对链上数据做出诚实的承诺,并通过平分博弈来惩罚含糊不清,以定位错误。另一方面,BitVM2 也提出了一个乐观协议,但通过使用 SNARK 压缩程序来更有效地实现。

为了了解如何使上述电路模型可行,以下是乐观协议的概述,该协议使用平分博弈来保持链上占用空间较小,同时确保提出的计算正确:

alt text

  1. 有两方:提议者和挑战者。
  2. 双方都预先签署盟约。
  3. 提议者发布一个交易,其中包含对锁定脚本 f 的输入 v1 和输出 z 的承诺,表示整个程序的执行。
  4. 新创建的 UTXO 可以由挑战者通过争议交易消费,也可以由提议者在时间锁期限后消费。
  5. 如果发生争议,参与者会在固定轮数内轮流通过平分博弈相互响应,以定位错误。
  6. 找到错误后,挑战者可以发布含糊不清的交易以消费 UTXO,其中包含来自提议者的存款,作为惩罚。
  7. 在争议期内,如果另一方在时间锁期限后未能响应,则任何一方都可以消费 UTXO。

在以后的文章中,我们可能会更详细地探讨这些乐观协议,以揭示它们如何利用电路模型。

结论

通过在比特币的 UTXO 编程范例上分层一个电路模型(通过模拟盟约、有状态性和分支等构建块)——可以将用户电路建模到 UTXO 电路中。为了使这种方法实用,BitVM 论文中提出的乐观协议可以通过保持链上占用空间最小来提高链上效率。总之,这些技术不仅在不改变其核心协议的情况下扩展了比特币的功能,而且还为有效验证任意计算铺平了道路。

  • 原文链接: blog.zksecurity.xyz/post...
  • 登链社区 AI 助手,为大家转译优秀英文文章,如有翻译不通的地方,还请包涵~
点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
zksecurity
zksecurity
Security audits, development, and research for ZKP, FHE, and MPC applications, and more generally advanced cryptography.