虾说区块链-67-以太坊三

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

区块链-以太坊三：

以太坊：

整理些以太坊相关概念。

Merkle树在bitcoin中有重要作用，以太坊中使用merkle patricia tree（梅克尔帕特里夏树）简称MPT，一种trie（redix）前缀树。以太坊中一种加密认证的数据结构。用于存储所有的key、value键值对，这是一种基于加密学，自动验证防篡改的数据结构。

参考：http://blog.csdn.net/qq_33935254/article/details/55505472

以太坊中区块包括区块头、一个交易列表、一个uncle区块的列表。

区块头中包括，交易的hash树根，用于校验交易的列表。在网络中传输的交易是一个简单的列表，组装为trie树的特殊数据结构，来计算hash根。这个数据结构在区块被验证正确后，那么技术上可以忽略。意味着交易列表在本地以trie树的形式来存储，发送到客户端的时候序列化成列表。客户端接收到交易列表后重新构建交易列表的trie树来验证hash根。

Trie树（redix树）：基数树，是将指针和long整数键值向关联的机制，一般实现快速查询，用于指针和整数值的映射（ID redix机制）、内存管理，这个redix树通常的定义。

IDR REDIX机制，是将对象的身份鉴别号整数值ID和对象指针建立关联表，完成从ID与指针之间的相互转换。IDR机制使用radix树状结构作为由id进行索引获取指针的稀疏数组，通过使用位图可以快速分配新的ID，IDR机制避免了使用固定尺寸的数组存放指针。

那么以太坊中更多称为trie树演变或者PAT（patricia trie or crit bit tree）位树（这个名称还是挺多的），后的一种叫MPT树，先对trie树简要说明：

trie树称为前缀树，一种有序树，保存关联数组，键通常是字符串。和传统的二叉查找树不一样的是，键不是直接保存在节点中，而是节点在树中的位置决定。一个节点的所有下属节点都有相同的前缀。简单理解为，这个节点对应的字符串，根节点对应空字符串，只有叶子节点和部分内部节点所对应的键才有相关的值。

键标注在节点中，值标注在节点下。常用来存储英文单词的每个节点是一个长度为27的指针数组，0-25位a-z字母，26位标志域。

Patricia树：压缩前缀树，更节省空间的trie树，如果检测到节点是唯一子节点那么就合并。如图：

MPT树：merkle patricia tree树，这个是混合了merkle树的产物，merkle树之前的文章已经有详细介绍。在以太坊中使用一种特殊的十六进制前缀的编码（hex-prefixHP），字母表中就16个字符，一个字符为一个nibble。MPT树种节点分类：

空节点：表示为空，代码中位一个空字符串。

叶子节点：leaf，表示[key，value]的一个键值对，key为16进制、value是RLP。

扩展节点：extension，表示[key，value]的一个键值对，value区别是其他节点的hash值，hash用来查询数据库中的基点，简单理解为通过这个hash值去链接到其他的节点。

分支节点：branch，MPT树中key为16进制编码，那么加上value一共17长度的list，如果一个[key，value]对在这个分支节点终止了，那么最后一个元素代表一个值，分支节点既可以搜索路径的终止也可以是路径的中间节点。

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

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

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

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

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

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

来源：

创业不易，用心坚持，希望您多多支持！

打赏

感谢您的支持，我会继续努力的!

扫码打赏

打开支付宝扫一扫，即可进行扫码打赏哦