DxChain中文博客

链结构(一):存储结构


前言

以太坊底层数据包括基础数据和状态数据,基础数据是以区块、交易等为单位存储在levelDB数据库中,存储账户状态数据则通过MPT树(Merkle Patricia Trie)存储管理。MPT树是一种经过改良的数据结构,融合了默克尔树和前缀树两种树的优点。虽然常见的平衡二叉树(或红黑树)的应用场景很多,但一般引用的是内存中数据,树的结点数据都临时存储在内存中;在区块链系统中账户状态数据往往很大难以完全在内存中查找运算,需要存放在硬盘,而硬盘的数据访问速度远远低于内存。这就显现出了MPT树的优势,使用MPT树组织同样大小的数据,访问数据时需要读取磁盘的次数远小于使用平衡二叉树或红黑树时的访问次数,同时在一定程度上减少了磁盘的损耗。

本章提纲

  1. 前缀树原理
  2. 默尔克数原理
  3. MPT树的设计
  4. 总结

前缀树原理

维基百科上对trie的定义为:Trie又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。键不需要被显式地保存在节点中。图示中标注出完整的单词,只是为了演示trie的原理。

merkel

每一个节点都是key的一部分,按照key向下遍历,直至最后一个字符便是key所对应的value值。相对于哈希表,查询key所对应的value值,需要遍历整个表,对于前缀树仅需遍历该value所对应key的前缀所对应的根节点即可,通常哈希表的遍历次数大于前缀树,在最差情况下遍历次数相等,而且前缀树不存在哈希冲突的问题。

默克尔树原理

在默克尔树中,分为叶子节点和非叶子节点,叶子节点负责保存输入信息,非叶子节点负责保存子节点哈希。第一层非叶子节点由叶子节点经过哈希计算得到,之后的为中间分支由每一层非叶子节点与相邻的分支拼在一起之后经过哈希计算的结果。在层层哈希计算之后,最后得到哈希值为默克尔树根节点。

叶子节点内容发生变化时,树的根节点的哈希值将发生改变。默克尔树仅需要存储约80个字节大小的区块头数据,通过提交的默克尔路径,便可验证某一笔交易是否被打包进区块链,根据该特点,使区块链轻节点可以运行在手机等存储容量较小的设备上。

merkel

根据完整构建出的默克尔树,确定一个叶子节点为输入值,构建默克尔树路径,选择Tx7为输入叶子节点,根据其余中间分支哈希值,执行计算步骤:

步骤一:通过Tx7计算出哈希 f120...f3cb

步骤二:通过 f120...f3cba931..64ee 计算出哈希 7dbb...8de4

步骤三:通过 7dbb...8de4b769...0cdc 计算出哈希 5618...d65c

步骤四:通过 5618...d65cff25...76fb 计算出哈希 35e4...89f2

最终计算出哈希是稀疏默克尔树的根节点,与完整默克尔树的根节点相等,可以证明所需验证的交易信息已存储在区块链上。稀疏默克尔证明与默克尔证明对比:

image-20201230143336535

使用稀疏默克尔证明通过移除大部分除需要验证交易之外的交易详情和部分中间分支节点,再利用节点哈希便构建整个默克尔树的证明,有效降低了证明算法的复杂度,减小了通信中的数据量,使内存空间更小,CPU 周期更短,实现了手机等设备上的轻节点验证交易。

MPT树的设计

如上文所述,尽管前缀树可以维护LevelDB内键值对数据,但是其具有的局限性十分明显。无论是查询操作,还是对数据的增删改,不仅效率低下,且存储空间浪费严重。因此以太坊为MPT树新增了几种不同类型的树节点,压缩了整体的树高,降低了操作的复杂度。本次将主要介绍MPT树的设计和优缺点。

首先,在以太坊的状态数据存储中,数据的key和value编码都是byte[]类型,为节省存储空间以太坊将byte的每4bit定义为nibble, 并将key的编码拆分为两个nibble。而该value为数据的哈希,需要根据该哈希值从数据库取出所对应的内容。

nibble

如果使用一个完整的byte作为key的最小单位,byte的范围为[0,255],因此索引数组的大小为256。考虑到索引数组中的元素大多数状态下为空,没有指向数据结点。在这种情形下,32字节的哈希作为索引数组的元素,无用数据将占用大量的空间。以太坊通过将byte进一步拆分,可以将索引数组从256降为16,减少了存储空间的浪费。通过这种方式,减小了每个分支节点的容量,但是在一定程度上增加了树高。

在以太坊中,索引数组的每个元素都是下一个结点的哈希,而不是指针。父结点是子结点的哈希,该方式使得以太坊的Trie具备了默克尔树的功能,通过验证两棵Trie根结点的哈希值是否相等,来判断两棵Trie怼内容是否相同。因此在以太坊内,采用Trie存储以太坊的状态等数据。

其次,以太坊将Trie内的结点分为了两类,fullNode和shortNode,在fullNode又分为空节点和全节点,shortNode分为扩展节点和叶子结点。

空节点表示为空值,其定义为:

nilValueNode = valueNode(nil)

分支节表示有超过1个子节点以上的非叶子节点,其定义为:

fullNode struct {
   Children [17]node // all 17 available slots could be allocated, aka. indices
   flags    nodeFlag // flags indicating status of the node, including cached hash, cachegen,
   // and whether node is dirty.
}

结合前缀树的特点,MPT将key编码在Trie的路径中。由于byte的拆分索引数组降为16,因此一个分支节点的孩子至多只有16个。

分支节点的孩子列表中,最后一个元素是用来存储value的内容。

叶子结点和扩展结点的定义相同:

shortNode struct {
   Key   []byte   // Key is the string key contained in this node.
   Val   node     // Val is the node this node is pointing to.
   flags nodeFlag // flags indicating status of the node, including cached hash, cachegen,
   // and whether node is dirty.
}

key是以太坊对前缀树改进的关键,当树的某条路径没有分支时,使用一个结点存储路径上的所有key,以较为易懂的方式表示前缀树的优化,如图所示。

shortNode

以太坊该方案,可提升查找的效率,减少过于频繁的磁盘操作,减少存储空间浪费,避免存储无用的节点。

Val用来存储结点的内容,在叶子结点中,该字段存储的是一个数据项的内容。而对于扩展结点中,可表示为:

  • 子结点在数据库中存储的索引值
  • 子结点的引用

总结

以太坊对Trie的改进,节省了大量的存储空间,可以进行高效的读写,并具有默克尔树的特性。但是以太坊的存储格式仍有较多问题,比如,以太坊维护多个结构会增加复杂性,典型的例子就是节点必须先遍历账户 Trie,得到存储 Trie 的根,然后再到存储 Trie 上获取数据。以太坊内设计的扩展结点是一种特殊的节点,负责给特定子树上的所有 key 加上前缀。这些节点的作用是能够限制需要被哈希的节点数量,但是也引入了复杂性,因为它们所涉及的 key 必须以特定方式打包。以太坊所采用的十六进制的前缀也会带来复杂性和混乱,并且十六进制的Trie比二进制Trie大四倍左右。以太坊在改进的同时产生了新的问题,正是为解决不断产生的新问题,使得以太坊Trie存储变得十分复杂。

附录

[1] https://en.wikipedia.org/wiki/Trie
[2] DR. GAVIN WOOD. ETHEREUM: A SECURE DECENTRALISED GENERALISED TRANSACTION LEDGER PETERSBURG VERSION. 2020-12-28. url:https://ethereum.github.io/yellowpaper/paper.pdf
[3] Guillaume Ballet. Ethereum state tree format change using an overlay. 2020-5-26.url:https://medium.com/@gballet/ethereum-state-tree-format-change-using-an-overlay-e0862d1bf201

Author image

About DxChain

DxChain is the world’s first decentralized big data and machine learning network powered by a computing-centric blockchain.