请选择 进入手机版 | 继续访问电脑版

比特世界—比特币/莱特/区块链/btc/ltc/比特论坛

 找回密码
 立即注册
搜索

Merkle Patricia Tree详解

2017-10-19 20:14| 发布者: admin| 查看: 100| 评论: 0|原作者: 戎佳磊

摘要: 1. 前言1.1 概述Merkle Patricia Tree(又称为Merkle Patricia Trie)是一种经过改良的、融合了默克尔树和前缀树两种树结构优点的数据结构,是以太坊中用来组织管理账户数据、生成交易集合哈希的重要数据结构。MPT树 ...

1. 前言

1.1 概述

Merkle Patricia Tree(又称为Merkle Patricia Trie)是一种经过改良的、融合了默克尔树和前缀树两种树结构优点的数据结构,是以太坊中用来组织管理账户数据、生成交易集合哈希的重要数据结构。

MPT树有以下几个作用:

  • 存储任意长度的key-value键值对数据;
  • 提供了一种快速计算所维护数据集哈希标识的机制;
  • 提供了快速状态回滚的机制;
  • 提供了一种称为默克尔证明的证明方法,进行轻节点的扩展,实现简单支付验证;

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

1.2 前缀树

前缀树(又称字典树),用于保存关联数组,其键(key)的内容通常为字符串。前缀树节点在树中的位置是由其键的内容所决定的,即前缀树的key值被编码在根节点到该节点的路径中。

如下图所示,图中共有6个叶子节点,其key的值分别为(1)to(2)tea(3)ted(4)ten(5)A(6)inn。

优势

相比于哈希表,使用前缀树来进行查询拥有共同前缀key的数据时十分高效,例如在字典中查找前缀为pre的单词,对于哈希表来说,需要遍历整个表,时间效率为O(n);然而对于前缀树来说,只需要在树中找到前缀为pre的节点,且遍历以这个节点为根节点的子树即可。

但是对于最差的情况(前缀为空串),时间效率为O(n),仍然需要遍历整棵树,此时效率与哈希表相同。

相比于哈希表,在前缀树不会存在哈希冲突的问题。

劣势

  • 直接查找效率低下

前缀树的查找效率是O(m),m为所查找节点的key长度,而哈希表的查找效率为O(1)。且一次查找会有m次IO开销,相比于直接查找,无论是速率、还是对磁盘的压力都比较大。

  • 可能会造成空间浪费

当存在一个节点,其key值内容很长(如一串很长的字符串),当树中没有与他相同前缀的分支时,为了存储该节点,需要创建许多非叶子节点来构建根节点到该节点间的路径,造成了存储空间的浪费。

1.3 默克尔树

Merkle树是由计算机科学家 Ralph Merkle 在很多年前提出的,并以他本人的名字来命名,由于在比特币网络中用到了这种数据结构来进行数据正确性的验证,在这里简要地介绍一下merkle树的特点及原理。

在比特币网络中,merkle树被用来归纳一个区块中的所有交易,同时生成整个交易集合的数字指纹。此外,由于merkle树的存在,使得在比特币这种公链的场景下,扩展一种“轻节点”实现简单支付验证变成可能,关于轻节点的内容,将会下文详述。

特点

  • 默克尔树是一种树,大多数是二叉树,也可以多叉树,无论是几叉树,它都具有树结构的所有特点;
  • 默克尔树叶子节点的value是数据项的内容,或者是数据项的哈希值;
  • 非叶子节点的value根据其孩子节点的信息,然后按照Hash算法计算而得出的;

原理

在比特币网络中,merkle树是自底向上构建的。在下图的例子中,首先将L1-L4四个单元数据哈希化,然后将哈希值存储至相应的叶子节点。这些节点是Hash0-0, Hash0-1, Hash1-0, Hash1-1

将相邻两个节点的哈希值合并成一个字符串,然后计算这个字符串的哈希,得到的就是这两个节点的父节点的哈希值。

如果该层的树节点个数是单数,那么对于最后剩下的树节点,这种情况就直接对它进行哈希运算,其父节点的哈希就是其哈希值的哈希值(对于单数个叶子节点,有着不同的处理方法,也可以采用复制最后一个叶子节点凑齐偶数个叶子节点的方式)。循环重复上述计算过程,最后计算得到最后一个节点的哈希值,将该节点的哈希值作为整棵树的哈希。

若两棵树的根哈希一致,则这两棵树的结构、节点的内容必然相同。

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

优势

  • 快速重哈希

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

  • 轻节点扩展

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

劣势

  • 存储空间开销大

2. 术语解释

在下文中,会有些特定的专业术语,在这里首先对这些术语给出定义

  • 世界状态:在以太坊中,所有账户(包括合约账户、普通账户)的状态数据统称为世界状态;
  • 轻节点:指只存储区块头数据的区块链节点;
  • 区块链分叉:指向同一个父块的2个区块被同时生成的情况,某些部分的矿工看到其中一个区块,其他的矿工则看到另外一个区块。这导致2种区块链同时增长;
  • 区块头:指以太坊区块结构体的一部分,用于存储该区块的头部信息,如父区块哈希、世界状态哈希、交易回执集合哈希等。区块头仅存储一些“固定”长度的哈希字段;

3. 结构设计

在这一章节,将详细地介绍MPT树的结构设计,以及采用这种结构设计的用意、优化点。

3.1 节点分类

如上文所述,尽管前缀树可以起到维护key-value数据的目的,但是其具有十分明显的局限性。无论是查询操作,还是对数据的增删改,不仅效率低下,且存储空间浪费严重。故,在以太坊中,为MPT树新增了几种不同类型的树节点,以尽量压缩整体的树高、降低操作的复杂度。

MPT树中,树节点可以分为以下四类:

  • 空节点
  • 分支节点
  • 叶子节点
  • 扩展节点

空节点用来表示空串。

分支节点

分支节点用来表示MPT树中所有拥有超过1个孩子节点以上的非叶子节点, 其定义如下所示:

type fullNode struct {
        Children [17]node // Actual trie node data to encode/decode (needs custom encoder)
        flags    nodeFlag
}

// nodeFlag contains caching-related metadata about a node.
type nodeFlag struct {
    hash  hashNode // cached hash of the node (may be nil)
    gen   uint16   // cache generation counter
    dirty bool     // whether the node has changes that must be written to the database
}

与前缀树相同,MPT同样是把key-value数据项的key编码在树的路径中,但是key的每一个字节值的范围太大([0-127]),因此在以太坊中,在进行树操作之前,首先会进行一个key编码的转换(下节会详述),将一个字节的高低四位内容分拆成两个字节存储。通过编码转换,key'的每一位的值范围都在[0, 15]内。因此,一个分支节点的孩子至多只有16个。以太坊通过这种方式,减小了每个分支节点的容量,但是在一定程度上增加了树高。

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

此外,每个分支节点会有一个附带的字段nodeFlag,记录了一些辅助数据:

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

叶子节点&&扩展节点

叶子节点与扩展节点的定义相似,如下所示:

type shortNode struct {
        Key   []byte
        Val   node
        flags nodeFlag
}

其中关键的字段为:

  • Key:用来存储属于该节点范围的key
  • Val:用来存储该节点的内容;

其中Key是MPT树实现树高压缩的关键!

如之前所提及的,前缀树中会出现严重的存储空间浪费的情况,如下图:

图中右侧有一长串节点,这些节点大部分只是充当非叶子节点,用来构建一条路径,目的只是为了存储该路径上的叶子节点。

针对这种情况,MPT树对此进行了优化:当MPT试图插入一个节点,插入过程中发现目前没有与该节点Key拥有相同前缀的路径。此时MPT把剩余的Key存储在叶子/扩展节点的Key字段中,充当一个”Shortcut“。

例如图中我们将红线所圈的节点称为node1, 将蓝线所圈的节点称为node2。node1与node2共享路径前缀t,但是node1在插入时,树中没有与oast有共同前缀的路径,因此node1的key为oast,实现了编码路径的压缩。

这种做法有以下几点优势:

  • 提高节点的查找效率,避免过多的磁盘访问;

  • 减少存储空间浪费,避免存储无用的节点;

此外Val字段用来存储叶子/扩展节点的内容,对于叶子节点来说,该字段存储的是一个数据项的内容;而对于扩展节点来说,该字段可以是以下两种内容:

  1. Val字段存储的是其孩子节点在数据库中存储的索引值(其实该索引值也是孩子节点的哈希值);
  2. Val字段存储的是其孩子节点的引用;

为什么设计在扩展节点的Val字段有可能存储一串哈希值作为孩子节点的索引呢?

在以太坊中,该哈希代表着另外一个节点在数据库中索引,即根据这个哈希值作为数据库中的索引,可以从数据库中读取出另外一个节点的内容。

这种设计的目的是:

(1)当整棵树被持久化到数据库中时,保持节点间的关联关系;

(2)从数据库中读取节点时,尽量避免不必要的IO开销;

在内存中,父节点与子节点之间关联关系可以通过引用、指针等编程手段实现,但是当树节点持久化到数据库是,父节点中会存储一个子节点在数据库中的索引值,以此保持关联关系。

同样,从数据库中读取节点时,本着最小IO开销的原则,仅需要读取那些需要用到的节点数据即可,因此若目前该节点已经包含所需要查找的信息时,便无须将其子节点再读取出来;反之,则根据子节点的哈希索引递归读取子节点,直至读取到所需要的信息。

由于叶子/扩展节点共享一套定义,那么怎么来区分Val字段存储的到底是一个数据项的内容,还是一串哈希索引呢?在以太坊中,通过在Key中加入特殊的标志来区分两种类型的节点。

3.2 key值编码

在以太坊中,MPT树的key值共有三种不同的编码方式,以满足不同场景的不同需求,在这里单独作为一节进行介绍。

三种编码方式分别为:

  1. Raw编码(原生的字符);
  2. Hex编码(扩展的16进制编码);
  3. Hex-Prefix编码(16进制前缀编码);

Raw编码


鲜花

握手

雷人

路过

鸡蛋

最新评论

QQ|Archiver|手机版|小黑屋|比特世界

p2p265 X3.4© 2013-2017 Designed by p2p265.com

GMT+8, 2017-11-25 02:21 , Processed in 0.431741 second(s), 15 queries .

免责声明:本站文章均来自网络,版权归原作者所有。如果侵犯了您的权益,请与我们联系,我们将会及时处理。