{"content":{"title":"以太坊无状态系列 #4 : 探索 Verkle Trie 结构","body":">- 原文链接：https://medium.com/@chaisomsri96/statelessness-series-part4-exploring-the-verkle-trie-structure-d97a8c85363e\r\n>- 译者：[AI翻译官](https://learnblockchain.cn/people/19584)，校对：[翻译小组](https://learnblockchain.cn/people/412)\r\n>- 本文永久链接：[learnblockchain.cn/article…](https://learnblockchain.cn/article/8588)\r\n    \r\nVerkle Trie 是引入无状态性的关键变化之一，以太坊基金会一直在继续开发和研究 Verkle Trie，以取代当前用于状态存储的 MPT（Merkle Patricia Trie）。[Verkle Trie 文档](https://verkle.dev/docs/intro) 最近已更新，目前 Verkle Trie 的实现可以在 ([Python](https://github.com/crate-crypto/verkle-trie-ref), [Go](https://github.com/ethereum/go-verkle), [Rust](https://github.com/crate-crypto/rust-verkle)) 中找到。在验证 Verkle Trie 后，本文将重点关注 Verkle Trie 的结构，以提供详细的理解。\r\n\r\n## 什么是 Verkle Trie?\r\n\r\nVerkle Trie 是向量和 Merkle 树的结合，使用向量承诺而不是传统 Merkle 树中的 keccak256 哈希函数。Verkle Trie 中使用的向量承诺（VC）方案基于 Pedersen 承诺（也称为 Pedersen 哈希），这是基于多项式承诺的。\r\n\r\n承诺的使用消除了生成证明所需的兄弟节点，由于它基于椭圆曲线，可以执行操作。这允许在树的每个级别添加所需的证明（ [多证明](https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html) ），从而减少证明的大小。一个恒定大小的证明可以包含在区块头中，实现弱状态无状态性。\r\n\r\n![Image 1](https://img.learnblockchain.cn/attachments/migrate/1719990834925)\r\n\r\n(来源: [SalomonCrypto](https://typefully.com/SalomonCrypto/verkle-trees-xsrSRdO))\r\n\r\n## Verkle Trie 结构\r\n\r\n![Image 2](https://img.learnblockchain.cn/attachments/migrate/1719990835188)\r\n\r\n![Image 3](https://img.learnblockchain.cn/attachments/migrate/1719990835120)\r\n\r\n> 2 层结构（来源: [以太坊黄皮书](https://www.lucassaldanha.com/ethereum-yellow-paper-walkthrough-2/), [以太坊 Reddit](https://www.reddit.com/r/ethereum/comments/nve036/ethmag_proposed_scheme_for_encoding_ethereum/))\r\n\r\n以太坊总共有四棵树：世界状态树(Trie)、收据树、交易树 和账户存储树。在这个结构中，状态 Trie 的叶节点包含每个账户的数据，如 nonce、余额、codeHash 和存储树的根（StorageRoot）。这种树包含另一棵树的结构被称为 **2 层结构（树中的树）**。2 层结构存在以下问题：\r\n\r\n> 1\\. 复杂性\r\n> \r\n> 2\\. 不平衡\r\n> \r\n> 3\\. 难以理解状态过期等机制之间的交互\r\n\r\n由于树包含另一棵树，因此需要额外的处理。同样，当尝试访问不是存储的账户头项目（即 nonce、余额、code）时，需要在各个领域进行复杂的处理，如数据库读取/写入、Merkle 证明构建、Merkle 证明验证、同步和缓存。此外，虽然世界状态 Trie 只包含存储根，但实际上这表示了大量数据，使得这种不平衡在状态同步协议中成为一个重要的麻烦。\r\n\r\n![状态树 和 存储树](https://img.learnblockchain.cn/attachments/migrate/1719990835210)\r\n\r\n>  状态树 和 存储树（来源: [cryptoauxiliary](https://www.cryptoauxiliary.com/post/smart-contract-storage-for-ethereum))\r\n\r\n例如，在现有状态树中，映射到账户 0x58…ae84 的键的数据将包括 nonce、余额、storageRoot 和 codeHash。这里，storageRoot 只包含一个根值，而不是实际数据。要访问存储槽，需要使用账户 0x58…ae84 和存储槽作为键来读取存储树（账户存储 Trie）中的值。如果存储树已更新，则保存它的状态树中的 storageRoot 值将根据更改的树内容进行更新。因此，2 层结构需要单独的逻辑来处理账户级别和存储槽级别的操作，并且在旨在实现无状态性的状态到期中也会出现类似的问题。由于这些效率低下的问题，Vitalik 提出了 [**单层结构**](https://www.reddit.com/r/ethereum/comments/nve036/ethmag_proposed_scheme_for_encoding_ethereum/)。\r\n\r\n![Image 5](https://img.learnblockchain.cn/attachments/migrate/1719990835175)\r\n\r\n> 单层结构（来源: [以太坊 Reddit](https://www.reddit.com/r/ethereum/comments/nve036/ethmag_proposed_scheme_for_encoding_ethereum/))\r\n\r\n这种结构将数据映射到状态中的一个 32 字节单一键，从而产生单一的键值结构。这意味着可以使用相同的键结构访问 nonce、余额以及存储槽。\r\n\r\n例如 `(地址, 存储槽)`, `(地址, NONCE)`, `(地址, 余额)` ..\r\n\r\n因此，每个账户的存储位于状态树的另一部分，而不是作为状态树内的子树，消除了树中的树结构。对于单层结构，**共享键的前 31 字节的值包含在同一底层承诺中**。这可以节省用于验证许多头字段、代码块或相邻存储槽的见证所需的空间。Verkle Trie 使用 **Tree Key** 来表示这一点，并节省见证空间。\r\n\r\n## 树键\r\n\r\n![Image 6](https://img.learnblockchain.cn/attachments/migrate/1719990836662)\r\n\r\n>  树键的结构（来源: [以太坊基金会 YouTube](https://youtu.be/RGJOQHzg3UQ))\r\n\r\nVerkle Trie 的树键是 32 字节，**由 31 字节的主干和 1 字节的后缀组成**。**后缀允许区分由树键存储的状态信息（账户头数据、代码、存储）**。\r\n\r\n![Image 7](https://img.learnblockchain.cn/attachments/migrate/1719990836767)\r\n\r\n树键生成函数的参数（来源: [Verkle Tree EIP](https://notes.ethereum.org/@vbuterin/verkle_tree_eip))\r\n\r\n![Image 8](https://img.learnblockchain.cn/attachments/migrate/1719990836992)\r\n\r\n基于后缀值的解释（来源: [Verkle Block Sample](https://github.com/gballet/verkle-block-sample))\r\n\r\n在上述上下文中，\\*\\_LEAF_KEY 表示树键的后缀，\\*\\_OFFSET 表示 32 字节（256 位）内子节点的位置。例如，如果树键的最后 1 字节是 00，则表示账户版本；01 表示账户余额；02 表示账户 nonce。先前在状态树中保存的 nonce 和余额是根据提到的偏移值存储的树键。这段代码介绍了在 [Verkle Trie EIP](https://notes.ethereum.org/@vbuterin/verkle_tree_eip) 中展示的树键生成函数。\r\n\r\n```python\r\ndef get_tree_key(address: Address32, tree_index: int, sub_index: int):  \r\n\r\n# 假设 VERKLE_NODE_WIDTH = 256\r\n    return (  \r\n        pedersen_hash(address + tree_index.to_bytes(32, 'little'))[:31] +  \r\n        bytes([sub_index])  \r\n    )\r\n```\r\n\r\n\r\n\r\n这个解释介绍了在 [Verkle Trie EIP](https://notes.ethereum.org/@vbuterin/verkle_tree_eip) 中展示的树键生成函数。\r\n\r\n```python\r\ndef get_tree_key_for_version(address: Address32):  \r\n    return get_tree_key(address, 0, VERSION_LEAF_KEY)\r\n    \r\ndef get_tree_key_for_balance(address: Address32):  \r\n    return get_tree_key(address, 0, BALANCE_LEAF_KEY)\r\n\r\ndef get_tree_key_for_nonce(address: Address32):  \r\n    return get_tree_key(address, 0, NONCE_LEAF_KEY)\r\n    \r\n# 为 EXTCODEHASH 的向后兼容性  \r\ndef get_tree_key_for_code_keccak(address: Address32):  \r\n    return get_tree_key(address, 0, CODE_KECCAK_LEAF_KEY)\r\n  \r\n# 为 EXTCODESIZE 的向后兼容性\r\n\r\ndef get_tree_key_for_code_size(address: Address32):  \r\n    return get_tree_key(address, 0, CODE_SIZE_LEAF_KEY)\r\n```\r\n\r\n\r\n\r\n用 \\*_LEAF_KEY 值作为后缀生成 nonce 和 balance 的键。\r\n\r\n```python\r\ndef get_tree_key_for_code_chunk(address: Address32, chunk_id: int):  \r\n    return get_tree_key(  \r\n        address,  \r\n        (CODE_OFFSET + chunk_id) // VERKLE_NODE_WIDTH,  \r\n        (CODE_OFFSET + chunk_id)  % VERKLE_NODE_WIDTH  \r\n    )\r\n\r\ndef get_tree_key_for_storage_slot(address: Address32, storage_key: int):  \r\n    if storage_key < (CODE_OFFSET - HEADER_STORAGE_OFFSET):  \r\n        pos = HEADER_STORAGE_OFFSET + storage_key  \r\n    else:  \r\n        pos = MAIN_STORAGE_OFFSET + storage_key  \r\n    return get_tree_key(  \r\n        address,  \r\n        pos // VERKLE_NODE_WIDTH,  \r\n        pos % VERKLE_NODE_WIDTH  \r\n    )\r\n```\r\n\r\n\r\n\r\n另一方面，代码哈希和存储是基于偏移量生成的，其中 VERKLE_NODE_WIDTH 为 256，表示树的子节点大小。与 MPT 不同，MPT 有 16 个子节点，而 Verkle Trie 有 256 个子节点。\r\n\r\n让我们看一些树键的示例。\r\n\r\n![Image 9](https://img.learnblockchain.cn/attachments/migrate/1719990837694)\r\n\r\n> 树键（来源：[verkle block sample](https://github.com/gballet/verkle-block-sample)）\r\n\r\n这些树键属于一个账户，显示不同的后缀。每个树键持有不同的值，存储的值与后缀指示的内容相对应。树键下存储的数据也是以 32 字节表示。\r\n\r\n例如，如果键是为地址 0x71562b71999873DB5b286dF957af199Ec94617f7 生成的，那么该地址的余额将存储在 0x274cde18dd9dbb04caf16ad5ee969c19fe6ca764d5688b5e1d419f4ac6cd1601 下。\r\n\r\n如果在 128256（0x800xff）范围内没有带有后缀的树键，这表示它是一个外部拥有账户（EOA）。\r\n\r\n![Image 10](https://img.learnblockchain.cn/attachments/migrate/1719990837877)\r\n\r\n树键（来源：[verkle block sample](https://github.com/gballet/verkle-block-sample)）\r\n\r\n对于提到的树键，你可以看到它们的后缀在 0x80~0xff 范围内。因此，可以理解拥有这些树键的地址是一个合约账户（CA）。合约拥有的余额和代码存储在数据区域中，根据后缀存储在树键下。\r\n\r\n![vekle ](https://img.learnblockchain.cn/attachments/migrate/1719990838216)\r\n\r\n> 树键和 vekle 树（来源：[ethereum foundation youtube](https://youtu.be/RGJOQHzg3UQ)）\r\n\r\n如描述所示，仅具有树键就可以直接访问叶节点（=后缀节点）。这意味着具有相同树干的树键的数据都汇聚到同一个叶节点，并且这些数据存储在后缀的一个承诺下。\r\n\r\n![Merkle Patricia Tree 结构](https://img.learnblockchain.cn/attachments/migrate/1719990838567)\r\n\r\n> Merkle Patricia Tree 结构（来源：[Leo Zhang](https://medium.com/@chiqing/merkle-patricia-trie-explained-ae3ac6a7e123)）\r\n\r\n这与原始 Merkle Patricia Tree 相反，Merkle Patricia Tree 中每个叶节点仅存储一个数据。在 Verkle Trie 中，叶节点更类似于分支节点，而不是 MPT 的叶节点。\r\n\r\n内部节点和后缀节点（扩展节点）\r\n----------------------------------------\r\n\r\nVerkle Trie 由两种类型的节点组成：内部节点和后缀节点。\r\n\r\n![verkle 树结构](https://img.learnblockchain.cn/attachments/migrate/1719990838874)\r\n\r\n> verkle 树结构（来源：[ethereum foundation blog](https://blog.ethereum.org/2021/12/02/verkle-tree-structure)）\r\n\r\n虚线框表示叶节点，即后缀节点。使用向量承诺允许**从原始的 16 个子节点扩展到 256 个子节点**。\r\n\r\n**_后缀节点_**\r\n\r\n叶节点（=后缀节点，为便于理解而称为叶节点）包含一个承诺，结构如下：\r\n\r\n![Verkle 叶节点](https://img.learnblockchain.cn/attachments/migrate/1719990839542)\r\n\r\n叶节点结构（来源：[Verkle Tree Dev](https://verkle.dev/docs/implementation/verkle%20trie%20structure)）\r\n\r\n*   **1：** 后缀节点的标记，在椭圆曲线上为 1，但并不是字面上的数字 1。\r\n*   **干：** 干指的是树键中的干。\r\n*   **C1、C2：** 是 Pedersen 承诺。\r\n\r\n![Image 15](https://img.learnblockchain.cn/attachments/migrate/1719990839710)\r\n\r\n（来源：[ethereum foundation blog](https://blog.ethereum.org/2021/12/02/verkle-tree-structure)）\r\n\r\n最终，包含这四个值的承诺值作为叶节点中的承诺。那么，数据的承诺采取什么形式呢？\r\n\r\n![Image 16](https://img.learnblockchain.cn/attachments/migrate/1719990839845)\r\n\r\n> C1、C2 结构（来源：[Verkle Tree Dev](https://verkle.dev/docs/implementation/verkle%20trie%20structure)）\r\n\r\n共享相同干的值汇聚到一个叶节点。通过干到达的叶节点包含不同后缀的数据，其中 Pedersen 承诺 C1 用于后缀 00 ~ 7F 的数据，Pedersen 承诺 C2 用于后缀 80 ~ ff 的数据。换句话说，账户版本、余额、nonce…代码哈希存储在 C1 中，其余数据存储在 C2 中。这种划分的原因是 Pedersen 承诺的创建受限于最多 253 位大小的 256 个值的承诺，对于 256 位值，会发生数据丢失。\r\n\r\n在树键下存储 32 字节数据时，进行以下过程（此描述基于 [Verkle Trie 的 Go 实现](https://github.com/ethereum/go-verkle) ）：\r\n\r\n1.  根据后缀，数据变为 v0、v1… v255。如果后缀是 20，则该值位于 v32。\r\n2.  计算叶节点的承诺 C1 和 C2。这里，v0v127 包含在 C1 中，v128v255 包含在 C2 中。\r\n3.  对于 C1，将 v0~v127 的每个 32 字节值分为上 16 字节（v1,0）和下 16 字节（v1, 1）作为多项式中的系数。这允许从 128 个数据中创建一个 256 度多项式，其中每个系数的数据为 16 字节（128 位）。C2 也类似构建。\r\n4.  计算 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 位数据，因此不会发生数据丢失。\r\n5.  C1、C2、1 和干值被承诺以计算 Cc = commit([1, 干, C1, C2])。这个 C 成为叶节点的承诺。\r\n\r\n因此，每个节点的承诺包括其子节点，类似于 Merkle 树中的哈希。\r\n\r\n**内部节点**\r\n\r\n内部节点保存树键的干值，并存储 256 个指向子节点的指针。简单来说，**它表示基于干从根到叶节点的路径**。这类似于 MPT 中的分支节点。\r\n\r\n![Image 17](https://img.learnblockchain.cn/attachments/migrate/1719990839971)\r\n\r\n内部节点结构（来源：[verkle tree dev](https://verkle.dev/docs/implementation/verkle%20trie%20structure)）**在这个插图中，C0、C1 … C255 代表子节点的承诺，内部节点包含这些承诺。** 让我们通过查看向 Verkle Trie 插入树键值对时内部节点的变化来了解内部节点和 Verkle Trie 的结构。\r\n\r\n1.  树键：0x00..20 [插入空]\r\n\r\n![Image 18](https://img.learnblockchain.cn/attachments/migrate/1719990840097)\r\n\r\n参考 [go-verkle 实现](https://github.com/ethereum/go-verkle)\r\n\r\n由于没有路径为“00”的节点，插入空会在根节点“00”下直接创建一个叶节点。由于后缀是 20，该值包含在叶节点的 C1 中。\r\n\r\n2.  树键：0xdefe…64 [插入空]\r\n\r\n![Image 19](https://img.learnblockchain.cn/attachments/migrate/1719990840422)\r\n\r\n参考 [go-verkle 实现](https://github.com/ethereum/go-verkle)\r\n\r\n在插入第 3 个树键之前，类似于情况 1，“de”处于空状态，因此在根节点“de”下创建了一个叶节点。\r\n\r\n3.  树键：0xde03a8..02 [插入叶节点]\r\n\r\n![Image 20](https://img.learnblockchain.cn/attachments/migrate/1719990840858)\r\n\r\n参考 [go-verkle 实现](https://github.com/ethereum/go-verkle)\r\n\r\n在第 3 次插入时，“de”处已经有一个叶节点。**在这种情况下，会插入新的内部节点，直到出现与现有叶节点树键不同的路径。插入的内部节点保存指向子节点的指针**。之前存在的第 2 个节点存储在“fe”处，第 3 个节点存储在“03”处。\r\n\r\n4.  树键：0xde03a8..02 [插入内部节点]\r\n\r\n![Image 21](https://img.learnblockchain.cn/attachments/migrate/1719990840989)\r\n\r\n参考 [go-verkle 实现](https://github.com/ethereum/go-verkle)\r\n\r\n类似地，在第 4 次插入时，由于在情况 3 中在“de”处插入了新的内部节点，因此在“de”处放置了一个内部节点。插入位置移动到子节点（在情况 3 中插入的新内部节点），路径变为“03”。由于叶节点位于“03”，内部节点会被插入，直到出现不同的路径，如情况 3 所述。插入了第 1、第 2、第 3 和第 4 个树键值后的 Verkle Trie 最终具有上述结构。\r\n\r\n通过插入树键的过程，我们探讨了内部节点的作用、Verkle Trie 的结构以及叶节点的形式。如果将示例值插入 Verkle Trie，则如下所示：\r\n\r\n\r\n\r\n![](https://img.learnblockchain.cn/attachments/migrate/1719992932719)\r\n\r\n\r\n\r\n> Verkle Trie 结构（来源：[Verkle Block Sample](https://github.com/gballet/verkle-block-sample)）\r\n\r\n在插图中，I 代表内部节点，L 代表叶节点，C 代表承诺。总结：\r\n\r\n*   Verkle Trie 由两种类型的节点组成：叶节点和内部节点。\r\n*   树键包含干和后缀。\r\n*   相同的干对应于相同的叶节点。\r\n*   数据通过树键的后缀进行区分存储。\r\n*   树键沿着从根到叶节点的路径逐字节编码。\r\n*   数据包含在叶节点的承诺中。\r\n\r\n## Merkle Tree（MPT）与 Verkle Trie 对比\r\n\r\n在开始之前，本文重点关注 Verkle Trie，因此我们将跳过对 Merkle Tree 的详细解释。\r\n\r\n**相似之处**\r\n\r\n*   数据元素以键值对的形式存储。\r\n*   键通过从根到包含值的节点的路径逐字节编码。\r\n*   每个节点都有一个密码承诺，承诺了子节点的值和位置。\r\n*   节点的位置和密码承诺仅取决于数据的内容，而不取决于数据创建和更新的顺序。\r\n\r\n如果你熟悉 Merkle Tree 的结构，并且已经理解了上述 Verkle Trie 的树键、内部节点和叶节点，那么应该很容易理解这两种树结构之间的相似之处。\r\n\r\n**不同之处**\r\n\r\n*   Merkle Tree 具有嵌套的树结构（trie-inside-trie），而 Verkle Trie 具有单个扁平的树结构。\r\n*   Verkle Trie 使用 Pedersen 承诺生成密码承诺，而不是 Merkle Tree 中使用的 keccak256 哈希函数。\r\n*   Merkle Tree 使用 20 字节键，而 Verkle Trie 使用 32 字节键。\r\n*   Merkle Tree 有 16 个子节点，而 Verkle Trie 有 256 个子节点。\r\n\r\n\r\n\r\nPedersen 承诺基于多项式，并使用在特定位置的评估生成证明和承诺，消除了兄弟节点的需求，并且仅由特定值唯一确定（有关更多详细信息，请参见 IPA）。这使得在树的宽度增加时保持恒定的证明大小成为可能，解决了以太坊在过渡到无状态客户端模型时面临的一个主要问题：见证的大小问题。\r\n\r\n> 我是 [AI 翻译官](https://learnblockchain.cn/people/19584)，为大家转译优秀英文文章，如有翻译不通的地方，在[这里](https://github.com/lbc-team/Pioneer/blob/master/translations/8588.md)修改，还请包涵～"},"author":{"user":"https://learnblockchain.cn/people/21103","address":null},"history":null,"timestamp":1719993274,"version":1}