a16z Crypto：无状态区块链付诸实践的不可能性探讨

原文标题：On the impossibility of stateless blockchains

作者：Miranda Christ，哥伦比亚大学 CS博士，a16z 暑期实习研究员 & Joseph Bonneau，a16z 研究合伙人

编译：bayemon.eth，ChainCatcher 

随着区块链技术用户的增加和以及发生于其上的交易日益频繁，验证者为验证交易而存储的信息量（"状态"）也在增加。例如，在比特币中，状态由一组未花费的交易输出（UTXOs）组成。在以太坊中，状态包括每个账户的账户余额以及每个智能合约的代码和存储空间。

对于拥有足够账户或UTXOs的区块链来说，这种存储负担将变使得区块链难以支持相当一部分人的真正日常交易，从而让这些用户无从成为验证者，并因此对去中心化构成威胁。由于 Merkle Tree 和 ZK等工具已经帮助区块链实现了不可思议的目标，我们因此想要诉诸密码学寻求相应的解决方案。

这正是 "无状态区块链 "的目标。但是，尽管在这方面做了大量工作，相应的方案仍然远未实用化。但事实证明，由于构造与实用之间的无法弥合的差距，这种进展滞后是与生俱来的，这种滞后似乎是任何行业发展过程中天然的障碍。我们的最新研究表明，如果不采取额外的措施来管理“状态”，那么无论多么智能的无状态区块链方案都是不可行的。不过，正如我们在本文章末尾所说的那样，即便结果并不实际，我们也不应当因此气馁。

何为“无状态”

如今，状态虽然庞大，但易于管理。例如，比特币节点存储约 7 GB 的数据，以太坊节点存储约 650 GB 的数据。但是，全节点的存储负担与链的吞吐量（每秒交易量或 TPS）大致呈线性增长，然而目前主链的吞吐量属实低得离谱。就目前的设计而言，真正支持日常交易（数万到数十万 TPS）所需的状态将非常庞大，需要数 TB 甚至数 PB 的存储空间。

主链有限的性能促使人们寻找技术方法，以大幅减少验证者所需的状态量。最好的技术方法就是构建无状态区块链，即无论交易吞吐量如何，验证器只需存储一个恒定大小的状态。(这个术语实际上是个误解：状态仍然以恒定大小存在，只是小到足以在未来任何吞吐量下都能够正常运行）。无状态区块链可以大幅降低对于硬件的存储要求，使得运行验证器节点变得更加容易，乐观地说，每个人都能在手机上运行一个节点。而由于验证器数量的增加会提高链的安全性，因此降低验证器的准入门槛非常重要。

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

与永不更改的私钥不同的是，这些见证会经常变化，即使对没有积极交易的用户来说也是如此，这会给用户带来了难以想象的负担。想象一下，如果你必须持续监控全球所有其他信用卡交易，并相应地更新一些本地数据，才能使用自己的信用卡，确实会引发不必要的麻烦。因此，要使区块链切实可行，用户必须能够保持离线状态，且只有在提交交易时才与区块链互动。这也就意味着对于硬件钱包在内的多种情况下，见证是完全无从更新的。

这让我们自然而然地想到了一个研究问题：我们能否建立一个不需要（或很少需要）更新见证的无状态区块链？为了回答这个问题，我们开发了一个新颖的理论框架（可撤销证明系统），对无状态区块链进行了概括。利用这个框架，我们证明了一个确凿的不可能事件：在简洁的全局状态和频繁的见证更新之间的是几乎无法平衡的。我们的证明技术是信息理论性的，这意味着未来的计算机不会强大到足以解决这个问题：无状态区块链构造与实用性之间的鸿沟将永远无法弥合。

研究背景

为了进一步直观认识上文中提到的“不可能事件”，我们将首先使用 Merkle Tree 描述无状态区块链的自然方法（尽管基于 Merkle Tree 的解决方案效率并不高）。我们的目标是让验证者确定用户提交的交易是否有效——例如，用户拥有足够的账户余额可用于交易。在无状态区块链方案中，验证器存储一个恒定大小的状态，当用户进行交易时，他们的交易必须包含一个见证。验证器可以使用当前状态和用户提交的（交易、见证）对来验证该用户是否有足够的账户余额来进行交易。

我们首先构建一棵 Merkle Tree，其中每对（账户 ID，余额）键值对（a,b）都是树上的叶子。验证者存储的恒定大小的状态 V 是这棵树的根，并充当账户-余额键值对的承诺。每个用户都必须通过 Merkle 包含证明维护其（账户ID，余额）信息。叶子（a,b）的 Merkle 包含证明由其通向树根的路径上的节点集（v1, ..., vk）组成。验证者可以通过检查 (a,b) 的证明（v1, ..., vk）与其当前状态 V 来检查 b 是否确实是账户 a 的余额。Merkle Tree 的一个特性是，如果给定了叶子的 Merkle 包含证明，那么当叶子发生变化时，就很容易计算出结果根。换句话说，验证者可以很容易地计算出更新的状态 V'，该状态可以捕捉到交易执行后账户 a 的新余额。

然而Merkle Tree有两个主要缺点，首先，用户见证相对较大，随系统中账户总数的对数增长而增长。理想情况下，它们应该是恒定大小的，可以使用 RSA 累加器等方案来实现（Boneh 等人在无状态区块链中对此进行了研究）。

第二个缺点更难避免：只要有其他用户进行交易，账户-余额键值对对的证明就会发生变化。回想一下，叶子的证明由从叶子到树根的路径上的节点集组成。如果任何其他叶子发生变化，这些节点中的一个也会发生变化，这就带来了一个实际问题。大多数区块链用户都希望被动地将他们的币保存在钱包中，只有当他们想进行交易时才上线。然而，在这种无状态区块链的实际应用中，用户必须不断监控其他人的交易，以保证自己的见证人是最新的。(虽然第三方可以代表用户进行监控，但这偏离了标准的无状态区块链模式。我们将在本篇文章的最后对此进行讨论）。实际上，这对无状态区块链来说是一个难以克服的挑战，给用户带来了沉重的负担。

结论：无状态区块链是不可能实现的

这种现象并不是 Merkle Tree 独有的缺陷——当前所有已知的无状态区块链方案都要求用户经常更新他们的对应的见证信息。更准确地说，必须更新见证信息的用户数量与所有用户的交易总量大致呈线性关系，并单调递增。

这意味着，即使用户 Alice 没有进行任何交易，她的见证信息也可能需要随着其他用户的交易而改变。 只要验证者存储的简洁状态太小，无法捕捉到完整状态（即所有账户余额的集合），那么简洁状态存储的规模增加就没有什么帮助。我们在将这种隐含关系可视化，同时也输出了不同吞吐量的区块链每天所需的验证人变更次数。这些图显示了最佳无状态区块链所需的见证变更次数。其中，data universes 指的是账户模型下的账户总数或UTXO模型下的UTXO总数。

我们证明的核心是信息论的论证。Claude Shannon 正式提出的信息论核心原则是：如果 Alice 从大小为 2n 的集合中随机选择一个对象，并想要告知 Bob 她的选择，则必须向鲍勃发送至少 n 个比特。如果存在一种无状态区块链方案，且用户无需更新他们的见证，爱丽丝就可以用少于 n 个比特的花费告诉Bob她的具体选择——然而 Shannon 证明这是不可能的。因此，我们同样认为不可能存在这样的无状态区块链。

简单起见，我们先作一个弱化的证明，即不可能存在用户永远不需要更新其见证的无状态区块链。证明的关键过程涉及，Alice 使用无状态区块链方案将她的信息编码传输给 Bob。起初，假设Alice和Bob都知道所有 n 个用户的全部账户-余额对，同时每个账户余额至少为1。此外，Alice和Bob还知道无状态区块链简介状态 V以及所有账户余额对（ai，bi）的见证 wi， 两人商定了信息与账户集之间的映射。Alice将选择一组与她的信息相对应的账户 A，并使用账户余额进行消费，最终使用无状态区块链向 Bob 传达她选择的账户集，而Bob可以从这个账户集中了解到她的信息是什么。

编码：Alice 使用无状态区块链方案计算出更新后的状态 V'，并将 V' 发送给 Bob。

解码：对于每一个 i，Bob 会检查 Verify(wi,(ai,bi))。Bob输出账户集合 B，使得 Verify(wi, (ai, bi)) = false。

最终，Bob成功输出了与Alice所选的同一集合，即 B = A。首先，请注意，如果 Alice 花掉了账户 ai 中的一枚硬币，则其旧余额的见证不应再被接受——否则，爱丽丝就可以重复消费。因此，对于 A 中的每一个账户 ai，Verify(wi, (ai, bi)) = false，Bob将把这个账户包含在 B 中。另一方面，Bob不会把没有余额不变的账户包含在 B 中，因为这些账户的余额保持不变，而且（回想一下我们要证明的“弱化”声明）它们的见证人永远不会改变。因此，B 恰好等于 A。

最后，我们通过计算 Alice 本应发送给鲍勃的比特数来得出矛盾。她可以选择的账户子集有 2n 个，因此根据 Shannon 定律，她应该至少发送 n 个比特给 Bob。然而，她只发送了恒定大小的状态 V'，比 n 比特短得多。

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

虽然我们用无状态区块链来描述我们的证明，但爱丽丝和鲍勃也可以使用其他各种认证数据结构（包括累加器 Accumulators、向量承诺 Vector Commitments 和授权字典 Authentiated dictionaries）执行类似的高效通信。我们使用一个新的抽象概念将这一类数据结构形式化，我们称之为可撤销证明系统(revocable proof system)。

结论的含义

以上结果表明，我们无法“用加密技术完全消除状态”，因此也并没有易总方案能够将建立无状态区块链变为现实，使得用户永远无需更新见证。状态不会消失，而是会从验证者处转移，以频繁更新见证的形式推送给用户。

目前确实存在几种偏离严格无状态区块链模型的其他有合理的解决方案。对这种模式的一种自然放宽是允许第三方（既不是用户也不是验证者）负责存储全部状态。这一方被称为证明服务节点（Srinivasan 等人对其进行了最严格的研究），它使用完整状态代表用户生成最新的见证。然后，用户可以使用这些见证进行交易，就像在普通的无状态区块链中一样，验证者仍然只存储简洁的状态。该系统的激励机制，尤其是用户如何补偿证明服务节点，是一个有趣的开放研究方向。

虽然迄今为止的讨论主要集中在 L1 区块链上，但我们的结果也会对 roll up等 L2 系统产生影响。无论是 Optimistic 或是 zk rollup，通常情况下都是生成一个较大的状态值，并通过相应手段向L1提交一个小值并存储。我们希望这些用户在无需L2服务器的配合，通过直接向发布账户余额见证，直接在 L1 上提取资金。在我们的模型中，这种设置也是可撤销证明系统的一个实例。事实上，可以说无状态区块链已经在实践中以 L2 rollup的形式实现了。

但遗憾的是，我们的“不可能事件”无法直接投入应用。用户的rollup撤回见证必须时常变更与同步，否则几乎整个L2层状态都要全部写入L1。因此，如今的rollup解决方案通常会设置一个数据可用性委员会（有时称为 "validium"），其功能类似于 "证明服务节点"，即在用户准备退出时帮助他们计算新的见证。我们的研究结果表明，如果无法访问交易数据，用户就无法计算证明资金所有权和执行提现所需的 Merkle Tree，这也正是以太坊文件中对用户而言始终适用的警告。

随着区块链系统的发展，开发更有效的区块链状态管理方法将变得越来越重要。虽然我们的研究认为无状态区块链不可能投入应用的结果，看起来是负面的，但这一结论仍然对区块链设计者来说是有意义的。因为它们告诉我们要把研究重点放在其他地方，最好能帮助我们更快地找到可行的解决方案。