区块更新摘要：无需全域状态树的成员资格证明
作者： Cody Littley、Alejandro Ranchal-Pedrosa ( @alranpe )、Omar Garcia — Sei Labs
TL;DR： BUD 是一种成员资格证明方案，它随著每个区块的写入量而不是总状态大小而扩展，而无需在关键路径上设定全域状态 trie。
动机
成员资格证明（也称为状态证明，由eth_getProof提供）允许链下观察者在无需信任第三方的情况下，以加密方式验证链上值。标准方法是在整个状态上建立一个 Merkle trie 树，这样，对根杂凑进行签名并结合 Merkle 路径，即可证明任何金钥的包含或排除。
这种方法的成本会随著状态总量的增加而增加：每个区块都必须更新一棵树，而这棵树的叶子节点跨越数百万个帐户和储存槽位。对于高吞吐量的 EVM 等效链来说，这种开销会成为难以承受的瓶颈，无论是在原始计算方面，还是在它所强制的资料库布局方面。即使是以太坊 L1 层，维护全域状态树也会带来显著的复杂性和 I/O 开销。
我们提出了一种名为区块更新摘要（BUD）的增量式认证资料结构，它将状态承诺成本与总状态大小解耦，而是根据每个区块的更新量进行扩展。 BUD 可以与我们称为SuperBUD 的分层摘要层以及按需存取交易相结合，从而满足各种延迟、证明大小和成本需求。
二元状态树和Verkle树的区别
以太坊 L1 路线图已将二元状态树 (EIP-7864) 确定为长期状态承诺机制，并计划采用O(1 )复杂度的SNARK 验证来验证状态证明。对于致力于在共识关键路径上维护全域认证资料结构的链而言，这些提案明显优于目前的 MPT。 BUD 则完全解决另一个问题，两者互为补充，而非竞争关系。
BUD 解决了一个不同的架构问题：经过认证的资料结构是否应该存在于共识关键路径上？
无论全域状态树的实作效率如何（MPT、二元树、Verkle 树），每个验证者都需要在区块执行期间维护和更新一个 trie 树状资料结构。此 trie 树限制了资料库布局，每次写入都会引入与树深度成正比的 I/O 放大，并将执行吞吐量与状态提交成本纠缠在一起。即使是完美的二元树，其复杂度也仅为O(log n) O ( log n) 。 n )路径施加O(w \cdot \log n) O ( w ⋅ log n )每个区块进行w次状态写入的杂凑计算，且资料库必须以 trie 友善的布局储存中间节点。
BUD 认为，对于高吞吐量的执行环境，将 trie 树放在验证器的关键路径上是不合适的抽象层。相反，验证器产生一个轻量级的区块摘要（成本仅与写入集成正比，与总状态大小无关），而完整的证明基础设施则委托给归档节点。状态本身可以储存在任何对原始执行速度最优的扁平键值储存布局中，不受 trie 树式 I/O 的限制。
这是一种架构选择，而非临时解决方案。采用 BUD 的区块链并非“等待迁移到更好的 trie 树”，而是选择完全不在关键路径上维护全域 trie 树。
需要注意的是，SNARK 验证论证是对称的：BUD Merkle 证明也可以用 SNARK 验证，而且由于 BUD 树更小（与The Block写入集合成正比，而非与完整状态成正比），电路也更简单。如果最终目标是为跨链桥和轻客户端提供 SNARK 验证的状态证明，那么两种方法都能达到目的；问题仅仅在于区块生成过程中验证者所承担的成本。
核心思想
芽
芽（BUD）是一个小型默克尔树，它基於单一区块（或更一般地，任何连续的k个区块视窗）产生的变化构建而成。每个叶子记录：
- 关键在于，
- 它的新价值，
- 当前区块编号，以及
- 密钥上次修改时所在的区块编号。
栏位 (4) 是关键的新增功能：它将每个键的修改链贯穿 BUD 序列中，以便同一键的两个相邻 BUD 条目可以证明其间没有任何变更。为了支援这一点，键值储存中的每个条目都携带 8 个额外的元数据，用于记录其上次修改的The Block高度（外加 1 个位元组的序列化版本栏位）。
图 1：BUD Merkle 树的结构。每个叶子节点记录（键、新值、当前区块号、已修改的前一个区块号）。 BUD 杂凑由权益大于 (n+f)/2 的验证者签署。
验证者对 BUD 杂凑值进行签名，并以常规方式聚合签名（法定人数为> (n+f)/2 > ( n + f ) / 2 个权益，其中至多f个权益为对抗性权益）。然后，BUD 被串流到归档节点进行长期储存和证明服务。
由于树仅基于资料区块中修改过的键构建，因此其构建成本与资料区块的写入集成正比，而非与全局状态的大小成正比。一个修改了 10,000 个键的资料区块，无论全域状态的总条目数是否达到 1 亿，都会建立一个包含 10,000 个叶子节点的树。
超芽
单一 BUD 验证键在其被修改的The Block中的值，但轻客户端查询d个区块前最后写入的键的当前值时，如果想排除该键，则需要检查d个BUD。 SuperBUD 将此线性扫描压缩为对数级扫描。
一个等级为 ℓₜ的SuperBUD跨越eℓ个区块（其中e是一个可配置的基数；我们以e = 2为例） ，并且产生于eℓₜ的倍数的区块高度处。在内部，SuperBUD 是一个 Merkle树，它将跨越范围内每个被触及的键映射到该键被修改的最新区块号。同一层级的两个相邻 SuperBUD 可以透过合并它们的键集，并且对于同时出现在两个 SuperBUD 中的键，仅保留最近的区块号，合并成下一级别的一个 SuperBUD。这种合并操作只需对两个已排序的 Merkle 树进行一次O(n )的协同遍历即可完成。
对于给定的密钥，SuperBUD 证明要么显示 (a) 密钥被修改的跨度内的最高区块，要么显示 (b) 密钥在该跨度内根本没有被修改。结合在已识别区块上的 BUD 证明，即可获得完整的成员资格证明。
图 2：基于基数e = 2的区块 B0–B11 上的 SuperBUD 层次结构。 1 级 SuperBUD 跨越 2 个区块，2 级跨越 4 个区块，3 级跨越 8 个区块。同一级别的相邻 SuperBUD 透过一次O( n )遍历合并到下一级。
延迟和证明大小。如果上次修改发生在 d d 个区块之前，则客户端需要一个等级为\lceil \log_e d \rceil ⌈ log e 的SuperBUD。 d ⌉ 。最坏情况下，客户端最多需要等待e^{\lceil \log_e d \rceil} e ⌈ log e d ⌉区块用于等待该层级下一个对齐视窗关闭。因此，等待时间在最坏情况下是线性的，但这种层级结构带来的好处是证明的紧凑性：摘要查找次数呈对数级，默克尔路径数量为常数，而不是每个区块的排除证明的线性链。
触摸交易
SuperBUD 以延迟换取证明的紧凑性，且不产生链上成本；而触碰交易则提供了相反的权衡：支付少量链上费用即可在当前区块立即获得 BUD 证明，无论密钥有多么陈旧。
触碰交易不会修改键的值；它只会更新「最后修改」元数据，并在当前区块的 BUD 中产生一笔记录。这类似于 Unix shell 中的touch指令：刷新时间戳记而不改变内容。触碰交易的定价是基于链上现有的资源计量机制（按状态存取和元资料写入单位计费），因此除了费用表已涵盖的部分之外，不会引入新的拒绝服务攻击面。
SuperBUD 和触控交易共同涵盖了整个延迟/成本设计空间：对成本敏感的用户等待 SuperBUD；对延迟敏感的用户进行触摸。
证明策略
BUD 和 SuperBUD 可以组成几种证明策略，每种策略都有不同的权衡取舍。
单次 BUD 验证。如果查询的区块高度与修改点（或接点）重合，则一次 BUD 验证即可。极其紧凑，但仅在修改点可用。
双重 BUD 证明。对同一密钥进行两次连续的 BUD 证明，其中第二次证明的「上一个区块已修改」栏位指向第一个证明，即可证明其间任意区块的值。每个密钥的修改链保证了不会遗漏任何中间变更。
BUD + SuperBUD。 BUD证明最后一次修改的数据，并结合 SuperBUD，SuperBUD 的跨度涵盖该修改和目标区块。 SuperBUD 证明在其跨度内不存在后续修改。这种方法紧凑且成本低廉，但对于最近修改过的条目会有中等延迟，而对于过时的条目则延迟较高。
图 3：策略 BUD + SuperBUD。在区块 B2 处使用 BUD 证明，结合跨越 A–C 的 SuperBUD，可以证明密钥 K 在 SuperBUD 上限边界之前的任何区块的值，而无需进行接触交易。
BUD + 多个 SuperBUD。为了在不进行接触式交易的情况下降低延迟，可以将多个相邻的 SuperBUD 连结起来以弥补延迟。这种方法虽然不太紧凑（证明大小会随著时间推移而增加），但可以避免链上成本。
首次修改证明。如果 BUD 条目的「上一个区块已修改」值为-1 - 1 ，则表示该金钥在该区块之前不存在（追溯到可设定的证明截止点）。这对于排除证明和最近创建的密钥非常有用。
设计选择和灵活性
建筑采用模组化设计。我们重点介绍其主要的灵活性体现：
BUD粒度。我们预设采用1:1的粒度（每个区块一个BUD），但也可以在前一个时间窗口内每隔k个区块产生一个BUD。这样可以分摊签名开销，但代价是证明的精准度略低。
SuperBUD的基础层级和调度。层级结构的基础层级e控制分支因子。当e = 2 时，层级跨度翻倍（2, 4, 8, 16, …），最大合并深度L决定最大证明年龄：系统支援最近e^ L区块内任何区块的证明。较大的e值会减少层级数量，但会增加最坏情况下的等待时间。如果链的最终性节奏使得某些边界更自然，则可以将生产调度（与e^\ell e ℓ的倍数对齐）进行偏移或交错。
最大证明期限和墓碑。删除密钥不得破坏其修改链。状态不会删除条目，而是写入一个墓碑（值为 nil，保留「最后修改」元资料）。可配置的最大证明期限（例如，区块的天数或月数）限制了墓碑的保留时间：一旦墓碑的年龄超过截止期限，就会被垃圾回收。在截止期限之前产生的证明将无限期地保持有效和可验证；失效的是为非常古老的区块产生新证明的能力。
排除证明。 SuperBUD本身无法证明排除性，因为它们不断言密钥的预先存在状态。完整的排除证明需要一个 BUD 条目（可能透过对不存在的金钥进行接触交易创建，从而产生墓碑标记）。这是一种有意为之的设计权衡：证明一个从未存在且没有墓碑标记的密钥不存在的极端情况非常罕见，因此需要进行接触交易是可以接受的。
与全域状态树的比较
| 方面 | 全域状态特里树（包括 Binary/Verkle） | 芽 + 超芽 |
|---|---|---|
| 建筑师职位 | 在共识关键路径上 | 卸载到归档基础设施 |
| 每个区块的承诺成本 | O(w \cdot \log n) O ( w ⋅ log n )哈希（ ww写入， nn状态条目） | O(w \cdot \log w) O ( w ⋅ log w ）哈希（ w w仅写入） |
| 资料库布局 | 需要适合Trie的储存方式 | 扁平键值存储，每个条目额外包含 9 位元组元数据 |
| 为目前状态产生证明 | 立即（来自 trie 树的单一 Merkle 路径） | 立即触摸；否则请等待 SuperBUD |
| 校样尺寸 | O(log n) O ( log n ） | O(log w) O ( log w )每个 BUD + O(\log s) O ( log s ）每 SuperBUD |
| SNARK友好性 | 可证明；电路复杂度为O(log n) O ( log n ）路径 | 可证明；电路复杂度为O(log w) O ( log w ）路径（较小） |
| 验证器储存负担 | 完整trie树（中间节点+叶节点） | 目前状态 + 9 位元组元数据 |
| 谁来提供证据 | 验证节点或全节点 | 归档节点（专用基础设施） |
核心权衡：全域 trie 树可以立即为任何最近区块的任何键提供证明，但代价是执行层与 trie 树的维护纠缠在一起。 BUD 仅在修改点（或透过 touch 按需）提供立即证明，但使执行层摆脱了任何 trie 树形状的约束。
目标和后续步骤
BUD 是一种永久性的架构方案，用于在共识关键路径上维护全域状态树。它们并非等待采用更优 trie 树的链的过渡机制，也不是叠加在现有 trie 树之上的补充。相反，BUD 的设计初衷是为那些选择完全不在验证者关键路径上维护全域认证资料结构的链而生，它们将证明基础设施委托给归档节点，以换取不受限制的执行吞吐量。
主要目标用户是高吞吐量的 EVM 等效 L1 快取和 Rollup 缓存，在这些快取中，状态树维护已成为或即将成为执行瓶颈。对于以太坊 L1 快取而言，由于二元树迁移（EIP-7864）已在进行中，BUD 并非其天然的适用方案。但对于那些从零开始设计状态承诺策略，或随著状态成长而重新考虑状态承诺策略的炼而言，BUD 提供了一种截然不同的扩展路径。
我们正在准备一份资讯性环境影响评估报告（EIP），以规范该建设方案。我们欢迎就设计、参数选择和潜在的应用路径进行讨论。
完整的 RFC 可供查阅；一旦 EIP 草案发布，我们将提供连结。
未解决的问题
我们欢迎就以下议题展开讨论：
- 参数选择：在实际应用中，对于高吞吐量链，基本 e和最大证明年龄的合适值是多少？ e = 2是正确的预设值，还是更大的分支因子更适合典型的金钥年龄分布？
- 排除证明的极端情况：要求透过接触交易来证明从未存在过的密钥不存在，这是一种有意为之的权衡。这在实践中是否可以接受，还是需要不同的解决方案？
- 归档节点激励机制： BUD 将证明服务完全委托给归档节点。什么样的激励机制能够确保归档节点在长期内维持可用性和诚信？
- 采用路径：对于已经运行全域状态 trie 的链来说，迁移到 BUD 的破坏性最小的路径是什么？
