「区块链」什么是MPT?Neo3的MPT有何不同?

原创 一夕笙歌  |  文章来源:币圈达人发布时间:2020-05-24 01:59  阅读 126 次 评论 0 条
众人帮 趣闲赚 牛帮
摘要:

今天的文章旨在介绍更多关于Merkle树,Patricia Tries前缀树,生成state root所需的基本组件信息,以及如何将它们用于轻客户端的简单支付验证上。
Neo软件工程师张涛在上篇文章中分享了一个在修订中的提案,并总结了当前正

今天的文章旨在介绍更多关于Merkle树,Patricia Tries前缀树,生成state root所需的基本组件信息,以及如何将它们用于轻客户端的简单支付验证上。

Neo软件工程师张涛在上篇文章中分享了一个在修订中的提案,并总结了当前正在开发的解决方案。根据初始提案的方案1可知,状态将添加到PrepareRequest共识消息中,并将签名作为Commit消息的一部分进行广播。在每一轮共识后,将区块以及state root信息进行转发并由网络上的节点进行解释分析。

张涛还概述了实现该特性所需的步骤,例如对P2P消息进行修改,以及RPC节点需要添加额外的功能用于提供Merkle证明。这些证明是进行简单支付验证(SPV)所必需的,SPV最初由中本聪在比特币白皮书中提出,用于允许轻客户端在不维护整个区块链副本的情况下进行交易验证。

实现State root所需的最重要模型是Merkle Patricia trie(MPT)。在RTN3系列的第一篇介绍state root的文章中,我们简单介绍了MPTs,它是Patricia trie和Merkle树的结合。

Patricia trie

Trie是由分支(边)连接的多个顶点组成的数据结构,每条边都用一个单独的字符进行标记。沿着树的路径可以得到不同的值。基数树是trie的压缩版本;每条边都用字符串而不是单个字符进行标记,字符串则作为后续顶点的公共前缀。

Patricia trie是一种特殊的基数树,又称二叉基数树。顾名思义,在二叉基数树中,每个顶点最多有两条边。这意味着对于任意给定的顶点,最多只有两条路径。具有相同字符的值存储在共同前缀的文档中。

上图的例子说明了基数树的效率。每条边不再只存储单一的字符(这将存在很多只有一个子节点的顶点),而是用部分字符串进行标记。

通过共享前缀对存储数据进行组织,优化了数据结构的存储空间,提高了平均的查找速度。这对于区块链节点而言非常重要,因为节点需要存储并计算大量的数据。

Merkle树

Merkle树是一种以多个数据块开始的数据结构。对块中的值进行哈希处理则可得到树中的第一行顶点。Merkle树的每个后续顶点仍用哈希表示,顶点的哈希值可通过将父顶点的哈希值相加并对相加的结果进行哈希计算所得。

这些哈希最终可计算得到一个公共的顶点,称为Merkle根或者根哈希。Merkle根节点可以被认为是树中数据唯一且加密的指纹。存储值的任意改变都将使得所连接的节点的哈希值发生变化,从而产生不同的指纹。

Neo网络上的所有节点都会计算一个本地的状态,并在每个新块后确定一个state root。通过将该state root与由共识节点签名的state root进行比较,节点即可验证状态与网络其他部分的一致性。

Merkle证明是这些树的一个有趣特性,它提供了一种可用于验证特定键值在树中存在性的机制。当轻客户端从RPC节点请求数据时,数据将附带可说明特定值(如用户的资产余额)在树中存在的Merkle证明。

这意味着轻客户端可以以一种去信任的方式验证来自RPC节点的信息,其中只需要Merkle证明以及从P2P网络接收到的共识节点的最新状态确认。

简单支付验证

以上面的Merkle证明图为例。假设一个轻钱包用户想要发送一笔交易,但是在此之前需要验证RPC节点是否提供了准确的资产余额信息。该余额信息存储在数据块c中。

由于轻钱包不会存储区块链数据,因此它会请求RPC节点提供Merkle证明。RPC节点会提供c中的余额值以及“路径证明”,即从c向上移动到state root所需的哈希列表。在这种情况下,RPC节点将提供c中的余额值以及hash(d) 与h(h(a) + h(b)))的值。

有了这些值,轻钱包就可以开始验证了。首先,对c的余额值进行哈希处理得到h(c)。该哈希值与hash(d)相加后,再次对结果进行哈希处理从而获得h(h(c) + h(d)))的值。

重复此过程,将计算所得的h(h(c) + h(d)))与RPC节点提供的h(h(a) + h(b)))相加,最后再进行一次哈希计算得到Merkle根。此时就可以开始进行验证了。

如果RPC节点提供的c块中的资产余额以及路径证明是正确的,则此过程将获得与共识节点在P2P网络上签名和广播的相同的Merkle根。如果余额或者路径证明不正确将产生一个不同的state root,即可证明RPC节点提供了与共识节点不一致的错误信息。

轻钱包现在就可以在不存储区块链副本的情况下验证余额数据,确保RPC服务器提供的信息与共识节点一致。

历史上的今天:

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

发表评论


表情