虾说区块链-68-以太坊四

一直在说区块链是一系列技术结合后的新的技术架构,那么这里分别介绍下这些相关技术,也涉及到一些扩展开去的相关内容。

区块链-以太坊四:

以太坊:

整理些以太坊相关概念。

以太坊中改进Redix树,增加其加密安全,每个节点通过hash被引用,即树的merkle部分是一个节点确定性的加密hash,一个非叶节点存储在leveldb中(关系型数据库),数据库中key是节点的RLP编码后的hash,value是节点的RLP编码。获得一个非叶子节点的子节点只需根据子及诶单的hash访问数据库获得节点的RLP编码,随即解码即可。那么这种模式根节点就是整个树的加密签名,任意给定trie的根hash公开,所有节点都可以证明,证明每一步向上的路径是特定的key是否有给定的值。

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

接着上一篇的MPT树。

下图:

图中有2个扩展节点(extension)

2个分支节点(brance)

4个叶子节点(leaf)

图中右上角:

叶子节点键值。

第一个分支节点中1和f位置,分别指向了两个叶子节点。

第二个分支节点中3和9位置,分别指向另外两个叶子节点。

图中左下角:

节点的前缀。

节点前缀遵循HP编码原则,补全保持整体的偶性。

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(node[1]),remain_key, value)

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

_update_and_delete_storage(self._decode_to_node(node[1]),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]的分支是node[1],即存储node的value。否则,这个分支节点的remain_curr_key[0]的分支指向一个新的节点,这个新的节点的key是remain_curr_key[1:]的HP编码,value是node[1]。如果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

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

本文由币乎社区(bihu.com)内容支持计划赞助。

之前写了点东西,随着对区块链的理解,发现有些理解的并不透彻,重新整理。如有理解不正确的地方,请及时指正,同时有兴趣一块交流的可以加笔者微信:

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180118B041DB00?refer=cp_1026

同媒体快讯

相关快讯

扫码关注云+社区