以太坊提案 Verkle 树结构

Tiny熊

发布于 2022-05-25 10:29:57

2.1K0

发布于 2022-05-25 10:29:57

本文作者：黑崎一户[1]

Verkle 树[2](音译为 “沃克尔树”）是一种承诺方案(commitment schme)，其工作方式类似于 Merkle 树[3]，但证据的大小要小得多。用向量承诺替换 Merkle 树中的哈希，这使得广泛的分支因子更高效。

感谢 Kevaundray Wedderburn 对帖子的反馈。

概述

有关 verkle 树如何工作的详细信息，请参阅：

Dankrad 的博客[4]
Vitalik 的博客[5]
从 Verkle 窥视 EIP[6]

本文的目的是，向希望实现 Verkle 树和想要深入研究 EIP 的客户端开发人员，解释 Verkle 树草案 EIP[7] 的具体布局。

Verkle 树对树结构进行了许多改进，其中最重要的是：

从 20 字节密钥切换到 32 字节密钥（不要与 32 字节地址混淆）；
帐户和存储树合并，并且是确定性的；
引入了 verkle 树本身，它使用向量承诺(vector commitments )而不是哈希。

作为 Verkle 树的向量承诺方案，我们使用 _Pedersen 承诺_——基于椭圆曲线。有关 Pedersen 承诺的介绍，以及如何使用内积参数将它们用作多项式或向量承诺，请参阅[8]此处。

我们用的是 Bandersnatch[9]曲线。选择 Bandersnatch 是因为它的高性能，也因为它将来可以让 BLS12_381 中高效的 SNARKs 推出 verkle 树。这对于 rollup 和升级都非常有用，一旦实现，所有证据都可以压缩到一个 SNARK 中，无需进一步的承诺更新。

Bandersnatch 曲线的阶/标量域的大小为p = 13108968793781547619861935127046491459309155893440570251786403306729687672801，这是一个 253 位的素数。因此，我们只能安全地承诺最多 252 位的字符串，否则会溢出。我们为 verkle 树选择分支因子(宽度)为 256，意思是每个承诺最多可以包含 256 个 252 位的值（确切地说，是最大整数为 p - 1 ）。承诺长度为 256 的列表v 写做 Commit(v_0, v_1, ..., v_{255}) 。

verkle 树的布局

Verkle 树 EIP 的设计目标之一是在访问相邻位置（例如存储地址几乎相同或者相邻的代码块）时可以更便宜。为此，密钥由 31 字节的词干和 1 字节的后缀组成，总共 32 个字节。密钥方案的设计让“邻近的”存储位置会映射到相同的词干和不同的后缀。详情请查看 EIP 草案[10]。

verkle 树本身由两种类型的节点组成：

扩展节点，代表 256 个有相同词干不同后缀的值
内部节点，最多有 256 个子节点，可以是其他内部节点或扩展节点。

扩展节点承诺是 4 个元素向量的承诺，剩余的位置将为 0：

C = Commit(1,stem,C_1,C_2)

C_1 和 C_2 是两个进一步的承诺，用于承诺所有与stem相等的词干值。需要两个承诺的原因是密钥有 32 个字节，但每个域元素只能存储 252 位，单个承诺不足以存储 256 位。因此，C_1 存储后缀 0 到 127 位的值，而 C_2 存储 128 到 255 位，值被分成两部分,以适应域的大小（我们稍后会谈到）。

扩展与承诺 C_1 和 C_2 一起被称为“扩展与后缀树”（extension-and-suffix tree 简称 EaS）。

图 1

图 1 是密钥0xfe0002abcd..ff04遍历树的表示: 路径经过 3 个内部节点，每个节点有 256 个子节点 (254, 0, 2)，一个扩展节点表示abcd..ff和两个后缀树承诺，包括04— v₄ 的值。请注意，stem实际上是密钥的前 31 个字节，包括通过内部节点的路径。

叶子节点值承诺

每个 EaS 节点包含 256 个值。因为一个值是 256 位宽，而我们只能将 252 位安全地存储在一个域元素中，如果我们只是简单的将一个值存储在一个域元素中，就会丢失 4 位。

为了规避这个问题，我们将这 256 个值分成两组，每组 128 个值。即每 32 字节值被拆分为两个 16 字节值。所以值 vᵢ∈ 𝔹_{32} 变成 {v^{(lower)}}_i ∈ 𝔹_{16} 和 {v^{(upper)}}_i∈ 𝔹_{16} ， {v^{(lower)}}_i ++ {v^{(upper)}}_i= vᵢ 。

给{v^{(lower)}}_i 添加了“叶子标记”，以区分从未访问过的叶子节点和已被 0 重写的叶子节点。永远不会从 verkle 树中删除任何值。这是之后的状态到期方案所必需的。该标记设置在第 129 位，即如果 vᵢ 在以前访问过，{v^{(lower\ modified)}}_i = {v^{(lower)}}_i + 2^{128} ，如果从未访问过 vᵢ ，则 {v^{(lower\ modified)}}_i = 0 。

然后将两个承诺 C_1 和 C_2 定义为:

C_1=Commit(v_0^{(lower,modified)},v_0^{(upper)},v_1^{(lower,modified)},v_1^{(upper)},...,v_{127}^{(lower,modified)},v_{127}^{(upper)})

C_2=Commit(v_{128}^{(lower,modified)},v_{128}^{(upper)},v_{129}^{(lower,modified)},v_{129}^{(upper)},...,v_{255}^{(lower,modified)},v_{255}^{(upper)})

扩展节点承诺

对扩展节点的承诺由一个“扩展标记”组成，即数字 1、两个子树承诺 C_1 和 C_2 ，以及通向该扩展节点的密钥的词干。

C=Commit(1,stem,C_1,C_2)

与 “默克尔帕特里夏树” (Merkle-Patricia tree)中的扩展节点不同，这里的扩展节点仅包含将父内部节点连接到子内部节点的密钥部分，而词干覆盖了直到顶点的整个密钥。这是因为 Verkle 树在设计时考虑了无状态证明：如果插入一个新密钥将扩展“拆分”为两部分，不需要更新旧的兄弟姐妹，这样可以让证明更小。

内部节点承诺

内部节点的承诺其计算方法更简单：节点被视为 256 个值的向量，每个值也是其 256 个子树的根承诺（的域表示）。空子树的承诺为 0，如果子树不为空，则内部节点的承诺为：

C=Commit(C_0,C_1,...,C_{255})

其中 Cᵢ 是内部节点的子节点，如果子节点为空，则为 0。

向树中插入值

图 2 展示了将新值插入树中的过程，当词干在几个初始字节上发生冲突时，其过程会变得很有趣。

图 2

图 2 将值 v_{192} 插入到 verkle 树中的位置0000010000...0000处，这个树仅在位置0000000000...0000处有值 v_{127} 。因为词干在第三个字节处不同，所以添加了两个内部节点就遇到了不同的字节。然后插入了另一个“EaS”树，具有完整的 31 字节词干。初始节点没有动，C²₀ 与插入前的 C⁰₀ 有相同的值。