「哈希表」状态根最终篇:一文读懂MPT的实施 | 三分钟入门Neo3

原创 胭脂  |  文章来源:币圈达人发布时间:2020-05-24 01:48  阅读 131 次 评论 0 条
众人帮 趣闲赚 牛帮
摘要:

在上一篇「三分钟入门Neo3」文章中,我们介绍了 Patricia树、Merkle树 以及如何将 Merkle证明 用于轻量级的交易验证。作为状态根系列的最后一篇文章,将结合前面两篇关于Patricia树 与 Merkle树 的文章来介绍

在上一篇「三分钟入门Neo3」文章中,我们介绍了 Patricia树、Merkle树 以及如何将 Merkle证明 用于轻量级的交易验证。

作为状态根系列的最后一篇文章,将结合前面两篇关于Patricia树 与 Merkle树 的文章来介绍 Merkle Patricia Trie(MPT)。理解 MPT 的实施逻辑有助于更好地理解 Neo3 的数据存储。

节点存储

Neo 网络上的每个节点都会处理区块内的数据,并按顺序读取并执行每笔交易。有些交易是只读模式,例如查询特定资产的总量,但有些则需要修改节点的存储区。例如,从一个地址向另一个地址进行转账,将修改这两个地址的资产余额。

节点以键值对的形式存储数据。键可以认为是与特定数据段相对应的名称或者唯一标识符,例如智能合约的名称或者特定地址的资产余额信息。

更改特定的值,需要使用键信息。由于每个节点都以完全相同的顺序处理每一笔交易,因此每个节点应该有相同的键和值数据,从而共享相同的状态。

使用 MPT树 的数据结构,可以验证节点是否共享了相同状态。如先前文章所述,Patricia树 是一种可以以任意共享前缀来组织键数据的数据结构,Merkle树 则提供了可用于验证状态的整个结构的加密指纹。

MPT树

下图我们提供了一个简化的 MPT树,其中存储了3个键值对,可以将此树看作节点存储的快照。通过该图,我们将说明 3 笔余额数据是如何存储的。

在树的顶部有一个包含 键b3 的节点,b3 是 b31d4、b38a2 和 b3d6f 这三个键的共享前缀。如果有其他以 b3 作为前缀的键,它们都会存储在该节点的子树中。

为了获取每个键的值,可以像操作 Patricia树 那样向下继续查找。下一个节点 n2 内提供了 16 个可选择的分支,每个分支对应着十六进制数据(0-9,a-f)中的其中一个。例如,如果我们想查找与键 b38a2 相对应的值,则可以从 8 开始向下查找并到达节点 n4。在该图中,该节点存储了键的最后一部分值 a2,并指向了最终存储的值:13.12GAS。

相反,正如前文所述的 Merkle树 操作那样,我们也可以从存储的值开始沿着树向上查找 Merkle 的根节点。要查找 n3、n4 和 n5 节点的哈希值,首先需要获取每个值的哈希。我们可以将这些节点和它们的哈希值一起进行哈希处理,从而确定 n2 节点的哈希值。根据 n2 的哈希可以进一步确定 n1 的哈希,即 Merkle 的根节点哈希。

如果网络上的所有节点都存储着完全相同的数据,即也共同享有相同的 Merkle 根节点。相反,如果有一个节点存储了不同的数据,比如某个键的值不正确,那么哈希计算后将会生成完全不同的 Merkle 根节点。这就能很容易地验证节点是否与共识节点具有一致的状态。

MPT的实施

目前 NGD 开发工程师张涛正在实施 Neo 的 MPT 功能。结构中使用了 4 种主要的节点类型:

1. 分支节点:具有 16 个分支,每个分支分别对应 十六 进制数 00~0F,最后再加上一个值(n2)

2. 扩展节点:包含键以及指向下一个节点的指针(n1、n3、n4)

3. 叶子节点:存储了键对应的值(v1、v2、v3)

4. 哈希节点:存储了特定节点的哈希。这主要是为了提高效率,因为许多存储的值并不会立即被查询,因此不需要存储特定节点的完整数据。

如果以后需要这些数据,我们可以使用状态根以及 Merkle 证明来确定正确的值,正如张涛解释地那样:

“当我们想要存储一个节点,如 n1 节点,n2 可以表示为一个哈希节点。因此在数据库中,键是 n1 的哈希,值是 n1 的键部分加上 n2 的哈希。因此我们可以使用数据库和状态根哈希来逐步构建所需的整棵树结构。”

MPT 作为存储区块数据的关键数据结构,也提供了新的应用场景,例如通过检查点来简化轻节点的本地计算,并确保节点存储的可审计和可信任,这也是目前普通终端用户和企业应用程序都需要的。

实施 MPT 及其他所需组件后,Neo 网络上的全节点和轻节点都将提供强大的存储一致性保证。

「状态根」系列已正式完结。下一篇「三分钟入门Neo3」将进入「区块同步」系列,介绍旨在优化网络效率的一些尝试。

历史上的今天:

本文地址:https://www.u5881.com/7585.html
版权声明:本站推荐的部分活动具有时效性,老淘本人并不能保证当您看到本文时,该项活动是否仍在继续。

发表评论


表情