虾说区块链-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）内容支持计划赞助。

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