merkle树、Trie树、MPT树、以太坊中的那些树

以太坊中的树,先再啰嗦下merkle树。在比特币中使用了merkle树的数据结构,那么在以太坊中针对三种对象设计了三课merkle树。称为(merkle patricia树)。分别对应:状态树、交易树、收据树。那么这些树能简单帮助以太坊客户端做一些简单的查询验证。

顺带提一句,所有区块和交易的数据都是存在在levelDB数据库中,在levelDB数据库中一个key-value的模式,其中value存储的内容根据RLP编码。

Merkle树之前有过介绍,这里就不展开了,首先说下Trie树。

Trie树

Trie树也叫做Radix树,又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。

优点:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

树中的key(这个不是币乎的key币~~~),代表是从树根root,到对应的value的一条路径,且这条路径真实可靠。那么从root根节点开始,key中每一个字符都代表一条路径,一条从root开始到你需要寻找的对应的value说经历的所有子节点。value的值存储在子节点。那么假设key中的字符在一个容量为n的不重复字母表,那么每个节点最多有n个孩子节点,树的深度就还是key的最大的长度。

Trie树优点有很多,上面简述了一个,这里再详细分解下:我们假设在一个Trie树中有两个value,且有两个相同的前缀key,那么相同前缀的长度占自身比例越大,那么两个value位置越接近。且不会类似散列表中的冲突,保证了一个key对应一个value。

Trie树缺点,那么就是一个存储不平衡的问题,设想下一个长度比较长的key,树中没有其他key有相同的前缀,那么去查询这个存储key和value就需要遍历相当多的节点,这样导致这个树不平衡。

Merkle Patricia树

Merkle Patricia Tree(简称MPT树,实际上是一种trie前缀树)是以太坊中的一种加密认证的数据结构,可以用来存储所有的(key,value)对。以太坊区块的头部包括一个区块头,一个交易的列表和一个uncle区块的列表。在区块头部包括了交易的hash树根,用来校验交易的列表。在p2p网络上传输的交易是一个简单的列表,它们被组装成一个叫做trie树的特殊数据结构,来计算根hash。值得注意的是,除了校验区块外,这个数据结构并不是必须的,一旦区块被验证正确,那么它在技术上是可以忽略的。但是,这意味着交易列表在本地以trie树的形式存储,发送给客户端的时候序列化成列表。客户端接收到交易列表后重新构建交易列表trie树来验证根hash。RLP(Recursive length prefix encoding,递归长度前缀编码),用来对trie树种所有的条目进行编码.参考:http://www.cnblogs.com/fengzhiwu/p/5565559.html

针对merkle树和Trie树的特点,以太坊对其改进。

目标一:保证树的加密安全,那么每个节点的散列值引用,在levelDB中查询。在非叶节点,数据的表现形式:key代码RLP编码的SHA3散列值,value是节点RLP编码。在获取一个节点的内容,只要根据节点的散列值去访问数据库然后获得RLP编码,解码即可。

目标二:引入多节点来提高效率。Merkle Patricia Tree节点分为下面几种,

1.空节点,就理解为一个空串。

2.叶节点,键值对应为列表,key为16进制编码,value是RLP编码。

3.扩展节点,键值对应列表,value是其他节点散列值,通过这个散列值去链接到其他的节点。

4.分支节点,长度为17的列表,key还是编码为16进制编码,加上value,前16个元素对应key的16个十六进制字符,如果一个键值在这个分支终止了,那么最后的一个元素表示为一个值。分支节点既是搜索的终止也可是路径的中间点。

MPT树中是16进制的hex-prefix,HP编码,对key编码。所以每个节点可能有16个孩子,引入一种特殊的终止标识符来标识key所对应的值是真实的值,还是其他节点的hash值。

一旦终止标识打开,那么key是叶节点,对应真实的value。

终止标识关闭,那么值就是在数据块中查询对应节点的hash。

不论key是奇偶长度,HP对其编码后,一个单独的hex字符或者4bit二进制数字,称为一个nibble。如下图:

一个nibble加上key前面,对终止奇偶符编码,最低位标奇偶性,第二低位编码终止符状态,一旦key是偶数,那么加上另外一个nibble,值0来保证整体的偶性。

MPT树操作

MPT树更新:

更新函数:_update_and_delete_storage(self,node, key, value)针对四种节点。

Node空节点:直接返回[pack_nibbles(with_terminator(key)), value],即对key加上终止符,然后进行HP编码。

Node分支节点:那么key为空时,说明更新的是分支节点的value,直接node[-1]设置为value。那么key不为空时,递归更新key[0]位置为根的子树,顺着key向下找,使用_update_and_delete_storage(self._decode_to_node(node[key[0]]),key[1:], value)

Node是叶子节点或者扩展节点:调用_update_kv_node(self, node, key, value)

curr_key是node的key,找到curr_key和key的最长公共前缀,长度为prefix_length。Key剩余的部分为remain_key,curr_key剩余的部分为remain_curr_key

再分以下情况:

remain_key==[]==remain_curr_key,key和curr_key相等,那么如果node是叶子节点,直接返回[node[0], value]。如果node是扩展节点,那么递归更新node所链接的子节点,即调用:

_update_and_delete_storage(self._decode_to_node(node1),remain_key, value)

remain_curr_key== [],即curr_key是key的一部分。如果node是扩展节点,递归更新node所链接的子节点,即调用:

_update_and_delete_storage(self._decode_to_node(node1),remain_key, value);如果node是叶子节点,那么创建一个分支节点,分支节点的value是当前node的value,分支节点的remain_key[0]位置指向一个叶子节点,这个叶子节点是[pack_nibbles(with_terminator(remain_key[1:])), value]

创建一个分支节点。如果curr_key只剩下了一个字符,并且node是扩展节点,那么这个分支节点的remain_curr_key[0]的分支是node1,即存储node的value。否则,这个分支节点的remain_curr_key[0]的分支指向一个新的节点,这个新的节点的key是remain_curr_key[1:]的HP编码,value是node1。如果remain_key为空,那么新的分支节点的value是要参数中的value,否则,新的分支节点的remain_key[0]的分支指向一个新的节点,这个新的节点是[pack_nibbles(with_terminator(remain_key[1:])),value]

key和curr_key有公共部分,为公共部分创建一个扩展节点,此扩展节点的value链接到上面步骤创建的新节点,返回这个扩展节点;否则直接返回上面步骤创建的新节点。

删除老的node,返回新的node。

https://www.cnblogs.com/fengzhiwu/p/5584809.html

链接中有些详细图解,有兴趣可参考,步骤分明。

MPT树删除操作:

删除函数:_delete_and_delete_storage(self,key)

同样和更新分多种情况:

Node为空节点,那么直接返回。

Node为分支节点,如果key为空,那么表示删除了分支节点的值,node[-1]=‘’,返回node的正规化的结果。如果key不为空,递归查找node的子及诶单,删除对应的value,调用elf._delete_and_delete_storage(self._decode_to_node(node[key[0]]),key[1:])。返回新节点。

Node为叶子节点或者扩展节点,curr_key是当前node的key。一种情况,如果key不是以curr_key开头,说明key不在node为根的子树内,直接返回node。另一种情况,如果node是叶节点,返回BLANK_NODE if key == curr_keyelse node。Node是扩展节点的话,递归删除node的子节点,即调用

_delete_and_delete_storage(self._decode_to_node(node1),key[len(curr_key):])。如果新的子节点和node[-1]相等直接返回node。否则,如果新的子节点是kv节点,将curr_key与新子节点的可以串联当做key,新子节点的value当做vlaue,返回。如果新子节点是branch节点,node的value指向这个新子节点,返回。

MPT树查找:

查找函数:_get(self, node, key)

Node为空节点,那么直接返回。

Node是分支节点,key为空,返回分支节点的value;否则递归查找node的子节点,即调用_get(self._decode_to_node(node[key[0]]),key[1:])

Node是叶子节点,返回node1 if key == curr_key else ‘’

Node是扩展节点,key以curr_key开头,递归查找node的子节点,即调用_get(self._decode_to_node(node1), key[len(curr_key):]);否则,说明key不在以node为根的子树里,返回空。

在以太坊的安全树中采用SHA3(k)作为密钥,状态树和账户存储树中均使用。通过设置离散节点的链深度为64,反复用sload和sstore指令,有效防范Dos攻击。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180508A0DQHT00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券