a16z：论「无状态区块链」的不可能性

原文作者：Miranda Christ、Joseph Bonneau

原文编译：深潮 TechFlow

随着区块链支持更多用户和更频繁的交易，验证者存储以验证交易的信息（即“状态”）的数量也在增加。例如，在比特币中，状态由一组未花费的交易输出（UTXO）组成。在以太坊中，状态由每个账户的账户余额以及每个智能合约的代码和存储组成。

随着账户或 UTXO 足够支持人口中相当一部分真正日常交易的区块链增长，这种存储负担将变得难以控制，使得成为验证者变得困难，并对去中心化构成威胁。诱人的解决方案是转向密码学，其中诸如 Merkle 树和零知识证明等工具帮助我们实现了以前难以想象的事情。

这正是“无状态区块链”的目标。但尽管对它们进行了大量研究，它们仍然远未实用。但事实证明，这种进展滞后是固有的 ——这些构建与实用性之间的差距将永远无法弥合。我们最近的工作表明，如果没有额外的措施来管理状态，任何无状态区块链方案，无论多么聪明，都是不可行的。然而，正如我们在本文末尾所展示的那样，这种不可能性结果不应该让人灰心。

无状态

如今，状态是庞大但可管理的。例如，比特币节点存储约 7 GB 的数据，以太坊节点存储约 650 GB 的数据。但是，完整节点的存储负担与链的吞吐量（每秒交易数或 TPS）大致呈线性增长，而当今的吞吐量仍然不可接受。根据当前的设计，真正支持日常交易所需的状态（每秒交易数为数万到数十万）将变得难以控制，需要使用千兆字节甚至拍字节的存储空间。

这促使人们寻找技术方法，以显著减少验证者所需的状态量。至关重要的是实现无状态区块链，这将要求验证者仅需存储恒定大小的状态，而不管交易吞吐量如何（实际上，这个术语是一个误称：仍然存在状态，只是足够小，以便在任何未来的吞吐量下都能实用——通常是恒定大小的）。这种轻量级存储要求将使得运行验证者节点变得更加容易；乐观地说，每个人都可以在他们的手机上运行一个节点。由于增加验证者的数量会增加链的安全性，降低验证者的准入门槛非常重要。

尽管对无状态区块链进行了大量研究（例如，由 Todd、Buterin、Boneh 等人和 Srinivasan 等人进行的研究），但它们距离实用还很远，据我们所知，没有一个被部署。所有已知的无状态区块链的根本问题是它们要求用户存储称为见见证的额外数据，以帮助验证者验证涉及其账户的交易。例如，这个见证可能是一个 Merkle 包含证明，显示用户的账户和余额包含在全局状态承诺中。当用户进行交易时，他们向验证者提交这个见证，以显示他们的账户具有足够的余额。

与存储私钥不同，它永远不需要更改，这些见证经常更改，即使对于不活跃交易的用户也是如此，给用户带来了不切实际的负担。类似地，想象一下，如果您不断监视全球所有其他信用卡交易并相应地更新一些本地数据以使用您自己的信用卡。为了使区块链实用，用户必须能够离线并仅在提交交易时与区块链交互。在许多情况下，例如硬件钱包，更新见证不仅仅是不方便，而且是不可能的。

这引导我们提出一个自然的研究问题：我们能否构建一个不需要频繁更新见证的无状态区块链（或者仅需要很少更新见证的区块链）？为了回答这个问题，我们开发了一个新颖的理论框架（可撤销的证明系统），它概括了无状态区块链。利用这个框架，我们证明了一个不可能性结果：简洁的全局状态和频繁的见证更新之间的权衡在本质上很难调和。我们的证明技术是信息论的，这意味着未来的计算机将没有足够的能力来解决这个问题：无状态区块链构建与实用性之间的差距将永远无法弥合。

我们研究的背景

为了帮助理解我们的不可能性结果，我们首先描述了一种自然但效率低下的使用 Merkle 树构建无状态区块链的方法。我们的目标是使验证者能够确定用户提交的交易是否有效 ——例如，用户是否具有足够的账户余额来进行交易。在无状态区块链方案中，验证者存储一个恒定大小的状态。当用户进行交易时，他们必须在交易中包含一个见证。验证者可以使用当前状态和用户提交的（交易，见证）对来验证该用户是否具有足够的账户余额来进行交易。

我们首先构建一个 Merkle 树，其中每个（账户 ID，余额）对（a，b）作为叶子节点包含在内。验证者存储的恒定大小的状态 V 是这棵树的根，它作为一组账户余额对的承诺。每个用户将其见证作为 Merkle 包含证明维护。一个叶子（a，b）的 Merkle 包含证明由沿着从该叶子到树根的路径的伙伴节点（v1，…，vk）组成。给定一个由账户 a 和声称的余额 b 进行的交易，验证者可以通过检查（a，b）的证明（v1，…，vk）与其当前状态 V 来验证 b 是否确实是账户 a 的余额。如果是这样，验证者执行交易并必须相应地更新账户的余额。Merkle 树的一个方便的属性是，给定一个叶子的 Merkle 包含证明，当该叶子发生变化时，计算结果的根很容易。换句话说，验证者可以轻松计算出一个更新的状态 V'，该状态捕捉了交易执行后账户 a 的新余额。

这个 Merkle 树方案有两个主要缺点。首先，用户的见证相对较大，随着系统中账户总数的对数增长。理想情况下，它们应该是恒定大小的，我们可以使用 RSA 累加器等方案实现这一点。

第二个缺点更难避免：每当其他用户进行交易时，账户余额对的证明就会发生变化。回想一下，叶子节点的证明由从该叶子节点到树根的路径上的合作伙伴节点组成。如果其他叶子节点发生变化，其中一个节点就会发生变化，从而带来实际上的问题。大多数区块链用户希望被动地将他们的硬币保存在钱包中，只有在想要进行交易时才上线。然而，在这种无状态的区块链中，用户必须不断监视其他人的交易，以保持他们的见证信息最新。尽管第三方可以代表用户进行此监视，但这偏离了标准的无状态区块链模型。实际上，这对于无状态区块链来说是一个无法克服的挑战，给用户带来了沉重的负担。

我们的结论：无状态是不可能的

这种现象不仅仅适用于这种 Merkle 树结构——所有已知的无状态区块链方案都要求用户频繁更新他们的见证信息，我们在这里进行了证明。更准确地说，我们表明，必须更新其见证信息的用户数量与所有用户进行的交易总数大致呈线性增长。

这意味着即使用户 Alice 不进行任何交易，她的见证信息也可能需要随其他用户的交易而改变。只要验证者存储的简洁状态太小而无法捕捉到完整的状态（即所有账户余额的集合），增加简洁状态的大小帮助甚微。我们根据我们的定理绘制了下面所示的这种关系图，以及每天对于不同吞吐量的区块链所需的见证信息更改次数。这些图显示了最佳无状态区块链需要更改见证信息的次数。在这里，数据宇宙指的是账户模型中的总账户数或 UTXO 模型中的总 UTXO 数量。

我们的证明核心是一个信息论的论证。信息论的一个核心原理，由 Claude Shannon 形式化，是如果 Alice 从一个大小为 2 n 的集合中随机选择一个对象，并希望告诉 Bob 她选择了哪个对象，她必须发送至少 n 个比特给他。如果存在一个无状态区块链方案，其中用户很少更新他们的见证信息，Alice 可以用少于 n 个比特告诉 Bob 她选择了哪个对象，而这是不可能的，正如 Shannon 所证明的。因此，这样的无状态区块链是不存在的。

为了简单起见，我们在这里描述一个稍微弱一些的陈述的证明：不存在一个无状态区块链，用户永远不需要更新他们的见证信息。关键是 Alice 使用无状态区块链方案来对她的消息进行编码，发送给 Bob。最初，Alice 和 Bob 都知道所有 n 个用户的完整的账户余额对集合。假设每个账户至少有一个币。Alice 和 Bob 也都知道无状态区块链的简洁状态 V 和所有账户余额对（ai， bi）的见证 wi。Alice 和 Bob 还商定了消息和账户集合之间的映射关系。Alice 将选择一个与她的消息对应的账户集合 A，然后她将从这些账户中花费币。她将使用无状态区块链向 Bob 传达她选择的集合，他可以从这个集合中了解她的消息。

编码：Alice 从 A 中的每个账户中花费一个币。使用无状态区块链方案，Alice 计算出更新后的状态 V'并将其发送给 Bob。

解码：对于每个 i，Bob 检查 Verify （wi， （ai， bi））是否为真。Bob 输出账户集合 B，使得 Verify（wi， （ai， bi）） = false。

Bob 成功地输出了 Alice 选择的相同集合：B = A。首先，观察到如果 Alice 从账户 ai 中花费了一个币，其旧余额的见证不应再被接受——否则，Alice 将能够进行双重支付。因此，对于 A 中的每个账户 ai，Verify（wi， （ai， bi）） = false，Bob 将把这个账户包括在 B 中。另一方面，Bob 永远不会将 Alice 没有从中花费币的账户包括在 B 中，因为这些账户的余额保持不变，并且（回想一下我们要证明的放宽的陈述）它们的见证永远不会改变。因此，B 恰好等于 A。

最后，我们通过计算 Alice 应该发送给 Bob 的位数来解决我们的矛盾。她可以选择的子集有 2 的 n 次方个，所以根据香农的定律，她应该至少发送 n 位个比特给 Bob。然而，她只发送了常数大小的状态 V'，它比 n 位短得多。

虽然我们在描述我们的证明时使用了无状态区块链，但 Alice 和 Bob 可以使用各种其他经过身份验证的数据结构执行类似的高效通信，包括累加器、向量承诺和经过身份验证的字典。我们使用一个我们称之为可撤销证明系统的新抽象来形式化这类数据结构。

结果的影响

我们的结果表明，你不能“通过密码学消除状态”，没有灵丹妙药的承诺方案允许我们构建一个用户永远不必更新他们见证的无状态区块链。状态并没有消失，而是从验证者手中转移出来，并以频繁见证更新的形式推送给用户。

还存在一些其他有前途的解决方案，它们偏离了严格的无状态区块链模型。这个模型的一个自然放宽是允许第三方（既不是用户也不是验证者）负责存储完整的状态。这个称为证明服务节点的第三方使用完整的状态为用户生成最新的见证信息。然后用户可以像在常规的无状态区块链中一样使用这些见证信息进行交易，其中验证者仍然只存储简洁状态。这个系统的激励机制，特别是用户如何补偿证明服务节点，是一个有趣的开放研究方向。

虽然我们迄今为止的讨论集中在 L1 区块链上，但我们的结果也对 L2 系统（如 Rollup 服务器）产生影响。Rollup（无论是 Optimistic 还是 ZK）通常使用一个小值在 L1 上存储一个大状态的承诺。这个状态包括 L2 上每个用户的账户。我们希望这些用户能够直接在 L1 上提取资金（无需 L2 服务器的合作），通过发布对他们当前账户余额的见证来实现。这个设置在我们的模型中也是可撤销证明系统的一个实例。事实上，可以说无状态区块链已经在实践中得到了实现，以 L2 Rollup 的形式。

然而，不幸的是，这意味着我们的不可能性结果直接适用。用户的 Rollup 提取见证必须经常更改，否则几乎整个 L2 状态都必须写入 L1。因此，如今的 Rollup 通常假设存在一个数据可用性委员会（有时称为“validium”），类似于“证明服务节点”，帮助用户在准备提取时计算新的见证信息。我们的结果表明，以太坊文档中对用户的警告：“如果没有交易数据，用户无法计算 Merkle 证明以证明对资金的所有权并执行提取。”将始终适用。