128

Ethereum Merkle Patricia Trie 介绍 (一)

icestormspirit · 于 发布 · 最后由 icestormspirit回复 · 561 次阅读

以太坊代码整体包含几个模块:

  1. 协议管理,一个是外部访问和交互的 JSON-RPC 协议(HTTP),一个用来节点发现和块/交易数据(TCP/UDP) 同步;
  2. 交易池,存储当前未打包的交易;
  3. 共识算法,目前官方版本里面包含了 PoW 和 PoA(Clique), 共识算法主要的作用就是决定产生新块,合法性验证以及冲突解决;
  4. EVM, 用来执行智能合约代码的虚拟机
  5. StateDB, 由 MPT(merkle patric trie) 和 KV 存储两部分组成,以太坊所有数据最终都会落到 KV 存储。

其中很重要的一个模块就是MPT,本文及接下来的文章都会着重介绍这一块。

Merkle Patricia Trie(又称Merkle Patricia Tree)是一种经过改良的、融合了默克尔树和前缀树两种树结构优点的数据结构。之后的文章会讲到的state trie、storage trie、transactions trie和receipts trie都是使用的MPT数据结构。而这几棵树在以太坊实现中也扮演了极其重要的角色,所以先了解下MPT是很有必要的。

MPT提供了一种加密可信的数据结构,用来存储所有的(key, value)对。

由于MPT结合了(1)前缀树(Patricia Trie)(2)默克尔树(Merkle Tree)两种树结构的特点与优势 ,因此在介绍MPT之前,我们首先简要地介绍下这两种树结构的特点。

Trie

Trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,每个节点数据所携带的key不会存储在Trie的节点中,而是通过该节点在整个树形结构里位置来体现;同一个父节点的子节点,共享该父节点的key作为它们各自key的前缀,因此根节点key为空;待存储的数据只存于叶子节点中,非叶子节点帮助形成叶子节点key的前缀。 "Trie"的命名来源于retrieval这个单词,trie的发明者Edward Fredkin把它读作/ˈtriː/ “tree”。

具体看下图所示,根结点为空,分别有6个叶子结点:to, tea, ted, ten,inn和A。

image1

相应的,该trie所存储的key也就分别为to, tea, ted, ten, inn和A。

Patricia trie,又称crit bit tree,压缩前缀树,是一种更节省空间的Trie(前缀树)。对于基数树的每个节点,如果该节点是唯一的子树的话,就和父节点合并。下图来自wiki:

image2

Merkle Tree

Merkel Tree,默克尔树,又叫哈希树。默克尔树叶子结点的key是他所关联数据块的哈希值,而非叶子结点的key是他的所有叶子节点哈希拼接起来的字符串的哈希。具体看下图(来自[wiki-MerkleTree](https://en.wikipedia.org/wiki/Merkle_tree)。

b82fb25ae13d4ff199f2386b54632298.png864x550 45.2 KB

这里一共有4个数据块:L1、L2、L3和L4。首先将这四个数据块的值做一个哈希分别存储到对应的叶子结点hash(0-0),hash(0-1),hash(1-0)和hash(1-1),接着再将hash(0-0)和hash(0-1)的值拼接成一个字符串,然后再计算这个字符串的hash就得到父节点Hash 0的值,依此类推得到Top Hash的值。这样构成的默克尔树,如果两棵树的根哈希一致,则这两棵树的结构、节点的内容必然相同。

如上图所示,一棵有着4个叶子节点的树,计算代表整棵树的哈希需要经过7次计算,若采用将这四个叶子节点拼接成一个字符串进行计算,仅仅只需要一次哈希就可以实现,那么为什么要采用这种看似奇怪的方式呢?

优势

  • 快速重哈希

默克尔树的特点之一就是当树节点内容发生变化时,能够在前一次哈希计算的基础上,仅仅将被修改的树节点进行哈希重计算,便能得到一个新的根哈希用来代表整棵树的状态。

  • 轻节点扩展

采用默克尔树,可以在公链环境下扩展一种“轻节点”。轻节点的特点是对于每个区块,仅仅需要存储约80个字节大小的区块头数据,而不存储交易列表,回执列表等数据。然而通过轻节点,可以实现在 非信任的公链环境中验证某一笔交易是否被收录在区块链账本的功能。这使得像比特币,以太坊这样的区块链能够运行在个人PC,智能手机等拥有小存储容量的终端上。

劣势

  • 存储空间开销大

Merkle-Patrcial Trie

MPT是Ethereum自定义的Trie型数据结构。MPT树结合了前缀树和默克尔树的特性,作为存储key-value键值对数据的数据结构。在MPT中的节点类型有以下几种,来源ethereum wiki

  1. NULL (represented as the empty string)
  2. branch A 17-item node [ v0 ... v15, vt ]
  3. leaf A 2-item node [ encodedPath, value ]
  4. extension A 2-item node [ encodedPath, key ]

空节点,用来表示空串。

分支节点,用来表示包含1个子节点以上的非叶子结点。其中包含了16个0-9a-f的key和一个value数组项。 在以太坊中,在进行树操作之前,首先会进行一个key编码的转换(下节会详述),将一个字节的高低四位内容分拆成两个字节存储。通过编码转换, key' 的每一位的值范围都在[0, 15]内。因此,一个分支节点的孩子至多只有16个。以太坊通过这种方式,减小了每个分支节点的容量,但是在一定程度上增加了树高。

叶子节点和扩展节点定义类似,都是存储了一个encodedPath,这个path就是共同前缀,叶子结点的value存储的是该节点的value即索引值。扩展节点的key是其孩子节点的索引。

由于叶子/扩展节点共享一套定义,所以以太坊又定义了一套编码方式来区别这两种节点,这会在下一篇详细讲解。

从以太坊代码中分析,trie/node.go

它定义了4种节点:fullNode,shortNode,valueNode,hashNode,其中只有fullNode和shortNode可以带有子节点。

image4.png1738x648 45.8 KB

image5.png1806x324 46.9 KB

fullNode : 是一个带有17项数组成员的节点,可以携带多个子节点的父节点。组中前16个空位分别对应16进制(hex)下的0-9a-f,这样对于每个子节点,根据其key值16进制形式下的第一位的值,就可挂载到Children数组的某个位置,fullNode本身不再需要额外key变量,Children数组的第17位,用来存储该fullNode自身的数据。每个父节点最多拥有16个分支也包含了基于总体效率的考量。

shortNode : 是一个仅有一个子节点的父(枝)节点。它的成员变量Val指向一个子节点,而成员Key是一个任意长度的字符串(字节数组[]byte)。

此外,这两种节点都有一个附带的字段nodeFlag,记录了一些辅助数据:

  • hash:若该字段不为空,则当需要进行哈希计算时,可以跳过计算过程而直接使用上次计算的结果(当节点变脏时,该字段被置空);
  • dirty:当一个节点被修改时,该标志位被置为1;
  • gen:当该节点第一次被载入内存中(或被修改时),会被赋予一个计数值作为诞生标志,该标志会被作为节点驱除的依据,清除内存中“太老”的未被修改的节点,防止占用的内存空间过多。

valueNode : 充当MPT的叶子节点。它其实是字节数组[]byte的一个别名,不带子节点。在使用中,valueNode就是所携带数据部分的RLP哈希值,长度32byte,数据的RLP编码值作为valueNode的匹配项存储在数据库里。

hashNode : 跟valueNode一样,也是字符数组[]byte的一个别名,同样存放32byte的哈希值,也没有子节点。不同的是, hashNode是fullNode或者shortNode对象的RLP哈希值 ,所以它跟valueNode在使用上有着莫大的不同。

这三种类型覆盖了一个普通Trie(也许是PatriciaTrie)的所有节点需求。任何一个[k,v]类型数据被插入一个MPT时,会以k字符串为路径沿着root向下延伸,在此次插入结束时首先成为一个valueNode,k会以自顶点root起到到该节点止的key path形式存在。但之后随着其他节点的不断插入和删除,根据MPT结构的要求,原有节点可能会变化成其他node实现类型,同时MPT中也会不断裂变或者合并出新的(父)节点。

特殊的那个 - hashNode

hashNode 跟valueNode一样,也是字符数组[]byte的一个别名,同样存放32byte的哈希值,也没有子节点。不同的是,hashNode是fullNode或者shortNode对象的RLP哈希值,所以它跟valueNode在使用上有着莫大的不同。

在MPT中,hashNode几乎不会单独存在,而是以nodeFlag结构体的成员(nodeFlag.hash)的形式,被fullNode和shortNode间接持有。一旦fullNode或shortNode的成员变量(包括子结构)发生任何变化,它们的hashNode就一定需要更新。所以在trie.Trie结构体的insert(),delete()等函数实现中,可以看到除了新创建的fullNode、shortNode,那些子结构有所改变的fullNode、shortNode的nodeFlag成员也会被重设,hashNode会被清空。在下次trie.Hash()调用时,整个MPT自底向上的遍历过程中,所有清空的hashNode会被重新赋值。这样trie.Hash()结束后,我们可以得到一个根节点root的hashNode,它就是此时此刻这个MPT结构的哈希值。

hashNode体现了MerkleTree的特点:每个父节点的哈希值来源于所有子节点哈希值的组合,一个顶点的哈希值能够代表一整个树形结构。

  • 128
    ajian1984

    论坛编辑器支持 markdown 格式。可以用 markdown 语法把文本写得更清晰些。。很棒!

  • 128
    icestormspirit

    好的,谢谢!第一次发帖,不太知道格式,但是我这个是用md的,不知道怎么发上来就不对了

  • 128
    ajian1984

    @icestormspirit 先用 md 写,不过复制的时候不要复制最终效果,要复制带有符号的源文本,这样粘贴到编辑器里最终就会有效果出来了。

  • 128
    icestormspirit

    原来如此!