以太坊无状态系列 #4 : 探索 Verkle Trie 结构
- Chaisomsri
- 更新于 3天前
- 阅读 90
探索 Verkle Trie 结构
Verkle Trie 是引入无状态性的关键变化之一，以太坊基金会一直在继续开发和研究 Verkle Trie，以取代当前用于状态存储的 MPT（Merkle Patricia Trie）。Verkle Trie 文档 最近已更新，目前 Verkle Trie 的实现可以在 (Python, Go, Rust) 中找到。在验证 Verkle Trie 后，本文将重点关注 Verkle Trie 的结构，以提供详细的理解。
什么是 Verkle Trie?
Verkle Trie 是向量和 Merkle 树的结合，使用向量承诺而不是传统 Merkle 树中的 keccak256 哈希函数。Verkle Trie 中使用的向量承诺（VC）方案基于 Pedersen 承诺（也称为 Pedersen 哈希），这是基于多项式承诺的。
承诺的使用消除了生成证明所需的兄弟节点，由于它基于椭圆曲线，可以执行操作。这允许在树的每个级别添加所需的证明（ 多证明 ），从而减少证明的大小。一个恒定大小的证明可以包含在区块头中，实现弱状态无状态性。
(来源: SalomonCrypto)
Verkle Trie 结构
2 层结构（来源: 以太坊黄皮书, 以太坊 Reddit)
以太坊总共有四棵树：世界状态树(Trie)、收据树、交易树 和账户存储树。在这个结构中，状态 Trie 的叶节点包含每个账户的数据，如 nonce、余额、codeHash 和存储树的根（StorageRoot）。这种树包含另一棵树的结构被称为 2 层结构（树中的树）。2 层结构存在以下问题：
1. 复杂性
2. 不平衡
3. 难以理解状态过期等机制之间的交互
由于树包含另一棵树，因此需要额外的处理。同样，当尝试访问不是存储的账户头项目（即 nonce、余额、code）时，需要在各个领域进行复杂的处理，如数据库读取/写入、Merkle 证明构建、Merkle 证明验证、同步和缓存。此外，虽然世界状态 Trie 只包含存储根，但实际上这表示了大量数据，使得这种不平衡在状态同步协议中成为一个重要的麻烦。
状态树 和 存储树（来源: cryptoauxiliary)
例如，在现有状态树中，映射到账户 0x58…ae84 的键的数据将包括 nonce、余额、storageRoot 和 codeHash。这里，storageRoot 只包含一个根值，而不是实际数据。要访问存储槽，需要使用账户 0x58…ae84 和存储槽作为键来读取存储树（账户存储 Trie）中的值。如果存储树已更新，则保存它的状态树中的 storageRoot 值将根据更改的树内容进行更新。因此，2 层结构需要单独的逻辑来处理账户级别和存储槽级别的操作，并且在旨在实现无状态性的状态到期中也会出现类似的问题。由于这些效率低下的问题，Vitalik 提出了 单层结构。
单层结构（来源: 以太坊 Reddit)
这种结构将数据映射到状态中的一个 32 字节单一键，从而产生单一的键值结构。这意味着可以使用相同的键结构访问 nonce、余额以及存储槽。
例如 (地址, 存储槽), (地址, NONCE), (地址, 余额) ..
因此，每个账户的存储位于状态树的另一部分，而不是作为状态树内的子树，消除了树中的树结构。对于单层结构，共享键的前 31 字节的值包含在同一底层承诺中。这可以节省用于验证许多头字段、代码块或相邻存储槽的见证所需的空间。Verkle Trie 使用 Tree Key 来表示这一点，并节省见证空间。
树键
树键的结构（来源: 以太坊基金会 YouTube)
Verkle Trie 的树键是 32 字节，由 31 字节的主干和 1 字节的后缀组成。后缀允许区分由树键存储的状态信息（账户头数据、代码、存储）。
树键生成函数的参数（来源: Verkle Tree EIP)
基于后缀值的解释（来源: Verkle Block Sample)
在上述上下文中，*_LEAF_KEY 表示树键的后缀，*_OFFSET 表示 32 字节（256 位）内子节点的位置。例如，如果树键的最后 1 字节是 00，则表示账户版本；01 表示账户余额；02 表示账户 nonce。先前在状态树中保存的 nonce 和余额是根据提到的偏移值存储的树键。这段代码介绍了在 Verkle Trie EIP 中展示的树键生成函数。
def get_tree_key(address: Address32, tree_index: int, sub_index: int):
# 假设 VERKLE_NODE_WIDTH = 256
return (
pedersen_hash(address + tree_index.to_bytes(32, 'little'))[:31] +
bytes([sub_index])
)这个解释介绍了在 Verkle Trie EIP 中展示的树键生成函数。
def get_tree_key_for_version(address: Address32):
return get_tree_key(address, 0, VERSION_LEAF_KEY)
def get_tree_key_for_balance(address: Address32):
return get_tree_key(address, 0, BALANCE_LEAF_KEY)
def get_tree_key_for_nonce(address: Address32):
return get_tree_key(address, 0, NONCE_LEAF_KEY)
# 为 EXTCODEHASH 的向后兼容性
def get_tree_key_for_code_keccak(address: Address32):
return get_tree_key(address, 0, CODE_KECCAK_LEAF_KEY)
# 为 EXTCODESIZE 的向后兼容性
def get_tree_key_for_code_size(address: Address32):
return get_tree_key(address, 0, CODE_SIZE_LEAF_KEY)用 *_LEAF_KEY 值作为后缀生成 nonce 和 balance 的键。
def get_tree_key_for_code_chunk(address: Address32, chunk_id: int):
return get_tree_key(
address,
(CODE_OFFSET + chunk_id) // VERKLE_NODE_WIDTH,
(CODE_OFFSET + chunk_id) % VERKLE_NODE_WIDTH
)
def get_tree_key_for_storage_slot(address: Address32, storage_key: int):
if storage_key < (CODE_OFFSET - HEADER_STORAGE_OFFSET):
pos = HEADER_STORAGE_OFFSET + storage_key
else:
pos = MAIN_STORAGE_OFFSET + storage_key
return get_tree_key(
address,
pos // VERKLE_NODE_WIDTH,
pos % VERKLE_NODE_WIDTH
)另一方面，代码哈希和存储是基于偏移量生成的，其中 VERKLE_NODE_WIDTH 为 256，表示树的子节点大小。与 MPT 不同，MPT 有 16 个子节点，而 Verkle Trie 有 256 个子节点。
让我们看一些树键的示例。
树键（来源：verkle block sample）
这些树键属于一个账户，显示不同的后缀。每个树键持有不同的值，存储的值与后缀指示的内容相对应。树键下存储的数据也是以 32 字节表示。
例如，如果键是为地址 0x71562b71999873DB5b286dF957af199Ec94617f7 生成的，那么该地址的余额将存储在 0x274cde18dd9dbb04caf16ad5ee969c19fe6ca764d5688b5e1d419f4ac6cd1601 下。
如果在 128256（0x800xff）范围内没有带有后缀的树键，这表示它是一个外部拥有账户（EOA）。
树键（来源：verkle block sample）
对于提到的树键，你可以看到它们的后缀在 0x80~0xff 范围内。因此，可以理解拥有这些树键的地址是一个合约账户（CA）。合约拥有的余额和代码存储在数据区域中，根据后缀存储在树键下。
树键和 vekle 树（来源：ethereum foundation youtube）
如描述所示，仅具有树键就可以直接访问叶节点（=后缀节点）。这意味着具有相同树干的树键的数据都汇聚到同一个叶节点，并且这些数据存储在后缀的一个承诺下。
Merkle Patricia Tree 结构（来源：Leo Zhang）
这与原始 Merkle Patricia Tree 相反，Merkle Patricia Tree 中每个叶节点仅存储一个数据。在 Verkle Trie 中，叶节点更类似于分支节点，而不是 MPT 的叶节点。
内部节点和后缀节点（扩展节点）
Verkle Trie 由两种类型的节点组成：内部节点和后缀节点。
verkle 树结构（来源：ethereum foundation blog）
虚线框表示叶节点，即后缀节点。使用向量承诺允许从原始的 16 个子节点扩展到 256 个子节点。
后缀节点
叶节点（=后缀节点，为便于理解而称为叶节点）包含一个承诺，结构如下：
叶节点结构（来源：Verkle Tree Dev）
- 1： 后缀节点的标记，在椭圆曲线上为 1，但并不是字面上的数字 1。
- 干： 干指的是树键中的干。
- C1、C2： 是 Pedersen 承诺。
最终，包含这四个值的承诺值作为叶节点中的承诺。那么，数据的承诺采取什么形式呢？
C1、C2 结构（来源：Verkle Tree Dev）
共享相同干的值汇聚到一个叶节点。通过干到达的叶节点包含不同后缀的数据，其中 Pedersen 承诺 C1 用于后缀 00 ~ 7F 的数据，Pedersen 承诺 C2 用于后缀 80 ~ ff 的数据。换句话说，账户版本、余额、nonce…代码哈希存储在 C1 中，其余数据存储在 C2 中。这种划分的原因是 Pedersen 承诺的创建受限于最多 253 位大小的 256 个值的承诺，对于 256 位值，会发生数据丢失。
在树键下存储 32 字节数据时，进行以下过程（此描述基于 Verkle Trie 的 Go 实现 ）：
- 根据后缀，数据变为 v0、v1… v255。如果后缀是 20，则该值位于 v32。
- 计算叶节点的承诺 C1 和 C2。这里，v0v127 包含在 C1 中，v128v255 包含在 C2 中。
- 对于 C1，将 v0~v127 的每个 32 字节值分为上 16 字节（v1,0）和下 16 字节（v1, 1）作为多项式中的系数。这允许从 128 个数据中创建一个 256 度多项式，其中每个系数的数据为 16 字节（128 位）。C2 也类似构建。
- 计算 256 度多项式的承诺以计算 C1 = commit([(v0,0), (v0,1), (v1,0), (v1,1)…(v127,0),(v127,1)]) 和 C2 = commit([(v128,0), (v128,1), (v129,0), (v129,1) … (v255,0),(v255,1)])。由于每个系数是来自 256 个数据的 128 位数据，因此不会发生数据丢失。
- C1、C2、1 和干值被承诺以计算 Cc = commit([1, 干, C1, C2])。这个 C 成为叶节点的承诺。
因此，每个节点的承诺包括其子节点，类似于 Merkle 树中的哈希。
内部节点
内部节点保存树键的干值，并存储 256 个指向子节点的指针。简单来说，它表示基于干从根到叶节点的路径。这类似于 MPT 中的分支节点。
内部节点结构（来源：verkle tree dev）在这个插图中，C0、C1 … C255 代表子节点的承诺，内部节点包含这些承诺。 让我们通过查看向 Verkle Trie 插入树键值对时内部节点的变化来了解内部节点和 Verkle Trie 的结构。
- 树键：0x00..20 [插入空]
参考 go-verkle 实现
由于没有路径为“00”的节点，插入空会在根节点“00”下直接创建一个叶节点。由于后缀是 20，该值包含在叶节点的 C1 中。
- 树键：0xdefe…64 [插入空]
参考 go-verkle 实现
在插入第 3 个树键之前，类似于情况 1，“de”处于空状态，因此在根节点“de”下创建了一个叶节点。
- 树键：0xde03a8..02 [插入叶节点]
参考 go-verkle 实现
在第 3 次插入时，“de”处已经有一个叶节点。在这种情况下，会插入新的内部节点，直到出现与现有叶节点树键不同的路径。插入的内部节点保存指向子节点的指针。之前存在的第 2 个节点存储在“fe”处，第 3 个节点存储在“03”处。
- 树键：0xde03a8..02 [插入内部节点]
参考 go-verkle 实现
类似地，在第 4 次插入时，由于在情况 3 中在“de”处插入了新的内部节点，因此在“de”处放置了一个内部节点。插入位置移动到子节点（在情况 3 中插入的新内部节点），路径变为“03”。由于叶节点位于“03”，内部节点会被插入，直到出现不同的路径，如情况 3 所述。插入了第 1、第 2、第 3 和第 4 个树键值后的 Verkle Trie 最终具有上述结构。
通过插入树键的过程，我们探讨了内部节点的作用、Verkle Trie 的结构以及叶节点的形式。如果将示例值插入 Verkle Trie，则如下所示：
Verkle Trie 结构（来源：Verkle Block Sample）
在插图中，I 代表内部节点，L 代表叶节点，C 代表承诺。总结：
- Verkle Trie 由两种类型的节点组成：叶节点和内部节点。
- 树键包含干和后缀。
- 相同的干对应于相同的叶节点。
- 数据通过树键的后缀进行区分存储。
- 树键沿着从根到叶节点的路径逐字节编码。
- 数据包含在叶节点的承诺中。
Merkle Tree（MPT）与 Verkle Trie 对比
在开始之前，本文重点关注 Verkle Trie，因此我们将跳过对 Merkle Tree 的详细解释。
相似之处
- 数据元素以键值对的形式存储。
- 键通过从根到包含值的节点的路径逐字节编码。
- 每个节点都有一个密码承诺，承诺了子节点的值和位置。
- 节点的位置和密码承诺仅取决于数据的内容，而不取决于数据创建和更新的顺序。
如果你熟悉 Merkle Tree 的结构，并且已经理解了上述 Verkle Trie 的树键、内部节点和叶节点，那么应该很容易理解这两种树结构之间的相似之处。
不同之处
- Merkle Tree 具有嵌套的树结构（trie-inside-trie），而 Verkle Trie 具有单个扁平的树结构。
- Verkle Trie 使用 Pedersen 承诺生成密码承诺，而不是 Merkle Tree 中使用的 keccak256 哈希函数。
- Merkle Tree 使用 20 字节键，而 Verkle Trie 使用 32 字节键。
- Merkle Tree 有 16 个子节点，而 Verkle Trie 有 256 个子节点。
Pedersen 承诺基于多项式，并使用在特定位置的评估生成证明和承诺，消除了兄弟节点的需求，并且仅由特定值唯一确定（有关更多详细信息，请参见 IPA）。这使得在树的宽度增加时保持恒定的证明大小成为可能，解决了以太坊在过渡到无状态客户端模型时面临的一个主要问题：见证的大小问题。
- 翻译
- 学分: 3
- 分类: 以太坊
- 标签: verkle 树 Pedersen承诺 无状态性
