作者：Miranda ChristJoseph Bonneau / 来源：https://a16zcrypto.com/posts/article/on-the-impossibility-of

翻译：火火/白话区块链
 

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

对于拥有足够账户或 UTXO 来支持大部分人口真正日常交易的区块链来说，这种存储负担将变得难以处理，从而使其难以成为验证者、并对去中心化构成威胁。人们很容易转向密码学作为解决方案，默克尔树和零知识证明等工具已经帮助我们实现了以前难以置信的目标。 

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

1、无状态区块链状态

如今，国家规模庞大但易于管理。例如，比特币节点存储约 7 GB的数据，以太坊节点存储约 650 GB 的数据。但全节点的存储负担随着链的吞吐量（每秒交易数或 TPS）大致呈线性增加，而目前该吞吐量低得令人无法接受。根据当前的设计，真正支持日常交易（数万到数十万 TPS）所需的状态将非常笨重，需要 TB 甚至 PB。

这促使人们寻找技术方法来大幅减少验证者所需的状态量。圣杯是无状态区块链，它要求验证器仅存储恒定大小的状态，而不管事务吞吐量如何。（这个术语实际是一个误称：仍然存在一个状态，它足够小，足以在任何未来的吞吐量下实用 - 通常它是恒定大小的。）

这样的轻存储要求将使运行验证器节点变得更加容易；乐观的是每个人都可以在他们的手机上运行一个节点。由于增加验证者的数量可以提高链的安全性，因此降低验证者的进入门槛非常重要。  

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

与存储永远不需要更改的私钥不同，这些见证人经常更改，即使对于不积极进行交易的用户也是如此，这给用户带来了很大的负担。同样，想象一下，如果您必须持续监控全球所有其他信用卡交易并相应更新一些本地数据才能使用您自己的信用卡。为了让区块链变得实用，用户必须能够保持离线状态，并且只有在提交交易时才能与区块链进行交互。在许多情况下，就像硬件钱包一样，更新见证不仅不方便而且不可能。

这给我们带来了一个自然的研究问题：我们能否构建一个不需要见证人更新（或很少需要见证人更新）的无状态区块链？为了回答这个问题，我们开发了一个新颖的理论框架（可撤销证明系统）来概括无状态区块链。使用这个框架，我们证明了一个结论性的不可能结果：简洁的全局状态和频繁的见证更新之间的权衡是根本性的。我们的证明技术是信息论的，这意味着未来的计算机都不会强大到足以解决这个问题：无状态区块链结构和实用性之间的差距永远无法弥合。

2、我们的研究背景

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

我们首先构建一棵 Merkle 树，其中每个（账户 ID，余额）对（a，b）都作为叶子包含在内。验证器存储的恒定大小的状态V是该树的根，它充当对帐户余额对集的承诺。每个用户都维护其（账户 ID、余额）对的 Merkle 包含证明作为其见证人。叶子 ( a , b ) 的 Merkle 包含证明由沿着其到树根的路径上的伙伴节点 ( v 1 , …, v k ) 组成。给定用户使用帐户a进行的交易并声明余额b，验证器可以检查b通过检查 ( a , b )的证明 ( v 1 , …, v k )与其当前状态V ，确实是帐户a的余额。如果是这样，验证器将执行交易并必须相应地更新帐户余额。Merkle 树的一个便利属性是，给定叶子的 Merkle 包含证明，当该叶子发生更改时，很容易计算生成的根。换句话说，验证者可以轻松计算更新后的状态V' ，该状态V'在交易执行后捕获帐户 a 的新余额。

这种默克尔树方案有两个主要缺点。首先，用户的见证人规模较大，在系统账户总数中呈对数增长。理想情况下，它们应该是恒定大小的，我们可以使用RSA 累加器等方案来实现（ Boneh 等人在无状态区块链的背景下进行了研究）。 

第二个缺点更难以避免：账户余额对的证明只要发生任何变化其他用户交易。回想一下，叶子的证明由从该叶子到树根的路径上的伙伴节点组成。如果任何其他叶子发生变化，这些节点之一就会发生变化，这在实践中会出现问题。大多数区块链用户希望被动地将他们的硬币保存在钱包中，并且仅在想要进行交易时才上网。然而，在这种无状态区块链的实践中，用户必须不断监控其他人的交易，以使他们的见证人保持最新状态。（虽然第三方可以代表用户进行此监控，但这偏离了标准的无状态区块链模型。我们将在本文末尾讨论这一点。）实际上，这对于无状态区块链来说是一个难以克服的挑战，给无状态区块链带来了沉重的负担。用户的负担。 

3、我们的结果：无状态区块链是不可能的 

这种现象并不是默克尔树结构特有的——所有已知的无状态区块链方案都要求用户频繁更新他们的见证人，我们在这里演示了这一点。更准确地说，我们表明必须更新见证的用户数量与所有用户进行的交易总数大致呈线性增长。 

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

我们证明的核心是信息论论证。由克劳德·香农 (Claude Shannon)形式化的信息论核心原理是，如果 Alice 从大小为2 n的集合中随机选择一个对象，并希望告诉 Bob 她选择了哪个对象，她必须向他发送至少n位。如果存在一个无状态的区块链方案，其中用户很少更新他们的见证人，那么爱丽丝可以使用少于n位告诉鲍勃她选择了哪个对象。但是香农证明这是不可能的。因此，这样的无状态区块链不可能存在。

为了简单起见，我们将在这里描述一个稍弱的陈述的证明：不可能存在用户永远不需要更新其见证人的无状态区块链。关键思想是爱丽丝使用无状态区块链方案将她的消息编码给鲍勃。最初，Alice 和 Bob 都知道所有n 个用户的完整帐户余额对。假设每个账户至少有一枚币。Alice 和 Bob 也都知道无状态区块链的简洁状态V和所有账户余额对( a i , b i )的见证人 w i。Alice 和 Bob 还就消息和帐户集之间的映射达成了一致。Alice会选择与她的消息对应的一组A账户，然后她会从这些账户中花费硬币。她将使用无状态区块链与鲍勃沟通她选择的集合，而他可以从该集合中了解她的消息是什么。 

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

解码：对于每个i， Bob 检查是否Verify( w i , ( a i , b i )) 。Bob 输出账户集合B，使得Verify( w i , ( a i , b i )) = false。 

鲍勃成功地输出了与爱丽丝选择的相同的集合：B = A。首先，观察到如果爱丽丝从帐户a i中花费了一枚硬币，则不应再接受其旧余额的见证人 - 否则，爱丽丝将能够加倍花费。因此，对于A中的每个账户a i，Verify( w i , ( a i , b i )) = false，并且 Bob 会将该账户包含在B中。另一方面，Bob 绝不会在B中包含Alice 所识别的账户。没有_花一枚硬币，因为这些账户的余额保持不变，并且（回想一下我们要证明的宽松声明）他们的见证人永远不会改变。因此，B完全等于A。 

最后，我们通过计算 Alice 应该发送给 Bob 的位数来解决我们的矛盾。她可以选择2 n 个可能的帐户子集，因此根据香农定律，她应该必须向鲍勃发送至少n位。然而，她只发送了恒定大小的状态V'，它比n位短得多。  

（熟悉密码学的读者可能会注意到，我们在这里掩盖了一些细节；例如，鲍勃的解码可能会失败，概率可以忽略不计。我们的论文包括完整的证明。）

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

3、结论

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

确实存在其他几种偏离严格无状态区块链模型的有前途的解决方案。该模型的一个特点是允许第三方（既不是用户也不是验证者）负责存储完整状态。该方称为证明服务节点（并由Srinivasan 等人进行了最严格的检查），使用完整状态代表用户生成最新的见证人。然后，用户可以像在常规无状态区块链中一样使用这些见证人进行交易，其中验证器仍然仅存储简洁的状态。这个系统的激励，特别是用户如何补偿证明服务节点，是一个有趣的开放研究方向。

虽然到目前为止我们的讨论主要集中在 L1 区块链上，但我们的结果也对 Rollup 服务器等 L2 系统产生了影响。Rollup（无论是乐观的还是 ZK）通常采用一个大的状态并使用存储在 L1 上的一个小值来提交它。此状态包括 L2 上每个用户的帐户。我们希望这些用户能够通过发布其当前账户余额的见证来直接在 L1 上提取资金（无需 L2 服务器的配合）。此设置也是我们模型中可撤销证明系统的一个实例。事实上，有人可能会说无状态区块链已经以 L2 汇总的形式在实践中得到了实施。 

但不幸的是，这意味着我们的不可能性结果直接适用。用户的Rollup提现见证必须经常更改，否则几乎整个 L2 状态都必须写入 L1。因此，今天的Rollup通常假设有一个数据可用性委员会（有时称为“validium”），其功能类似于“证明服务节点”，帮助用户在准备退出时计算新的见证人。我们的结果表明，以太坊文档中对用户的警告 “如果无法访问交易数据，用户就无法计算证明资金所有权和执行提款所需的 Merkle 证明” 将永远适用。

随着区块链系统的发展，开发更有效的方法来管理区块链状态将变得更加重要。尽管我们排除无状态区块链的结果可能看起来是否定的，但不可能性的结果对区块链设计者来说是有用的，因为它们告诉我们将研究重点放在其他地方，理想情况下可以帮助我们更快地找到可行的解决方案。