Press "Enter" to skip to content

以太坊提案 Verkle 树结构

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

 

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

 

感谢 Kevaundray Wedderburn 对帖子的反馈。

 

概述

 

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

Dankrad 的博客
Vitalik 的博客
从 Verkle 窥视 EIP

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

 

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

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

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

 

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

 

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

 

verkle 树的布局

 

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

 

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ᵢ∈ ₃₂$ 变成 ${v^{(lower)}}_i ∈ ₁₆$ 和 ${v^{(upper)}}_i∈ ₁₆$ , ${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⁰₀$ 有相同的值。

 

更浅的树,更简单的证明

 

verkle 树结构让树更浅,从而减少了存储的数据量。然而,它的关键特性是其产生更小的证明的能力。这将在下一篇文章中解释。

 

原文链接: https://blog.ethereum.org/2021/12/02/verkle-tree-structure/ 本文由Guillaume Ballet和Dankrad Feist于2021年12月2日发布

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注