从 Lamport 签名中获得脚本状态

作者：Andrew Poelstra

来源：<https://blog.blockstream.com/script-state-from-lamport-signatures/>

过去的半年时间里，我们看到了多项旨在提升比特币脚本（Bitcoin Script）的提议：CAT、64 位运算，以及其它更古老的想法（例如 CTV）、更面向未来的想法（如 Chialisp 和 Simplicity）。这些活动在很大程度上掩盖了一些近期发生的、我们对现有比特币脚本的理解的革命性的变化；这些变化构成了 BitVM 的基础，但也可能会变成其它同样让人兴奋的升级的基础。

本文尝试总结和分类其他人对比特币脚本的研究。我无意声称对这里所描述的东西有原创性的发现。

比特币脚本

如许多研究者注意到的，Bitcoin Script 是嵌在比特币区块链系统中的一种简单的编程语言，我们用它来编程移动一笔资金所需满足的条件。迄今为止，Script 最常见的用法是使用一个公钥来检查一个签名。虽然比特币的地址格式在过去几年中经历了许多变化，但每一种地址都将脚本的这种用法当成首要用法并予以支持：公钥可以直接编码到比特币地址中，然后钱包软件会知道如何将这个公钥展开成完整的、用来检查该公钥的签名的程序。

但 Script 可以做到更多事情：它可以检查哈希值的原像、可以检查相对的和绝对的时间锁，还可以作一些简单的推理、从而以多种方式组合这些检查。这就是 Miniscript 编程语言背后的假设：我们可以将 “把公钥展开成一个脚本” 的想法普遍化，从而 “将任意大的签名条件组合展开成一个脚本”。

从技术上来说，Script 可以做的甚至比这还要多：它可以加减 32 比特长的数字，它可以求数据的哈希值并检查哈希值相等，它还可以重新安排和操作一个 “堆栈” 的数值，方式灵活多样。但是，Script 有许多局限性：它没有操作码来运行简单的算术（比如乘法），它（几乎）不能分析超过 32 比特的对象并且（几乎）不能内省交易本身的数据。后者就是支持 “限制条款（covenant）” 可能需要软分叉的原因，而前者就是直到今天 Script 都没有被用来计算任何 “有趣” 函数的原因。

举个例子，在 Script 中，要将两个 16 比特的数字相乘，即只使用 Script 提供的加法和减法操作码，你需要将它们先打散成比特（通过要求在见证数据中提供比特，然后复制、相加，以重建原本的数字），然后以加法的形式来实现乘法。最终，你的代码将需要数十行操作码来实现一次乘法。

在 Taproot 升级以前，Script 还有一个人为的限制，每个程序最多只能使用 201 个操作码，而一次乘法会占用这个额度超过 1/4，所以你根本做不了什么事情。在 Taproot 升级之后，这个 201 个操作码的限制已经移除了，但每一个操作码都依然会占用一个见证字节，这意味着，对于普通的钱包来说，要想在区块链上放置几千字节的程序，代价会高不可攀。

而且，没有交易内省的话，我们也不清楚要用这样大体积的计算来做什么。

毕竟，即使你能对任意数值作任意计算，但这些数值跟区块链上的交易数据没有关系，那这些计算如何能为比特币带来有用的语法？

Lamport 签名

“Lamport 签名” 是 Leslie Lamport 在 1979 年发明的 —— 虽然如果没有现代的密码学哈希函数，它是不安全的，而现代密码学哈希函数到 1990 年代才出现 —— 也是少数几种从那个时代存留到今天的密码学物件。它的经久不衰的热度来自它的简洁性，而它对抗量子计算机的能力仅仅基于充分随机的哈希函数（不像更晚出也更高效的抗量子签名方案提议）。

但是，Lamport 签名有两个重大缺点：（1）它是极为低效的，公钥和签名都需要几 kB 的数据；（2）它是一次性的。用户只要使用同一个公钥签名多于一条消息，第三方就可以伪造更多消息，从而让所有签名都变得毫无价值。这是可以优化的，比如说，让你的 “公钥” 变成一棵由几百万个一次性公钥组成的 “默克尔树” ，但已经越过了实用性的边界。

这些局限性，让 Lamport 签名在量子计算突破的时候，可以作为比特币的一种 “备用签名方案”。但也使它无法在任何广泛部署的系统中作为主要的签名方案。

它的工作方式也非常简单：假设被签名的消息是 256 比特长的（可通过先运行 SHA256 哈希函数来保证任意长度的待签名消息都会被 “转化” 为 256 比特长）。用户的公钥就由 256 对哈希值组成（总共是 512 个哈希值）。要签名一条消息的时候，用户就揭开每一对哈希值中的其中一个哈希值的原像，至于要揭晓哪一个，就看消息的对应比特位的数值。

签名的验证者需要重新哈希消息和原像来检查签名与比特位相对应。

在 2021 年，Jeremy Rubin 发布了一篇文章，声称 Bitcoin Script 可以直接验证对 33 位数值的 Lamport 签名。他的机制是非常清晰的。Bitcoin Script 没有操作码可以直接读取一个数字的每一个比特，也没有能够从比特中构造数字的比特位（bitwise）操作。但 Script 有一个操作码可以将两个数字相加，而通过让只有一个比特集（bit set）的不同数字相加，我们就可以按位构造（bitwise-construct）以及按位解构（bitwise-deconstruct）一个数字。

凭借这一洞见，Rubin 以如下方法检查了一个编码成一系列哈希原像的 Lamport 签名：

1. 对每一个原像，计算其哈希值，并将其哈希值与一对嵌入 Script 的目标数值相比较（这些目标值就构成了公钥）。
2. 如果哈希值与成对目标值的第一个数值相等，那就返回比特 0；这时候脚本不会做任何事。
3. 如果哈希值与成对目标值的第二个数值相等，那就返回比特 1；这时候，在累加器上加 2 的特定次幂。
4. （要是对不上任何一个数值，那么这个签名就是无效的，脚本会终止。）

累加器最终的数值将等于被签名的数字，后者是通过通过累加相应于其比特展开形式的每一个比特的 2 的幂数来获得的。

这已经足够有趣了：它意味着，对于特定类型的 “断言机签名” 应用来说，你可以直接在 Bitcoin Script 中检查签名，假定你的断言机愿意对特定事件制作一次性的 Lamport 签名，而且人们可以提前知道你的断言机对每一个事件的 Lamport 公钥的话。举个例子，一场球赛的结果，可以编码成 1 个比特。而比分则可以用几个比特来编码。一个具体的时间戳可能需要编码成 33 比特，等等。当然，只需检查多个 Lamport 签名，你就可以签名任意数量的比特。

但如果不能签名大体积的消息，你就不能获得对交易数据的签名，因此无法制作限制条款。（真的吗？）

BitVM 与模棱两可

Jeremy Rubin 的文章在当时被很多人认为是稀奇的东西，然后就被淹没在围绕他所提出的 OP_CTV 提议和限制条款的更大范围的讨论中。在 2023 年 12 月，该文在 Ethan Heilman 和 Armin Sabouri 所撰写的 OP_CAT BIP 中被间接引用，让它在对 Bitcoin Script 有不同看法的人群中获得了新的受众。

人们之所以会产生不一样的看法，是因为在 2023 年 10 月，也就是两个月以前，Robin Linux 在邮件组里宣布了他的项目 “BitVM” —— 这是一个通过将程序分切成多笔交易、从而在 Bitcoin Script 中实现任意计算的大胆项目。单笔交易只作一个简单的操作，而一个操作的输出会通过 哈希值-原像-揭晓 的构造挂钩到另一个操作的输入中，这看起来跟 Lamport 签名极为相似。

这里的技巧是，如果一个用户使用同一个公钥签出了对多条消息的 Lamport 签名，结果将是同一对哈希值的两个原像都暴露。这在 Script 中是很容易检查出来的，这就可以用来构造一种 “罚没交易”，将资金从这样做的用户手中拿走。只要一个用户使用相同的 Lamport 公钥公开签名了两条消息，这样的罚没交易将是完全有效的。罚没交易可以用在多交易的协议内部，以惩罚行为不轨的用户，一般是没收他们必须提前缴纳的保证金。

所以，这些 Lamport 签名，不是在被复用时单纯地失去安全性，而是可以被配置成主动惩罚多次签名的用户。这对于断言机签名场景有明显的用途：签名者被假设会见证真实世界中的事件的一个结果；我们希望遏制这样的签名者声称（比如说）两个队都赢了比赛。但还不止于此。

在密码学文献中，我们管一个参与者为一个理应独一无二的数揭晓两个数值的情形叫 “模棱两可（equivocation）”。我们可以认为，罚没交易是一种对抗模棱两可的措施，因为它惩罚任何使用同一个公钥对同一条消息签出多个签名的签名人。

那么，有了抗模棱两可构造的 Lamport 签名，就有了将公钥映射成具体的、不可篡改的数值的效果。换句话来说，我们有了一个全局的 “键-值”对存储，是可以通过 Script 来访问的，而且它还有一个神奇的特性，这个全局表中的每一个条目都可以由一个具体的人（知道该公钥的原像的人）来设定，但永远只能设定一次。这个键值对存储对任何比特币交易（实际上，是对任何区块链上的交易）来说都是可以访问的，无论它是否连接到另一笔交易。

这个键值对存储有 2^256 个条目，其中的大部分都是不能访问的，因为没人知道这些键背后的原像，所以，虽然它是一个由每一种使用这种 Lamport 签名构造的程序共享的 “全局键值对存储”，但它不会被填满，也没有来自一个程序的数据意外破坏来自另一个程序的数据的风险，也没有理应由某一个用户设置的数值被另一个用户设定的风险。这个键值对存储也并不完整地存储在任何地方。

BitVM 及其变种利用这个事实，将一个操作的输出跟下一个操作的输入捆绑起来：给定的一个程序可以分割成一长串的基本操作，比如 RISC-V 指令集中的操作码，而每一个这样的基本操作都可以用一个自包含（self-contained）的 Script 程序实现出来，它会在键值对存储中搜索操作的输入和输出，检查它们是否已被正确联系起来，如果没有，就以某种方法惩罚用户。

完整的 BitVM 要比我们这里说的复杂得多：对每一个程序，它要从键值对存储中划出一个可寻址的内存空间；每一个操作都需要从内存空间中搜索其输入和输出；每一个操作都需要跟踪一个程序计数器，以及输入和输出以外的状态；而且整个系统要使用交互式的协议以及待确认交易的树捆绑在一起，以保证罚没交易可以正确地强制执行；而且，在一个步数高达数十亿的程序中，只需一步走错，就可被瞄准并遭到惩罚。但这篇文章并不是关于 BitVM 的，我们不会再展开。

插句话：小脚本和大脚本

我们要花一分钟来帮读者回顾：Script 只能对 32 位长（以及更小）的数值作不简单的计算。这样的数值是 “scriptnums”，而 Script 由多个操作码可以操作它们，可以将它们解释成有符号的整数，或是布尔值，有时候两者皆可。

使用 BitVM 或一种类型的机制，将 Script 程序分割在多笔交易中，你可以在小体积的脚本中做任意计算，从 “零知识证据” 的验证，到 PoW 检查，再到数分解，都可以。

而大于 32 比特的数值，则只能被少数用途狭窄的操作码操作：可以哈希它们；可以将它们解释成公钥或签名，以检查一个交易签名；可以计算它们的字节长度；也可以作为不透明的数据在堆栈中移动。对它们来说，可以做到的唯一 “真正” 通用的计算是检查相等，它本身的价值微不足道。

我们将 32 比特数值的世界称作 “小脚本”，它富有表达计算的能力，只是不能以任何方式访问交易数据。而更大的数值的世界可以称作 “大脚本”，可以通过 CHECKSIG（检查签名）操作码来访问交易数据。也可以在大脚本世界中检查哈希原像，这正是实现 Lamport 签名的关键，但这几乎就是你能在大脚本中做的全部了。

没有办法有效地沟通这两个世界：你可以哈希一个小数值来获得一个大数值，但你无法从这个大数值中知道你原来不知道的任何东西。没错，你可以用 SIZE 操作来知晓一个大数值的长度，但如果这个数值代表着一个哈希值、公钥或签名，那它的长度是固定的，所以你无法知晓任何新东西。（虽然在 Taproot 之前，签名的长度是可变的，所以你有可能从一个恰当约束的、传入 CHECKSIG 的交易中抽取中交易信息。）

所有这些都是为了提醒读者，虽然这个新的 Script 功能令人兴奋，它提供了大量计算表达能力，但它没有内省交易数据的能力，因此无法用在 “保险柜（vaults）” 或其他限制条款应用中。

CAT 操作码提供了一种沟通两种脚本的机制，这就是为什么 CAT 自身就足以提供限制条款功能。这也是为什么 Script 在许多方面 “只差一步” 就支持限制条款，以及为什么像 CAT 这样看起来不相关的提议能够启用限制条款：非常多的操作码可以取小数值为输入、输出大输出，或者反过来；它们可以将从大脚本世界中获得的交易数据输送到小脚本世界的通用程序中。甚至 SHA1 操作码的一个非常糟糕的中断，也可能被用作这样的桥梁，因为这样你就可以通过将大数值解释成 SHA1 哈希值、寻找它的小数值原像，在大数值上作 “计算”。

插句话：虫洞

实际上，假设你有足够多的运算力，你可以在小脚本中获得限制条款。通过跳出 Script “之外”，用户可以（在脚本中）验证比特币区块链，以及包含这段脚本的交易（需要避免直接编码其自身的数据，以避免体积无限膨胀，但这可以通过间接的方式来做到来；下一节会提供更多的细节），然后，就可以将限制施加在这一内部验证自身的 “视角” 上，从而对这样的交易施加额外的约束。

这个想法可以创建出一些有限的限制条款功能，但要记住，对键值对存储的正确访问是分割大型计算的前提，但它并不是直接执行的。相反，需要一些额外的机制来保证对不正确访问的惩罚。这会让保险柜这类限制条款的实现变得复杂很多，因为其功能依赖于特定的花费模式变得不可行（而不是仅仅受到抑制）。

三子棋

到目前为止，我们已经谈到了 Lamport 签名的反模棱两可特性，以及这种特性如何在 Bitcoin Script 中实现一种 “全局的键值对存储”，这种键值对存储又如何在脚本程序间传递数据、从而将大型计算分割成许多独立的部分。但 Lamport 签名还有另一个有趣、可能是优越的方面：它们可以在脚本中承诺一个唯一的数值，而不让这个数值影响它所在的交易的 TXID。

这有两个后果：一，我们可以在交易中承诺数据，而不影响 TXID；意味着，我们可以改变一个 Script 程序内部的参数而不会让待确认交易的链条失效；二，我们可以承诺数据，而不影响签名哈希；意味着，用户可以在不知道全部交易数据的时候 “预签名” 一笔交易。

（顺带说一句，只要有一种检查可以惩罚签名多个数值的行为，那么任何签名方案都具备这种属性。Lamport 签名有趣的地方在于我们在今天的比特币上就能使用它。）

这种在一个 Script 程序中放置数据，而不影响包含该程序的交易的 TXID 的能力，为一个能够引用自身代码的程序的构造打开了大门（举个例子，通过在程序中注入其自身的 TXID，而 TXID 是所有交易数据 —— 包括该程序 —— 的哈希值）。这个叫作 “自复制程序（Quine）”，可以用来启用委托（delegation）以及创建递归型限制条款。这种能力正是 Simplicity 语言的 “disconnect 组合器” 背后的动机。不过，因为我们只能在小脚本中验证 Lamport 签名，这就排除了 TXID 这么大的对象，似乎在这个方向上目前我们还没什么可以做。不过，没有什么能阻止我们用相似的技巧来模仿非递归的限制条款。

我们来介绍一个由 supertestnet 在 Github 上发表的案例。

三子棋游戏是一种两个人在一个井字格上玩的回合制游戏。规则很简单：玩家不能在已经落子的方格上落子；只要能让自己的子连成一条直线（不论是直线还是斜线），就赢。假设一些玩家想在链上玩这个游戏，一笔交易就代表一个回合。

当然，与这些交易并行的，是他们会签名一笔 “握手言欢” 交易：双方都签名，把资金直接交给胜出的一方；所以，如果双方都同意游戏的结果，他们就不需要发布表示每一回合的交易！但构造完整游戏的副本依然重要，因为这样一来，在发生争议的时候，区块链才能居中调解。

要模拟这个游戏，他们可以采取的一种办法是一连串的预签名交易，每一笔交易都要求来自双方的签名。先手玩家的第一步有 9 种可能；那么后手玩家需要签名全部 9 笔交易，然后先手玩家选择代表自己要走的那一步的交易来签名。然后，在后手玩家的第一步，有 8 种可能的落子位置；所以先手玩家也要签名所有 8 笔交易，让后手玩家来选择自己想要的。以此类推。

可以证明，这种办法不太能行 —— 因为任何一个玩家都有可能拒绝签名某一步棋，在游戏卡住的情况下，没有办法归责，因此落败的玩家也就没有激励完成游戏。为了防止这种情形，每一个玩家都必须在游戏开始之前签名对手可能的所有走棋。这样一来，一个玩家就只能拒绝签名他自己的走棋，而这可以容易用带有时间锁的没收条件，来迫使他们行动。

另一种方法是让每一个玩家都签名对手的走棋，而他们可以招募一个受信任的第三方来预先签名每一步棋。但结果是完全一样的：每一种可能的交易链条都必须得到签名。对三子棋游戏来说，总共有 255168 种对局可能，需要总计 549946 笔预先签名的交易。这就突破了实用性的边界，而且显然，这样的策略无法推广到更复杂的游戏上。举个例子，对国际象棋来说，这样的可能性以 “香农数” 为界，这可是 10^120 。

我们面临这么大的膨胀，是因为我们要通过不同的交易来区分每一步棋，而每一笔交易都必须在游戏开始之前设置好。

不过，使用 Lamport 签名，我们就可以做得更好：

• 每一局三子棋都（最多只）有 9 步；
• 每一步都让棋局从一个状态转变为另一个状态；而棋局的状态小到可以用 Lamport 签名；
• 每一次状态转换所要遵守的规则，都足够简单，可以用 Script 来编码。

因此，我们可以用另一种方法来实现这种游戏：每一个玩家，都生成一个 Lamport 公钥，用来签名自己的每一步之后的棋局状态（所以先手玩家需要 5 个 Lamport 公钥；后手玩家需要 4 个）。然后，他们生成一连串的 9 笔交易，交易输出的 taptree 有三个分支：

1. 一个 “常规走棋” 分支，由以下条件满足：

   • 来自双方的常规签名
   • 来自相应玩家对上一个棋局状态的 Lamport 签名
   • 来自另一个玩家，对下一个状态的 Lamport 签名
   • 一个用 Script 实现的检查：两个状态是正确关联的（两个状态的区别在于，理当行动的玩家只走了一步合法的棋）。

2. 一个 “赢棋” 分支，由以下条件满足：

   • 来自双方的常规签名
   • 来自相应玩家对上一个棋局状态的 Lamport 签名
   • 一个用 Script 实现的检查：本玩家已经赢得比赛。

3. 一个 “超时” 分支，由以下条件满足：

   • 来自双方的常规签名
   • 一个相对时间锁已经过期。

最后一笔交易的 “常规走棋” 分支要换成一个 “平局” 分支，因为如果格子都已被填满但还没有胜者，就说明打平了，锁定的资金要原路返回。

和面前一样，每一个玩家都要预先签名所有的交易，在这里是 27 笔，包括 “胜出条件” 交易（将所有的资金发给胜出的玩家）、“超时条件” 交易（将所有的资金发给没有超时的玩家），以及 “平局条件”。

这样一来，即使国际象棋的规则会复杂很多，棋盘状态可能需要多个 32 比特的数值来表示，而且步数显然多于 9 步，采用相同的构造也是完全有可能的。

交易树

在上一个例子中，我们充分利用了一个事实：三子棋的规则可以嵌入 Script，意味着玩家签名一个无效的棋局状态是没有用的。（即使他们签名了无效的走棋，表示这一步棋的交易也将是无效的，而且表示所有未来走棋的交易可能会作废，因为它们都依赖于它。）所以，所有的攻击者能够做到的仅仅是泄露被攻击者的一部分 Lamport 签名密钥，从而让其他玩家可以伪造被攻击者的走棋。

我们也利用了一个事实：我们的整个协议并不长，最多只有 9 步。这意味着，如果一个玩家拒绝完成游戏，或者完成游戏但不承认结果，那么将完整的游戏副本发送到链上（以追索资金），是合理的。对许多游戏来说，这已经足够了。

这个模型还有许多技巧，但已经超出了本文的范围：作为证明者和验证者之间的 “游戏”、检查单方的计算；外包一个甚至两个角色；使用较大的 taptree 将多个步骤合并到一笔交易中；将线性的副本换成对无效步骤的二进制搜索，等等。这些技巧构成了 BitVM、BitVM 2、BitVMX 等等的基础。

使用这样的技巧，我们可以减少现有的依赖于未签名交易树的协议的开销。Bentov 和 Miller 在 2017 年出版的一篇古老论文声称在 UTXO 模型上实现富状态协议将总是面临指数级的膨胀（相对于在账户模型（例如以太坊）上实现类似协议）。使用 Lamport 签名作为一个全局的键值对存储，我们可以部分反驳这篇论文。但这又超出了本文的范围，需要在我们的下一篇文章中展开！

致谢

感谢 Robin Linux 和 Ethan Hilman 审核本文的草稿。

注：本文的一个较早的版本首次发表在 Bitcoin Magazine 上。