的总数。 我们证明的核心是信息论论证。Claude Shannon提出的信息理论的一个核心原则是，如果Alice从一个大小为2n的集合中随机选择了一个对象，并希望告诉Bob她选择了哪个对象，她必须向他发送至少n位。如果存在一个无状态的区块链方案，用户很少更新他们的见证，那么Alice可以用少于n比特的时间告诉Bob她选择了哪个对象——Shannon证明这是不可能的。因此，这种无状态区块链是不可能存在的。 为了简单起见，我们将在这里描述一个稍弱的陈述的证明：不可能存在用户永远不需要更新其见证的无状态区块链。关键思想是Alice使用无状态区块链方案将她的消息编码给Bob。最初，Alice 和 Bob 都知道所有n 个用户的完整帐户余额对。假设每个账户至少有一枚币。Alice 和 Bob 也都知道无状态区块链的简洁状态V和所有账户余额对( a i , b i )的见证人 w i。Alice 和 Bob 还就消息和帐户集之间的映射达成了一致。Alice会选择与她的消息对应的一组A账户，然后她会从这些账户中花费代币。她将使用无状态区块链与Bob沟通她选择的集合，而他可以从该集合中了解她的消息是什么。 编码： 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。 Bob成功地输出了与Alice选择的相同集合：B = A。首先，观察到如果Alice从帐户a i中花费了一枚代币，则不应再接受其旧余额的见证 - 否则，Alice将能够加倍花费。因此，对于A中的每个账户a i，Verify( w i , ( a i , b i )) = false，并且 Bob 会将该账户包含在B中。另一方面，Bob 绝不会在B中包含Alice 所识别的账户。没有_花一枚代币，因为这些账户的余额保持不变，并且（回想一下我们要证明的宽松声明）他们的见证人永远不会改变。因此，B完全等于A。 最后，通过计算Alice应该发送给Bob的比特数来解决矛盾。她可以选择的账户子集有2 n 种可能，根据Shannon定律，她至少应该发送n比特给Bob。然而，她只发送了常量大小的状态V'，远远比n比特要短。 (熟悉密码学的读者可能会注意到，我们在这里掩盖了一些细节；例如，Bob的解码失败的概率可以忽略不计。我们的论文包括完整的证明。) 虽然我们用无状态区块链描述了我们的证明，但Alice和Bob可以使用各种其他经过身份验证的数据结构(例如累加器、向量承诺)执行类似的过于高效的通信。我们使用一种新的抽象来形式化这类数据结构，我们称之为可撤销证明系统。 结果带来的影响 我们的结果表明，你不能“加密状态”——没有灵丹妙药式的方案允许我们构建一个用户永远不必更新他们的见证的无状态区块链。状态并没有消失，而是从验证器转移到用户身上，以频繁更新见证的形式推送给用户。 确实存在一些潜在的解决方案，但这些解决方案脱离了严格的无状态区块链模型。该模型允许第三方(既不是用户也不是验证者)负责存储完整的状态。这一方被称为证明服务节点(由Srinivasan等人进行了最严格的检查)，它使用完整状态来代表用户生成最新的见证。然后，用户可以使用这些见证进行交易，就像在常规的无状态区块链中一样，其中验证器仍然只存储一个简洁的状态。该系统的激励机制，特别是用户如何补偿证明服务节点，是一个有趣的开放研究方向。 虽然到目前为止我们的讨论主要集中在L1区块链上，但我们的结果也会对L2系统(如rollup服务器)产生影响。rollup(无论是optimistic的还是ZK的)通常采用一个大的状态并使用存储在 L1 上的一个小值来提交它。此状态包括L2上每个用户的帐户。我们希望这些用户能够通过发布其当前账户余额的见证来直接在 L1 上提取资金（无需 L2 服务器的配合）。此设置也是我们模型中可撤销证明系统的一个实例。事实上，有人可能会说无状态区块链已经以 L2 rollup的形式在实践中得到了实施。 不幸的是，这意味着我们的不可能性结果直接适用。用户的rollup取款见证必须经常更改，否则几乎整个L2状态都必须写入L1。因此，今天的集合通常假设有一个数据可用性委员会(有时称为“有效性委员会”)，其功能类似于“证明服务节点”，在用户准备退出时帮助他们计算新的见证。我们的研究结果表明，以太坊文档中对用户的警告——“如果无法访问交易数据，用户无法计算证明资金所有权和执行提款所需的默克尔证明。”——将永远适用。 随着区块链系统的发展，开发更有效的方法来管理区块链状态将变得更加重要。尽管我们排除无状态区块链的结果似乎是消极的，但不可能的结果对区块链设计者来说是有用的，因为它们告诉我们将研究重点放在其他地方，理想情况下可以帮助我们更快地找到可行的解决方案。 来源：金色财经lg...
北美站
