作者：ajtowns

来源：https://delvingbitcoin.org/t/btc-lisp-as-an-alternative-to-script/682

这是我关于 Chia Lisp 的文章（中文译本）的续篇。它依然使用层层递进的模式，因此，跟上一篇文章一样，如果本文不能点燃你的兴趣，不妨记住有这样一篇文章；待日后你发现我们做出有意思的东西之后，再回来读这篇有用的背景材料。

背景

过去几年中，我一直在研究是否有某种形式的 Lisp 可以替代 Script，主要成果是我称为 “btclisp.py” 的凌乱 python 代码。它主要是我的学习工具，背后的想法是让它帮我搞清楚一些问题，比如：

• 如果你有 Lisp 作为一种交易编程语言，你能实现什么类型的特性？

• 理论上可行的想法，在现实中尝试会成功还是失败？

• 实现/维护/升级 一种 Lisp 解释器难不难？

• 用 Lisp 来写代码会不会很麻烦？

交代我的背景，你可能会更理解我：虽然我熟悉函数式编程（曾经涉猎 haskell、hope、coq、lean4），我以前从未尝试过 Lisp（甚至连 emacs lisp 也没有）。我的灵感的主要来源是 Daniel Holden 的 Build Your Own Lisp ，以及我已经提到的，Chia Lisp 。

范围

我的想法非常简单：如果我们制作一种 Lisp 语言来作为 BIP 342 tapscript 的一种嵌入式替代，会有什么效果？也就是说，引入一种新的 tapleaf 版本，从而在使用该版本的时候，taproot 脚本会被解码成一种 Lisp 表达式，而剩余的交易见证数据会被填充成 “环境”，然后用 Lisp 表达式求值；如果求值失败，交易就是无效的，反之则是有效的。

别的一些东西则不在我考虑范围内：

• 改变 UTXO 数据库 —— Chia 的 “coin 集合” 模式在数据库中包含的信息与比特币的 “UTXO 集” 模式的不同，前者允许一些巧妙的结构。在此我们不考虑这些，因为这需要改变 UTXO 数据库，比起添加一种新的 tapleaf 版本，是大得多的变更。
• 让脚本交互 —— Chia 的模式的多种特性让脚本可以交互：条件语句允许一个脚本要求其它脚本在同一区块中创建出来或者花费一笔资金；花费绑定让来自不同 coin 的脚本可以被组合以及复制；签名聚合允许签名被聚合；而 transactions_generator_ref_list 特性甚至让你可以从更早的区块中拉取历史脚本，从而你可以便宜地复用来自其它脚本的代码和数据。所有这些也都不在我考虑范围内。
• 改变交易被处理为程序的一个结果的方式 —— Chia 的脚本通常只是验证过程的第一步：例如，在 Chia 中，你无法知道一笔交易会在区块中占据多少 “空间”，除非你真的用脚本求值，因为开销的计算是脚本求职的一个副作用，而脚本求值的结果是一组条件，也要被该区块满足的条件。我的工作的目标不是为了实现这个，所以脚本的运行依然只会产生两个布尔值结果，即 “有效” 和 “无效”，而任何其它信息（例如 重量/开销、时间锁、与其它交易的相对关系）依然应该在脚本求值之前就得到。

上述陈述不是想说这些想法必然都是坏的，只是说：我认为它们超出了我的目标范围。也就是说，我只是想探索使用 Lisp 作为一种 tapscript 替代的可能性，没准备讨论更复杂的变更。

总结

你可能已经猜到了，我最终重复了得出 Chia Lisp 的大部分设计抉择，所以我这里只谈有差异的地方。你看，方便之处现在就体现出来了 —— 已经有一篇讨论 Chia Lisp 的帖子（即前文所述本文的前篇，中文译本）了，真方便呀 ：）

带有星号标记的参数只能是 atom 。 这里总计有 45 种操作码，虽然不是所有操作码都已经在 btclisp.py 中实现，而且一部分实现还是不正确的 —— 毕竟只是个学习工具嘛：读者也需要自己练习！

补充细节如下：

引用

实际上，我要先指出一件事：我的表达式解析器允许将 (q . x) 缩写为 'x 。不是什么大事，但确实更容易写，所以在下文中我也会使用这样的缩写。

环境树

Chia 风格的环境结构是非常整洁的，但如果你将环境构造成一棵二叉树（而不是一个列表）会更好 —— 如果使用列表，则元素会逐个放在位置 2、5、11、23、47、95 等等上，每一个后续的位置都是前一个位置的两倍加一，即 $p_{n+1} = 2p_n + 1$，实质上，每多一个元素，存储的长度就会长一倍。但如果是用一棵较小的二叉树来做，需要的存储位置最多只有 $2n$ 个（好吧，实际上是 $2^{log_2(2n)}$），所以，6 个元素可以编码在 8、12、10、14、5、7 这几个位置上。这有多大作用是可以出辩论的，但是，在有些时候，将一个索引序列化为大数字，会比序列化为较小的数字更低效，所以，这种优化在有些时候可能是有用的。

无论如何，我为 a 操作码的 ENV… 参数实现了这种动作，并且通过 b 操作码：在两种情况下，如果你给这些操作码提供 4 个参数，它们会将列表转化为一棵平衡的、由 cons 组成的树，从 (a b c d) 变成 ((a . b) . (c . d))。如果实现了 sf 操作码，也会应用相同的动作。

椭圆曲线密码学计算

secp256k1_muladd 操作允许在一定程度上手动运行椭圆曲线密码学操作，尤其是它允许 a*P + b*Q = c*R 这样的断言（a, b, c 都是标量，而 P, Q, R 都是 secp256k1 曲线上的点）。这个操作的编码有一些技巧：

• 如果一个参数是一个 atom，它会被当成表示生成元的一个标量乘法因子，即 a*G
• 如果一个参数是一个 cons，其开头项会被当成一个标量，而结尾项会被当成点，即 h*T；这个点既可以是常规的 33 字节的点，也可以是一个 32 字节的 x-only 点
• 如果 cons 的开头项是 nil，则其代表的标量会被当成 -1
• 如果 cons 的结尾项是 nil，则其代表的点会被当成 -G
• 它不把其中一个参数当成是等式另一边的单独项，而是求值 a*P + b*Q + c*R = 0（0 是位于无穷远处的点）
• 标量被处理为大端序的数字（跟 BIP 340 的处理一致），而别的地方都处理为小端序

因此，BIP 340 验证等式（s*G = R + h*P）可以表达成 (secp256k1_muladd (s . nil) (1 . R) (h . P)) 。这让我们可以直接编写 bip340_verify，差不多是这样：

(a '(secp256k1_muladd 
       (c '1 4) 
       (c (sha256 5 4 7 (bip342_txmsg)) 7)
       (c 6 nil)
     )
    (substr 3 0 '32)
    (substr 3 '32 '64)
    (a '(cat 1 1) (sha256 '"BIP0340/challenge"))
    2
)`

假设初始的环境是 (key . sig) 。

我认为，这也是一个很好的例子，表明，借助由足够通用的操作码构成的足够强大的编程语言所提供开发模块，你就可以实验新功能，比如说获得 BIP 340 的功能，而无需先用 C++ 实现其逻辑并让它合并到 Bitcoin Core 中。

（还比如说，可以手动实现 BIP 340 Schnorr 签名验证，意味着你可以选择微调构造、作出不同于 BIP 340 的设计选择，比如允许签名不承诺自身的签名密钥。）

交易内省

几乎所有有趣的新功能都要求一些基于交易本身的逻辑 —— 如果你希望实验 SIGHASH_ANYPREVOUT 或者 OP_CSV 这样的想法、又不想要先实现 C++ 代码，那么你需要一些工具来拉取关于正在被验证的交易的信息。这就是 tx 操作码的用意。这是非常直接的：你给它一个参数的列表，从而告诉它你想要关于交易的哪些信息，然后它给你返回所需的信息。（例外是，如果你只想要一段信息，它就不会封装成一个列表，以节省你对 h 的调用。）

当前受支持的信息比特是：

这里的想法是，如果你仅指定一些数字，例如 (tx 5 13 20) 你将得到当前输入的对应数据，或者跟当前输入具有相同索引号的输出的对应数据；如果你想要了解另一个 输入/输出，你需要使用一个 cons 对，来指定数字以及你感兴趣的 输入/输出，例如：(tx (10 . 0) (20 . 0))。

请注意，对于其它输入，只有脚本签名和 annex 是可以获得的，不能获得完整的见证数据堆栈；这里的想法有两重：第一，其它输入的见证堆栈可能会依赖于未来的软分叉，而且不是你可以分析出意义的东西；第二，我们可以合理地致力于保证 annex 紧凑，从而分析其它输入的 annex 是一个较快而且便宜的操作，而它们的见证数据可能较大，导致分析缓慢且昂贵。

目前还没有定义将数据放入 annex 的格式，因此无法提供从 annex 中拉取数据片段的功能。可能最好的做法是使用一种 annex 操作码。

bit342_txmsg 给你提供了拉取需要被签名的交易的信息的方法（根据 BIP342 的要求）。你可以直接实现 txmsg，但更为复杂：

(a '(a '(sha256 4 4 '0x00 6 3) 
       (sha256 '\"TapSighash\") 
       (cat '0x00 (tx '0) (tx '1)
            (sha256 (a 1 1 '(cat (tx (c '11 1)) (tx (c '12 1))) '0 (tx '2) 'nil))
            (sha256 (a 1 1 '(tx (c '15 1)) '0 (tx '2) 'nil))
            (sha256 (a 1 1 '(a '(cat (strlen 1) 1) (tx '(16 . 0))) '0 (tx '2) 'nil))
            (sha256 (a 1 1 '(tx (c '10 1)) '0 (tx '2) 'nil))
            (sha256 (a 1 1 '(cat (tx (c '20 1)) (a '(cat (strlen 1) 1) (tx (c '21 1)))) '0 (tx '3) 'nil))
            (i (tx '14) '0x03 '0x01)
            (substr (cat (tx '4) '0x00000000) 'nil '4)
            (i (tx '14) (sha256 (a '(cat (strlen 1) 1) (tx '14))) 'nil)
       )
       (cat (tx '6) '0x00 '0xffffffff)
    ) 
   '(a (i 14 '(a 8 8 12 (+ 10 '1) (- 14 '1) (cat 3 (a 12 10))) '3))
)

上述代码假设了 SIGHASH_DEFAULT 已足以满足需要、 OP_CODESEPERATOR 还未被使用、scriptPubKey 的长度小于 253（已避免执行合适的 CompactSize 编码）。

数字

现在已经出现了关于在 Script 中启用 64 位算术的讨论，并且其中的大部分顾虑在这里也适用：如果我们希望能够处理聪的数值，脚本当前的 32 位 CScriptNum 就不够用。我采用了简单的方法，相当于说：“数学操作码会将自己的输入视作 64 位的无符号小端序数字，有必要时可以截断”。我的猜测是，使用变长的小端序数字，然后将最高位的比特作为一个信号位（匹配 CScriptNum 的动作）可能是更合理的方法。

加入一个 strrev 功能将允许更容易将正数封装成其大端序表现形式，从而可以用作 secp256k1_muladd 中的标量，这可能会有用。

序列化

虽然 Chias 的序列化形式简单到令人佩服，我还是认为，为用途而优化可能是更好的。我认为，以下事物可能会频繁出现，也许值得尽可能降低它们的开销：

• nil
• 小数字（用于操作码和环境索引，例如从 0x01 到 0x2f）
• 小体积 atom（最长可达 64 字节的字符串；这样就包括了 BIP 340 签名）
• 小列表（例如，拥有 1 到 5 个元素以及终止的列表）
• 以 nil 终止的列表（即，标记列表是规整或不规整的，是否要暗含一个 nil 中字符）
• 被引用的元素

所以，我选择以下编码：

使用这种编码，上述验证一个 Schnorr 签名和计算 BIP 342 sighash 的代码可以序列化为：

7f0001f82a7705810477057924050407752c0777050600780f0300a0780f03a0b4407701f71001017624c4424950303334302f6368616c6c656e676502（61 字节）

和

7701f901ff00240404b40006037624bd546170536967686173687f0610b400762b80762b8176247f01010101f710762b77058b01762b77058c0180762b828076247f01010101f62b77058f0180762b828076247f01010101f701f710760e0101762bf51080762b828076247f01010101f62b77058a0180762b828076247f01010101f710762b770594017701f710760e0101762b7705950180762b83807803762b8e8381780f7710762b84b70000000080847803762b8e76247701f710760e0101762b8e807810762b86b400b7fffffffff60178030eff010108080c77170a8177180e8177100377010c0a83（236 字节）

显然，更好的是使用一个内置的一字节操作码（在可用的时候），但如果没有一个操作码恰好可以做到你想做的事、而唯一的替代又在等待共识变更得到开发、支持、合并、部署和激活，那么花费跟一个 2-of-3 多签名大体相当就似乎非常好了。如果你不尝试匹配一种现有的规范的化，那么，通过设计你自己哈希值来使用给定操作码易于表达的东西，也可以节约更多字节 —— 例如，通过 (tx ...) 直接拉取你想要的数据，然后使用 (wr (tx ...)) 来序列化它，然后取其哈希值 (sha256 (wr (tx ...)))，这些东西应该既容易又便宜、且不会损失任何表达力和安全性。

开销

上文假设了，在分析一个脚本的开销的时候，见证数据的体积（以字节计）是重要的考虑因素。这在当前是真的，但对任何允许循环的语言都不是真的：有了实现迭代（或者说递归）的能力，写下来只需少量字节的程序，可能需要花费大量的时间和内存才能结束。

我认为，需要担心的是三种基础的东西：

• 程序自身的体积 —— 必须在区块链上揭晓，因此会占用一定的带宽和存储空间
• 运行程序所需的 时间量/计算量 —— 一个区块中的所有程序都应该在几秒内完成；所以，任何程序单体所占用的时间，都应该跟它所使用的区块重量成比例
• 运行程序所需的 内存量 —— 当前，Script 程序被限制为在堆栈中操作大约 500 kB 的数据（包括替代堆栈），可以可以扩大一些，但维持一个较小的固定限制，可能是明智的做法

我的结论是一个可以监控这些限制的一个粗略框架（ALLOCATOR.limit 设定了一个全局分配限制来跟踪被使用的内存；而 ALLOCATOR.effort_limit 名义上跟踪总的计算资源，假设了在计算完成的时候会调用 ALLOCATOR.record_work(x)），但还没有在实际上以有意义的方式设定多种功能的开销。真的，我发现我们需要用 C++ 语言切实地实现所有操作码，然后运行基准测试，以测量符合实际的开销，然后回过头来为区块设定总体的开销限制。

注意，度量当前的内存用量隐含地定义了一种 “共识偏好的” 求值程序的办法：急迫求值 或 懒惰求值（eager vs lazy elvaluation）、尾部调用消除（tail call elimination）、以及求值的顺序，不同程序在不同方法下会产生不同的内存用量，而且，因为超过内存用量限制会让一笔交易称为无效交易，一致而且准确地度量它们在这种编程模式的共识中是极为关键的。者并不意味着无法实现优化，只是说，开销/用量限制 的检查成了求值的一个额外的结果，而且不能被任何优化改变。

中间状态

Liquid/Elements 在不久之前加入的一个有趣的东西是 “流式哈希操作码”：

我们加入了 “流式哈希” 操作码，以允许向一个哈希引擎喂入数据、无需将它们都放进一个栈层中。这清楚地规避了 520 字节的栈大小限制，而且不需要脚本解释器使用更多资源。

这套操作码有： OP_SHA256INITIALIZE （取一个字符串，产生一个中间状态）、OP_SHA256UPDATE（取一个中间状态和字符串，产生一个中间状态）和 OP_SHA256FINALIZE（取一个中间状态和字符串，产生最终状态）。所以，你不需要这样 A B C CAT CAT SHA256，只需要 A SHA256INIT B SHA256UPDATE C SHA256FINALIZE。

这样做的直接后果是，你可以从一连串的小段数据中产生一个哈希值，而不需要先将它们合并在一起。但在这里并不神奇，因为我们可以直接提供相同的小串数据，作为 (sha256 ...) 操作码的参数，然后得到相同的结果。

迄今为止看起来一切都好，但当你考虑要让底层的脚本编程语言更加强大的时候，值得考虑它到底改变了什么。所以，实质上有两个重大区别：

• 对哈希函数的输入数值进行交错计算并调用更新
• 复用来自不同哈希函数的输入

先举一个第一方面的例子。假设（作为一种编程联系）你想要计算前 2000 个斐波那契数的拼接的 SHA256 哈希值。使用 Chia 的模式，也即拥有一种多参数的 SHA256 操作码和急迫求值模式，这将要求你先计算出前 2000 个斐波那契数，然后对它们运行 SHA256 运算；这本身需要大概 174 kB 的内存来存储所有这些数字的二进制表示，而不是每计算出一个就喂进哈希函数、算出下一个数就抛掉前一个数。

解决这个问题的一种方法是懒惰求值：你构造出一个程序，生成一个包含了前 2000 个斐波那契数的列表 (sha256 1 1 2 3 5 ...)，然后对它调用一个 a。因为求值是惰性发生的，所以直到 sha256 操作码真的需要下一个参数之前，什么都不会计算，而且自动编写这个程序的最简单的方法也成了相对高效的办法。

然而，第二方面的挑战却不能借助解释器来解决 —— 找出什么时候需要交错计算也许可以自动化，但作为一种共识特性却显然过于复杂了。

一种也许通用的、让这种特性成为可能的方法是，加入一种 “部分应用” 操作码，从而编写 (partial sha256 abc) 会返回一种特殊的 “函数” 对象，封装了哈希 a b c 的中间状态而不定型。然后，这个对象可以传递给 a 操作码，以终结运算，或者可以传递给另一个 (partial ...) 调用，从而继续运算。

虽然这样的动作有点过于模糊，无法为这些 设计/实现 工作辩护，我认为，一种 (partial ...) 构造的另一个优势是，它将允许带有大量参数的操作在运行时更加高效地求值，即使解释器是以急迫求值而非懒惰求值形式实现的。

（据我所知，Simpliciy 稍微延伸了由 Liquid 采用的方法，加入了 6 种 jet，分别支持 SHA256 和 SHA3）

补完

不管怎么说，上面还有一个问题：“用它来编写代码是不是很烦？”答案是：“非常烦人”。

开发一种懒惰求值解释器，这样我可以只编写 (i C nil (x)) 来检查 C 是真值，而不需要写成 (a (i C (q q nil) (q x)))，这让事情可以简单一些，但即使如此，管理环境依然非常困难、确保所有引用都正确也非常困难（在治理我能直接说 nil 吗？它需要一个 q 还是两个，还是几个？我需要使用 c 来构造一个列表而不是直接引用它吗？）。

好消息是，加入一个补完阶段，你就可以编写带有命名的函数以及带有命名的参数，非常好地解决了这个问题。（而且，如果你真的这样做，你可以同时重写 if，从而将它作为一种懒惰求值程序，即使底层的操作码是被一个急迫求值解释器求值的。）

我把一些东西拼凑在一起，好让部分例子更容易说清楚，但我认为，我做过的大部分事情都需要抛在脑后、从头开始，所以我不准备详细说明。不过，我猜想其中一个方面也许值得保留：将一些符号（操作码的名称、函数的名称、函数参数的名称）跟 atom 区别开来，可能会好得多 —— 这样一来，如果 foo 没有定义成一种符号，(foo) 就会被当成一种报错，而不是被扩展成三字节的字符串 "foo"（就像在 Chia 中发生的那样）。（也许值得探索的一个事情是使用一种真正的 Lisp，比如 racket，来编写编编译器，也就是将它当作从一种 DSL（域专用语言）翻译成另一种。）

结论

回到我最初的问题：

• 如果你有 Lisp 作为一种交易编程语言，你能实现什么类型的特性？

• 理论上可行的想法，在现实中尝试会成功还是失败？

• 实现/维护/升级 一种 Lisp 解释器难不难？

• 用 Lisp 来写代码会不会很麻烦？

我的回答差不多是：

• 链上开销可能会有点昂贵，但似乎你可以做几乎所有事情；至少，只要你不关心我假设的 “范围” 约束，比如不改变 UTXO 集的 存储/查询 方式。
• 只有两件事情让我担心实践可能与理论不符：第一件是，部分程序似乎比我真正满意的情形要慢，但我认为，大部分应归咎于它们是在一个实验性的 python 求值引擎中运行的；另一件是，我既喜欢 Chia 的单操作码 SHA256 方法，也喜欢 Liquid 的显式 SHA256 中间状态处理的灵活性，而两者是有冲突的。
• 我不认为实现一种 Lisp 解释器以及一组与之适应的操作码是很难的事。
• 如果没有能够将高级表示翻译成共识层操作码的编译器，编写 Lisp 代码是非常烦人的，但这似乎是可以解决的。

未来的工作

我认为，这项工作在以下方面还可以进一步推进：

1. 优化 btclisp.py 样品代码
   • 修复 bug，实现尚未实现的操作码，梳理清楚
   • 加入一种 partial 操作码（然后切换回急迫求值？）
   • 重写 “编译器”，让编程更容易
2. 找出是否有一些有趣的合约可以用这种更强大的编程语言来编写，以及它在实践中会是什么样子，基于 btclisp.py 样品代码
3. 实现一种这样的编程语言，然后部署在 signet/inquisition 上，要求：
   • 目的是使其最终在主网或者一种联盟化的侧链上可用
   • 作为一种允许开发者构造和测试新的智能合约、无需编写 C++ 代码及部署额外共识升级的办法，目的是设计受限制的原语来直至类似合约的部署（例如，在 signet 上测试用 lisp 实现的保险柜合约的动作，然后选出好的、设计出支持同样动作的 OP_VAULT 操作码，然后部署到主网上）

（完）