The road to universal computing on Bitcoin: Conceiving STARK to expand Bitcoin

撰文：StarkWare

Compile:Starknet 中文Community

1. Introduction

本文，我们将讨论在比特币上实现通用计算的任务及其涉及的各个步骤。事实上，实现在比特币脚本上计算任意逻辑的能力是一个吸引人的目标，因为其将比特币带入了非托管应用和去中心化金融的领域。

之前，由于两个严重的限制 — 比特币脚本长度和操作码的表达能力，比特币上的通用计算几乎被认为是不可能的。前者禁止了除短脚本之外的任何交易，后者限制了脚本操作码能够计算的内容。这两个限制共同构成了比特币计算可行性的严峻局面，因为许多应用无法在这些限制条件下实现。

不过，近年来，这种状况已经有了明显改善。事实上，随着 2021 年 Taproot 的升级，脚本长度的限制取消了，使得比特币脚本可以显著加长（事实上，Taproot 脚本甚至允许有时只对脚本的一部分进行链上支付，但我们不会在本文探讨这一特性）。此外，为了解决操作码表达能力的限制，我们发现一个简单的操作码就足以有效地实现无限的表达能力。

上述操作码被称为 OP_CAT，自 2012 年起就在比特币脚本中被禁用。这是一个非常简单的操作码，允许在堆栈上连接元素，只需要 13 行代码，就可以通过软分叉在比特币上进行非侵入性激活。从这个看似不起眼的操作码中衍生出如此大的能量是非常不容易的，因此，本文的核心目标就是详细阐述这一点。

下文，我们将深入探讨比特币上的计算过程，从其实现方式以及存在的限制开始。

接下来，我们将概述两种工具 — Covenantand STARK 证明，并证明如果二者能在比特币脚本中运行，将能够实现比特币上的通用计算。此外，我们将在本文中论证，得益于 STARK 证明，这种计算还能被赋予更多有用的属性：

• Scalability— 链上交易处理和计算变得可行，手续费极低。

• 表达能力— 逻辑可以用不同的、比比特币脚本更强大的编程语言进行编程。这对比特币编程的人性化和Safety性至关重要。

• On-chainSafetysex— 不管是什么样的计算，比特币脚本都只验证委托计算的数学证明。

• flexibility— 比特币上的计算可以存储全局状态，从而实现大量应用。

最后，我们将讨论 OP_CAT，及其如何实现上述工具。我们还将提到我们在这方面所做的一些努力，并讨论未来的发展方向。

注意：本文简化了一些技术性问题，以提供一个清晰的思维模型。当涉及实际实施所呈现的想法时，「细节决定成败」。

2. UTXO 模型和锁定脚本

本节，我们将简要概述比特币的 UTXO 模型，即每个 UTXO 都被锁定在一个锁定脚本后面。如果你对此很熟悉，可以跳到下一节内容。

了解比特币交易的第一步是注意到它们是根据未花费的交易输出（UTXO）模型进行安排和处理的，如图 1 所示。比特币交易可以有多个输入和输出，其中每个输出代表了可以由另一笔exchange花费的一定数量的比特币。相应地，一个交易的输入则代表了另一个比特币交易输出的支出。当然，我们要求输入中的比特币总量与输出中的比特币总量大致相等（差额为支付给矿工的费用）。

图 1：UTXO 模型中的交易。每个交易的输入和输出都与一定数量的比特币相关联，其中输出中的累计金额不能超过输入中的金额。未花费的交易输出（UTXO）以蓝色表示。

每个交易输出都被一个锁定脚本（scriptPubKey）锁定，该脚本将接受或拒绝它所给定的输入（scriptSig）（由所谓的花费者提供）。因此，如果想要从一个未花费的交易输出（UTXO）中转移资金，你必须能够生成正确的 scriptSig，并将此 UTXO 作为输入包含在你生成的交易中。

默认情况下，锁定脚本将简单地根据硬编码的公钥验证数字签名，这定义了被锁定比特币的所有权。更笼统地说，每当存在一个 UTXO 时，我们就可以说，能够提供正确 scriptSig 的人就是对应锁定脚本背后锁定的比特币的所有者。因此，每个比特币所有者的总余额由与该所有者相关的所有 UTXO累积决定（例如，由同一人进行数字签名的所有 UTXO）。

3. 比特币脚本的局限性

上一节概述了锁定脚本的一般情况，以及它们如何与比特币交易和比特币本身互动。本节，我们将重点介绍锁定脚本本身及其组成内容。

比特币上的锁定脚本是用一种类似于 Forth的基于堆栈的语言编写，这种语言被称为「比特币脚本」。由于比特币脚本没有循环，我们通过脚本所需的操作码数量来衡量脚本的成本，因为脚本的长度与其运行时间成正比。在图 2 中，我们可以看到一个简单程序的示意图，该程序将检查两个输入的和是否为 12。

图 2*：一个检查两个输入值之和是否为 12 的简单程序。程序的执行是通过将 scriptSig 与锁定脚本本身连接起来，然后从左到右处理操作码。scriptSig 只将元素推入堆栈。(a) 计算的第一步。(b)* 计算过程中。(c) 计算的最后一步（锁定脚本接受输入）。

我们必须指出，比特币脚本有很多局限性，这使得为它开发简单的逻辑变得非常困难，甚至根本不可能。这些局限性包括：

• 堆栈大小限制为最多 1000 个元素。

• 没有乘法操作码（事实上，即使是 31 字节整数乘法也需要用约 1.4 万个操作码来模拟）。

• for Pay2Taproot输出类型（Taproot 升级后）来说，单个交易中可容纳的操作码总数最多约为 400 万个，占满整个区块，而对于其他输出类型，操作码总数仅为 1 万个。

• 算术操作（加法、减法）仅限于 4 字节元素。

在最后一点提到的 4 字节限制尤其成问题。实际上，这意味着你无法修改长元素，例如，加密操作所需的 20 字节或更长的元素。

例如，将数据连接在一起并应用加密操作这种非常常见的操作是不可能完成的，除非忽略加密操作码，并将其模拟为对由 4 字节元素数组表示的数据进行的操作。后者的成本极高，因为单一的哈希操作可能需要数十万个操作码来模拟。

最后，我们要指出的是，由于比特币脚本的开发难度很大，代码自然更容易出现错误和漏洞。

4. 在比特币脚本中保存状态的挑战

虽然上一节已经证明比特币脚本还有很多不足之处，但我们认为，比特币锁定脚本的最大限制在于其只能读取花费者的输入。这意味着两个严重的限制：

• 比特币脚本不具备状态性。也就是说，它们不能读取 / 写入存储单元数据。类比以太坊虚拟机，没有类似于 SLOAD/SSTORE的操作码，而这是进行通用计算的一个基本功能。

• 比特币脚本无法强制规定比特币的花费方式（少数例外除外）。这可以通过 Covenant来解决，Covenant 赋予锁定脚本这种能力。（你可以想象这样一个简单的应用：链上金库，它通过限制允许花费的地址来运作。更通俗地说，Covenant 是一个功能极其强大的工具，具有广泛的应用范围。）

然后，我们将看到，通过构建 Covenant ，我们已经可以获得状态性。直观地说，这是因为你可以使用 Covenant 在交易数据本身中模拟存储的读取和写入。

事实上，以上所述还不足以概括比特币脚本及其复杂性的全部内容。但至少，我们可以肯定的是，编写比特币脚本并非易事。比特币脚本有非常严格的限制：

• 堆栈大小不得超过 1000 个元素的限制。

• 必须使用许多操作码来模拟乘法等简单操作。一般来说，你必须使用繁琐的比特币脚本语言编写逻辑。

• 必须以 4 字节形式编码的元素进行操作。特别是，你不能对加密操作码的输入进行操作和更改。

• 你的逻辑不能保存状态，必须适应单个交易。

• 一旦进行身份验证，你的逻辑不能控制比特币的花费方式。

此外，根据上述限制编写代码容易出现错误和漏洞。

虽然支付等非常简单的应用可以满足上述限制，但任何稍微复杂的应用都会遇到障碍。下文，我们将了解 Covenantand STARK 证明如何使我们打破这些局限性。此外，我们还将讨论 OP_CAT 如何帮助比特币脚本实现上述功能。

5. 通过 Covenant 实现比特币上的智能contract

本节，我们将了解比特币中的 Covenant 是如何保存逻辑状态的，并将更通俗地解释，比特币上的「intelligentcontract」是什么样的。这里的智能合约指的是某种有状态的逻辑，它包含一系列函数，可以根据预定义的规则调用这些函数，将状态转换为不同的有效状态。

更具体地说，比特币合约需要以下功能：

• 持久的逻辑和状态

• 控制逻辑 / 状态变化的能力

如前所述，上述功能可以通过 Covenant来实现。回想一下，默认情况下，锁定脚本只能读取直接输入的数据（scriptSig）。然而，通过 Covenant，锁定脚本可以读取花费者交易的所有数据字段,as well as锁定脚本所在的交易数据字段，甚至其他交易的数据。图 3 展示了使用 Covenant 时锁定脚本可以访问的不同部分。

图 3：锁定脚本（可视化为一个锁）可以访问的一些数据字段（红色箭头所示）。除了访问花费者交易的数据字段外，锁定脚本还可以访问锁定脚本所在的交易（tx1）的数据字段，以及由花费者交易同时花费的另一笔交易（tx2）的数据字段。

我们认为，上述描述的 Covenant 足以在比特币上构建通用智能合约。实际上，通用的方法是在交易数据本身中编码状态，并检查其向新值转换的有效性。为此，我们的交易将有两个输出：

• 第一个输出保存合约的逻辑（通过锁定脚本）以及合约中锁定的资金。

• 第二个输出保存智能合约的当前状态。这个 UTXO 的锁定脚本只保存状态，永远不会被花费（它锁定的比特币实际上为 0）。

锁定脚本逻辑将执行以下规则：

• 花费者的交易必须具有完全相同的形式（只有两个输出，并且所有资金都锁定在第一个输出中）；

• 第一个输出必须具有相同的锁定脚本逻辑;

• 第二个输出必须是有效状态;

• 提供给当前锁定脚本的输入必须使该锁定脚本相信从当前状态到新状态的转换是有效的（有效性由逻辑设计者定义）

图 4 是这种结构的示意图。正如 Weikeng Chen 所写的那样，已有许多人建议为这种结构起一个正式的名称，而「状态守车（state caboose）」作为一个候选名字脱颖而出。守车（caboos）指的是连接在货运列车尾部的铁路车厢，是指乘务员的专用车厢及其工作空间。

图 4：通过 Covenant 在比特币上实现的智能合约，遵循「状态守车」设计模式。锁定脚本确保花费者交易具有相同的形式和锁定脚本，并且具备有效的新状态 S’，其从上一个状态 S 的转换也是有效的。

举个简单的例子，你可以想象一个简单的计数智能合约。该合约的状态总是按花费者提供的值递增，这实际上调用了一个「累计」函数。这个计数智能合约如图 5 所示。

图 5：一个简单的智能合约，通过将输入（scriptSig）相加而将输入累加到其状态中。

最后要指出的是，为了「调用合约」并将合约转换到新的有效状态，用户需要为每次调用创建一个新的花费者交易。与以太坊智能合约不同，比特币智能合约本质上是按顺序的，要求交易同时承诺当前状态和新状态。在比特币上构建智能合约时，必须考虑到这种顺序属性。尽管也存在一些可能缓和该限制的方案，但本文将不对此展开讨论。

总的来说，我们了解到 Covenant 使比特币上实现了智能合约，理论上来说，当计算被分割到足够多的交易中时，可以在比特币上进行任意长度的计算。然而，仅仅使用 Covenant 仍然受到比特币脚本的大部分限制，即堆栈大小限制、操作码数量有限，以及一般情况下必须根据比特币脚本语言的约束进行编程。

下文，我们将探讨 STARK 证明系统如何通过减少比特币上计算的Blockchain占用以及允许使用完全不同的语言进行脚本编写，从而缓解上述限制。这种方法显著提高了编程效率和Safetysex.

6. 比特币 STARK 验证器

本节的目的是探讨如何在比特币上进行计算，同时把通过比特币脚本进行的实际计算量降至最低水平。我们的一般方法是通过计算委托，即将计算转移至链下进行（多个实体都有可能参与），只有验证步骤在链上的比特币脚本中进行。

这就引出了一个问题：我们如何确保链下计算是正确执行的？实际上，解决这个问题的一个很自然的候选方案就是证明系统。简单来说，证明系统允许 Alice（证明者）通过提供一个「证明」，来说服 Bob（验证者）某个语句的正确性，关键在于：

• 与没有证明者的帮助相比，验证者只需完成更少的工作就能验证这个语句。

• 此外，验证者得到了保护，即证明者无法欺骗验证者并使其相信一个错误的语句。

被证明的语句几乎可以是任何语句，从难题的解法，到更相关的计算委托例子。更具体地说，Alice 将向 Bob 证明 f(x)=y，而不需要 Bob 自己进行 f(x) 的计算，如图 6 所示。

图 6：计算委托的证明系统。证明者计算 y=f(x) ，并让验证者相信这个语句的正确性。关键点在于，如果 y≠f(x)，证明者则无法说服验证者相信这个事实。

因此，我们减少计算在Blockchain上的占用的方法将是在比特币脚本中实现一个证明系统的验证器。因此，为了调用智能合约，调用者将提供一个正确状态转换的证明，比特币智能合约将验证这个状态转换的证明的正确性，而不是直接检查状态转换（见图 7）。

此外，这种方法还有一个至关重要的好处，那就是比特币脚本的逻辑可以保持固定不变，而不受应用的影响，这就大大降低了出现错误的几率，并简化了审计工作。这源于一个简单的事实：同一个验证算法可以验证 y=f(x) 语句或 y=g(x) 语句，而无需事先知道要计算的函数。

图 7：通过 Covenant 在比特币上实现的智能合约，遵循图 4 中的「状态守车」设计模式，但增加了一个验证器。这一次，锁定脚本不再直接检查从 S 到 S’ 的转换是否有效，而是验证转换是否正确的证明。

虽然存在许多证明系统，但我们选择使用 STARK 证明系统（STARK），因为其具有许多吸引人的特点：

• 后量子Safety

• 无需可信设置

• 不增加比特币新的加密假设

• 扩展速度最快

• 经过实战检验，在超过一万亿美元的结算中得到信任

最后，与其他证明系统相比⬇️

STARK 对比特币友好，即其验证器组件更容易在比特币脚本中实现。从本质上讲，这是因为 STARK 主要基于哈希，与基于配对的证明相比，涉及的代数运算非常少。

在比特币脚本中代数运算的成本很高，这就解释了为什么 STARK 是比特币友好的。此外，Circle-STARK变体由于字段很小，对比特币尤其友好。

因此，由于比特币验证器可以相对容易地验证任何计算，我们可以选择验证哪种类型的计算。值得注意的是，这甚至可以是某种类型的 CPU 执行。此外，我们还可以在 CPU 的基础上设计高级编程语言。为此，我们在 StarkWare 开发了 Cairo，这是一种类 Rust、人性化且安全的编程语言，专为高效证明和验证而设计。在比特币上证明 Cairo 的执行可以带来很大的优势。

总的来说，通过使用 STARK 验证器以及 Covenant ，我们能够在比特币上实现通用计算。此外，这种计算还具有以下吸引人的附加特性：

• Scalability— 链上交易处理和计算变得可行，手续费极低。

• 表达能力— 逻辑可以用不同的、比比特币脚本更强大的编程语言进行编程。这对比特币编程的人性化和安全性至关重要。

• 链上安全性— 不管是什么样的计算，比特币脚本都只验证委托计算的数学证明。

• flexibility— 比特币上的计算可以存储全局状态，从而实现大量应用。

7. 使用 OP_CAT 进行连接以及其它功能

如上所述，OP_CAT 是一个简单的、目前已被禁用的操作码，其可以让比特币脚本连接堆栈上的元素。这个简单操作的重要性不可低估，因为它可以同时在比特币上实现 Covenantand STARK。具体操作如下：

• STARK— 实际上，这并不奇怪。这是因为，STARK 实际上只是将数据连接在一起，然后进行哈希计算，由于哈希计算是比特币脚本的原生计算，与代数运算不同，因此可以大大节省成本。STARK 中的主要哈希计算是 Merkle 路径验证（见图 8）和 Fiat-Shamir 变换。( 此外，Circle-STARK 变体的字段大小只有 31 字节，因此符合比特币Xiaobai Navigation脚本的 4 字节限制，使其成为一种比特币友好算法）。

• Covenant— 在 2021 年，Andrew Poelstra 提出了一个非同小可的观点，即 OP_CAT 可以通过所谓的 Schnorr 技巧在比特币上实现 Covenant，其中 Schnorr 的算法是 Pay2Taproot输出类型的数字签名（对于其他输出类型，可以使用 Robin Linus 观察到的类似的 ECDSA 技巧）。简而言之，要实现 Covenant，我们需要使用 OP_CHECKSIG，这是唯一能够将与花费者交易相关的数据放入堆栈的操作码。这样的操作过程并不简单，但通过一些操作，你可以访问所有必要的数据。

关于最后一点，在 Pay2Taproot输出中保存状态涉及一些技术难题。不过，可以使用其他输出类型来存储状态，如 Pay2WitnessScriptHash。这就产生了前面提到的图 4 和图 5 中的「状态守车」技术，交易中有两个输出。

图 8：*Merkle 路径验证，涉及哈希和字符串连接操作。Merkle 路径各部分（蓝色字符串）被连接起来，并进行相应的哈希处理。然后，与 Merkle 根进行相等性检查。OP_CAT操作被写成 ||。*

8. 现状与未来

在由 Weikeng Chen 和 Pinghzou Yuan 领导的开源项目中，我们正在共同努力建设 Bitcoin Wildlife Sanctuary。其中的两个主要项目包括：

• Circle-STARK 验证器，其工作演示可以验证比特币符号上一个简单语句（与斐波纳契数有关）的 STARK 证明。你可以通过此地址跟踪其进展。

• Covenant 框架，已经通过一个简单的计数 Covenant得以应用。验证器也使用了该框架。

通过这一努力，我们的目标是为比特币带来高效、安全、对开发者友好的 OP_CAT 智能合约。我们认为，这对比特币计算领域来说是一个充满希望且令人兴奋的前景。

9. 结语

总的来说，通过本文，我们了解到：

• Covenant是比特币脚本的一个强大工具，允许在比特币上创建智能合约。Covenant 扩展了比特币的功能，不仅仅是简单的价值转移。

• 然而，即使有了 Covenant ，比特币脚本仍有许多限制，包括堆栈大小的限制以及可使用的操作码类型的限制。这限制了仅使用 Covenant 就能实现的智能合约的复杂性和表达能力。

• STARK可以有效验证链下计算的执行情况，因此为缓解这些限制提供了一个很有前景的解决方案。通过利用 STARK，可以在比特币智能合约中执行更复杂的计算，并最小化其在链上的计算占用。

• Cairo是一种专为使用 STARK 进行高效证明和验证而设计的编程语言，非常适合用于比特币智能合约。它能够创建更复杂的智能合约，提升了人性化程度、功能性和安全性。

• OP_CAT是一种比特币脚本操作码，用于连接元素。OP_CAT 在比特币上实现 Covenant 和 STARK 方面起着至关重要的作用，进而为比特币带来了强大的通用计算能力。

下一篇文章，我们将深入探讨比特币上的 Circle-STARK 验证器。

感谢 Weikeng Chen、Pingzhou Yuan 以及 StarkWare 团队对本文提出的宝贵意见。

Victor Kolobov

The article comes from the Internet:The road to universal computing on Bitcoin: Conceiving STARK to expand Bitcoin

相关推荐: HTX Ventures 宣布赞助 LSDFI SUMMIT 活动：探讨 DeFi 核心，探索 LSDFI 未来

HTX Ventures是火币HTX的全球投资部门，整合投资、孵化和研究以识别全球最优秀和最有前景的团队。 7月8日，HTX Ventures宣布赞助在布鲁塞尔举行的ECC 的周边活动LSDFI Summit。该活动由Tenderize主办，于本周一（7月8日…