详解以太坊默克尔压缩前缀树-MPT

在以太坊中，一种经过改良的默克尔树非常关键，是以太坊数据安全与效率的保障，此树在以太坊中称之为 MPT（默克尔压缩前缀树）。 MPT 全称是 Merkle Patricia Trie 也叫 Merkle Patricia Tree，是 Merkle Tree 和 Patricia Tree 的混合物。 Merkle Tree(默克尔树) 用于保证数据安全，Patricia Tree(基数树,也叫基数特里树或压缩前缀树) 用于提升树的读写效率。

简述

以太坊不同于比特币的 UXTO 模型，在账户模型中，账户存在多个属性（余额、代码、存储信息），属性（状态）需要经常更新。因此需要一种数据结构来满足几点要求：

• ①在执行插入、修改或者删除操作后能快速计算新的树根，而无需重新计算整个树。
• ②即使攻击者故意构造非常深的树，它的深度也是有限的。否则，攻击者可以通过特意构建足够深的树使得每次树更新变得极慢，从而执行拒绝服务攻击。
• ③树的根值仅取决于数据，而不取决于更新的顺序。以不同的顺序更新，甚至是从头重新计算树都不会改变树的根值。

要求①是默克尔树特性，但要求②③则非默克尔树的优势。 对于要求②，可将数据 Key 进行一次哈希计算，得到确定长度的哈希值参与树的构建。而要求③则是引入位置确定的压缩前缀树并加以改进。

Trie 介绍

对部分开发者来说 Trie 这个术语可能比较陌生，而理解 Trie 的概念在本文中非常重要。因此，我先介绍 Trie 。

在计算机科学中， Trie ，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。 与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。 一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。 一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie 这个术语来自于re Trie val。根据词源学， Trie 的发明者Edward Fredkin把它读作/ˈtriː/ "tree"。但是，其他作者把它读作/ˈtraɪ/ "try"。如图所示：

在图示中，键标注在节点中，值标注在节点之下。每一个完整的英文单词对应一个特定的整数。 Trie 可以看作是一个确定有限状态自动机，尽管边上的符号一般是隐含在分支的顺序中的。键不需要被显式地保存在节点中。图示中标注出完整的单词，只是为了演示 Trie 的原理。

Trie 中的键通常是字符串，但也可以是其它的结构。 Trie 的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，bitwise Trie 中的键是一串比特，可以用于表示整数或者内存地址。

上文摘自维基百科。

压缩前缀树(Patricia Tree)

在压缩前缀树（基数树）中，键值是通过树到达相应值的实际路径值。 也就是说，从树的根节点开始，键中的每个字符会告诉您要遵循哪个子节点以获取相应的值，其中值存储在叶节点中，叶节点终止了穿过树的每个路径。假设键是包含 N 个字符的字母，则树中的每个节点最多可以有 N 个子级，并且树的最大深度是键的最大长度。

虽然基数树使得以相同字符序列开头的键的值在树中靠得更近，但是它们可能效率很低。 例如，当你有一个超长键且没有其他键与之共享前缀时，即使路径上没有其他值，但你必须在树中移动（并存储）大量节点才能获得该值。 这种低效在以太坊中会更加明显，因为参与树构建的 Key 是一个哈希值有 64 长（32 字节），则树的最长深度是 64。树中每个节点必须存储 32 字节，一个 Key 就需要至少 2KB 来存储，其中包含大量空白内容。 因此，在经常需要更新的以太坊状态树中，优化改进基数树，以提高效率、降低树的深度和减少 IO 次数，是必要的。

改进方案

为了解决基数树的效率问题，以太坊对基数树的最大改动是丰富了节点类型，围绕不同节点类型的不同操作来解决效率。

1. 空白节点 NULL
2. 分支节点 branch Node [0,1,...,16,value]
3. 叶子节点 leaf Node : [key,value]
4. 扩展节点 extension Node: [key,value]

多种节点类型的不同操作方式，虽然提升了效率，但复杂度被加大。而在 geth 中，为了适应实现，节点类型的设计稍有不同：

//trie/node.go:35
type (
    fullNode struct { //分支节点
        Children [17]node
        flags    nodeFlag
    }
    shortNode struct { //短节点：叶子节点、扩展节点
        Key   []byte
        Val   node
        flags nodeFlag
    }
    hashNode  []byte //哈希节点
    valueNode []byte //数据节点,但他的值就是实际的数据值
)
var nilValueNode = valueNode(nil) //空白节点

• fullNode: 分支节点，fullNode[16]的类型是 valueNode。前 16 个元素对应键中可能存在的一个十六进制字符。如果键[key,value]在对应的分支处结束，则在列表末尾存储 value 。
• shortNode: 叶子节点或者扩展节点，当 shortNode.Key的末尾字节是终止符 16 时表示为叶子节点。当 shortNode 是叶子节点是，Val 是 valueNode。
• hashNode: 应该取名为 collapsedNode 折叠节点更合适些，但因为其值是一个哈希值当做指针使用，所以取名 hashNode。使用这个哈希值可以从数据库读取节点数据展开节点。
• valueNode: 数据节点，实际的业务数据值，严格来说他不属于树中的节点，它只存在于 fullNode.Children 或者 shortNode.Val 中。

各类 Key

在改进过程中，为适应不同场景应用，以太坊定义了几种不同类型的 key 。

1. keybytes ：数据的原始 key
2. Secure Key: 是 Keccak256(keybytes) 结果，用于规避 key 深度攻击，长度固定为 32 字节。
3. Hex Key: 将 Key 进行半字节拆解后的 key ，用于 MPT 的树路径中和降低子节点水平宽度。
4. HP Key: Hex 前缀编码(hex prefix encoding)，在节点存持久化时，将对节点 key 进行压缩编码，并加入节点类型标签，以便从存储读取节点数据后可分辨节点类型。

下图是 key 有特定的使用场景，基本支持逆向编码，在下面的讲解中 Key 在不同语义下特指的类型有所不同。

节点结构改进

当我们把一组数据（romane、romanus、romulus、rubens、ruber、rubicon、rubicunds）写入基数树中时，得到如下一颗基数树：

在上图的基数树中，持久化节点，有 13 次 IO。数据越多时，节点数越多，IO 次数越多。另外当树很深时，可能需要遍历到树的底部才能查询到数据。 面对此效率问题，以太坊在树中加入了一种名为分支节点(branch node) 的节点结构，将其子节点直接包含在自身的数据插槽中。

这样可缩减树深度和减少IO次数，特别是当插槽中均有子节点存在时，改进效果越明显。 下图是上方基数树在采用分支节点后的树节点逻辑布局：

从图中可以看出节点数量并无改进，仅仅是改变了节点的存放位置，节点的分布变得紧凑。图中大黑圆圈均为分支节点，它包含一个或多个子节点， 这降低了 IO 和查询次数，在上图中，持久化 IO 只有 6 次，低于基数树的 12 次。

这是因为在持久化分支节点时，并不是将叶子节点分开持久化，而是将其存储在一块。并将持久化内容的哈希值作为一个新节点来参与树的进一步持久化，这种新型的节点称之为扩展节点。比如，数据 rubicon(6) 和 rubicunds(7) 是被一起持久化，在查询数据 rubicon 时，将根据 hasNode 值从数据库中读取分支节点内容，并解码成分支节点，内含 rubicon 和 rubicunds。

另外，数据 Key 在进入 MPT 前已转换 Secure Key。 因此，key 长度为 32 字节，每个字节的值范围是[0 - 255]。 如果在分支节点中使用 256 个插槽，空间开销非常高，造成浪费，毕竟空插槽在持久化时也需要占用空间。同时超大容量的插槽，也会可能使得持久化数据过大，可能会造成读取持久化数据时占用过多内存。 如果将 Key 进行Hex 编码，每个字节值范围被缩小到 [0-15] 内(4bits)。这样，分支节点只需要 16 个插槽来存放子节点。

上图中 0 - f 插槽索引是半字节值，也是 Key 路径的一部分。虽然一定程度上增加了树高，但降低了分支节点的存储大小，也保证了一定的分支节点合并量。

树的增删改查

上面已介绍树的改进内容，下面我们来讲解经过改进后，树的增删改查将有哪些不一样。在讲解前需要你掌握几个内含的规则和概念：

1. MPT 是一颗逻辑树，并不一一对应物理树（存储）。
2. 在 MPT 中必将在叶子节点处存放在 Key 对应的数据节点（ValueNode），数据节点必然是在树的子叶节点中。
3. 在 MPT 中，到达节点的树路径 Path 和节点中记录的 Key 一起构成了节点的完整 Key。
4. 分支节点的插槽 Index 就是树路径的一部分。

查询数据

即使在修改某项数据时，也会涉及到查询，因此我先讲讲 MPT 树的查询逻辑。 在树中查找数据，需要考虑性能，省时和低 IO 是关键。 因为数据项 [Key,Value] 的 Key 是确定的，那么数据在 MPT 中的树路径也是确定的。 因此，达到数据项的路径是唯一的，是效率最高的最短路径查找。

下图是以太坊从 MPT 中查询查找某 Key 对应数据的流程图。

图中流程中，有几点需要稍微说明：

1. 查找时依赖节点的类型，不同类型的节点所包含的值属性不同。
2. 要找的数据虽然并不一定对应一个存储，但要查找的数据存在于叶子节点的 shortNode.Value 中，value 实际 valueNode 。
3. 在分支节点中继续向下查找时，分支节点的子节点插槽也属于路径的一部分，占用一个字节。根据 pos= key[0] 便可在确定的插槽 pos 中继续查找。
4. 短节点 shortNode [key,value] 中只有在 数据 key 是 node.key 的前缀时，才能说明数据项属于 node 子树的一部分，可以继续查找。
5. 当节点是哈希节点时，node 就是节点数据持久化到 KV 数据库时所用的键。根据此键可以从数据库中读取节点原始数据。加载节点数据到内存后，可以继续判断节点类型。

插入数据

插入数据包含新数据加入和旧数据修改。下图是往 MPT 中插入数据流程。

首先，插入空节点是无意义的，反而会使树变得臃肿。 因此，当数据为空时，需从树中删除该数据节点。 否则需要根据数据节点的路径从树根开始查找到数据节点所在位置来更新节点。在查找时根据路径中节点的类型不同，需要不同的解析方式。

1. 判断当前节点的类型，如果是哈希节点，则需要先从数据库中读取节点原始数据。还原成一颗子树后，继续执行插入到此子树中。
2. 如果是分支节点，那么只需要确认子节点插槽位置，便可以将子节点作为一颗子树继续下探尝试更新。
3. 如果是短节点，则需匹配相同前缀。如果前缀刚好等于原节点key，则说明需要将原节点的 value 进行更新。 否则，说明此路径处需要分叉才能容纳这个两个节点。分叉时，是构建新的分支节点，新节点的 key 为相同前缀部分，将原节点下移到新节点下对应的子节点插槽中。 数据节点则也存放在新节点对应的插槽中。
4. 当到达数据节点时，数据节点的 Key 是不存在的，节点本身即是数据。如果节点不含数据，则说明插入的节点是第一次出现，属于新增。在树中加入此数据节点即可。 如果存在数据，则说明属于更新旧数据，覆盖即可。

插入数据的过程，是深度递归遍历方式。先深度查找，抵达数据应处位置，再从下向上依次更新此路径上的节点。 虽然只更新了路径中的相关节点，但这毕竟涉及多个节点的更新。从这一点上看，MPT 性能并不出色。

删除数据

从 MPT 中删除数据节点，这比插入数据更加复杂。从树中删除一个节点是容易的，但在 MPT 中删除节点后需要根据前面的改进方案调整结构。 比如，原本是一个分支节点下有两个子节点，现在删除一个子节点后，只有一个子节点的分支节点的存储是无意义的，需要移除并将剩余的子节点上移。 下图是 MPT 中删除数据的流程图。

同样，删除数据也是深度递归遍历。先深度查找，抵达数据应处位置，再从下向上依次更新此路径上的节点。 在删除过程中，主要是对删除后节点的调整。有两个原则：

1. 分支节点至少要有两个子节点，如果只有一个子节点或者没有则需要调整。
2. shortNode 的 value 是 shortNode 时可合并。

删除数据也涉及路径上节点的更新，图中的绿色虚线是表示递归删除节点。

树更新实例

下面，我演示依次将一组数据 romane、romanus、romulus、rubens、ruber、rubicon、rubicunds 插入到 MPT 中时的树结构的变化情况。

首先依次写入：romane、romanus、romulus 后树的变化如下：

图中的每一个圆圈均代表一个节点，只是节点的类型不同。需要注意的是，图中的红色字部分，实际是一个短节点（shortNode）。 比如，红色的“roman“ 短节点的 key 为 roman, value 是分支节点。继续写入 rubens、ruber、rubicon 的变化过程如下：

最后，写入最后一个数据项 rubicunds 后可得到最终的 MPT 树结构：

注意，本过程演示中，为降低复杂度，省去了 key 的 Secure 和 Hex 过程。

MPT数操作总结

即使以太坊有大量改进基数树，形成 MPT。但还是并没有解决树节点更新时的蝴蝶效应问题。 在 MPT 中树的最大深度是 64，当树充分大时，为更新一个数据节点而需要连带更新的节点也非常多。 这使得以太坊的数据更新是昂贵的。大量的变动也会使得每产生一个新区块，持久化数据后。 有大量的存储不再属于最新状态的一部分，即以太坊的数据增量更新的体量依旧很大。

如果要满足以太坊 2.0 的性能要求，继续改进 MPT 是不可忽略的。

计算树Root

上面已描述 MPT 在内存中的结构，下面我们以 romane、romanus、romulus 为示例数据，来讲解是何如计算出 MPT 树的一个树根 Root 值的。

上图是三项数据的业务 Key 经过 HP 编码后，写入 MPT 树后所形成的 MPT 树结构布局。HP表和树的虚线连接表示树路径的生成依据，这是根据前面所描述的 MPT 生成规则而形成的树结构。在树中，一共有6 个节点，其中节点 1 和 3 为扩展节点，节点 2 和 5 为分支节点，节点 4 和 6 为叶子节点。可以看到在分支节点 5 中的 value 位置存放着业务 key “romane” 所对应的值“罗马”，但业务 key “romanus”和“romulus” 则存放在独立的叶子节点中。

当我们执行 trie.Commit 时将获得一个 Hash 值，称之为 树的 Root 值，这个 Root 值是如何得到的呢？ Root 值算法源自默克尔树（Merkle Tree），在默克尔树中，树根值是由从子叶开始不断进行哈希计算得到最终能代表这棵树数据的哈希值。

同样在计算 MPT 树的 Root 值是也是如此，在 MPT 中一个节点的哈希值，是节点内容经 RLP 编码后的 Keccak256 哈希值。当对一个节点进行哈希计算遵循如下规则：

1. Hash(扩展节点)= Hash( HP(node.Key),Hash(node.Value) )， 节点 key 需 HP 编码后参与哈希计算。当 node.Value 是表示业务数据时(valueNode)，将为 Hash( HP(node.Key),node.Value)。
2. Hash(叶子节点) 无，叶子节点只存在于分支节点中。
3. Hash(分支节点)= Hash( hash(node.Children[1]),...,hash(node.Children[i]),node.Value)，需要先将每个子节点存储中的节点进行哈希。如果子节点为 null，则使用空字节表示。

根据上面的规则，我们可以得到上面 MPT 树进行哈希计算时的节点分布：

图中，可哈希的节点只有 4 个，而叶子节点 4 和 6 则直接属于分支节点的一部分参与哈希计算。MPT 的 Root 值是 MPT 树根节点的哈希值。在本示例中，Root 节点为 节点 1，Hash(节点 1)=0x84f3c5......80ef13 即为 MPT 的 Root 值。扩展节点 1 和 3 的 key 在哈希计算时有进行 HP 编码。需要编码的原因是为了区分扩展节点的 value 是叶子节点还是分支节点的区别，具体见 HP 编码规则。

持久化

当需要将 MPT Commit 到 DB 时，这颗树的数据是如何完整存储到数据库的呢？以太坊的持久层是 KV 数据库，一个 Key 对应一份存储内容。 当上面在计算 Root 值时，实际上已完成了哈希值和节点内容的处理过程。不同于在内存中计算 Root 值，在持久化时是持久化和 Hash 计算同步进行。

从Root的计算规则可知，HASH 计算是递归的，从树的叶子节点向上计算。每次计算出一个节点哈希时，将使用此哈希值作为数据库的 Key，存放节点的 RLP 持久化内容到数据库中。 因为节点哈希值以及被包含在父节点中，直至树根。因此，我们只需要知道一颗树的 Root 值，便可以依次从 DB 中读取节点数据，并在内存中构建完整的 MPT 树。

比如，上图中的树的 Root 值为 0x84f3c5……80ef13，通过 db.Get(root) 可获得节点 1，在通过 db.Get(node1.Value) 可获得节点 2...，直至节点 5。

需要注意的是，在分支节点 2 中，他的子节点插槽 6 的位置上是记录的节点 3 的哈希值。在从数据库中获得节点 2 时，并不会立刻将 节点 3 立刻加载。而是在需要使用 到 node2.Children[6]时，根据 node2.Children[6].Value 的类型仅一步判断。如果它是 hashNode 类型，则将根据此 Value 获取节点数据并展开。这样，保证在使用树时是按需实例化节点。

Key的编码规则

Secure 编码

这并非 MPT 树的必要部分，是为了解决路径深度攻击而将数据进入 MPT 前进行一次安全清洗，使用 Keccak256(key) 得到的key 的哈希值替换原数据 key。

在实现上，只需要在原 MPT 树进行依次封装即可获得一颗 Secure MPT 树。

HEX 编码

用于树路径中，是将数据 key 进行半字节拆解而成。即依次将 key[0],key[1],...,key[n] 分别进行半字节拆分成两个数，再依次存放在长度为 len(key)+1 的数组中。 并在数组末尾写入终止符 16。算法如下：

半字节，在计算机中，通常将8位二进制数称为字节，而把4位二进制数称为半字节。 高四位和低四位，这里的“位”是针对二进制来说的。比如数字 250 的二进制数为 11111010，则高四位是左边的 1111，低四位是右边的 1010。

// trie/encoding.go:65
func keybytesToHex(str []byte) []byte {
    l := len(str)*2 + 1
    var nibbles = make([]byte, l)
    for i, b := range str {
        nibbles[i*2] = b / 16
        nibbles[i*2+1] = b % 16
    }
    nibbles[l-1] = 16
    return nibbles
}

例如：字符串 “romane” 的 bytes 是 [114 111 109 97 110 101]，在 HEX 编码时将其依次处理：

最终得到 Hex("romane") = [7 2 6 15 6 13 6 1 6 14 6 5 16]

HP(Hex-Prefix) 编码

Hex-Prefix 编码是一种任意量的半字节转换为数组的有效方式，还可以在存入一个标识符来区分不同节点类型。 因此 HP 编码是在由一个标识符前缀和半字节转换为数组的两部分组成。存入到数据库中存在节点 Key 的只有扩展节点和叶子节点，因此 HP 只用于区分扩展节点和叶子节点，不涉及无节点 key 的分支节点。其编码规则如下图：

前缀标识符由两部分组成：节点类型和奇偶标识，并存储在编码后字节的第一个半字节中。 0 表示扩展节点类型，1 表示叶子节点，偶为 0，奇为 1。最终可以得到唯一标识的前缀标识：

• 0：偶长度的扩展节点
• 1：奇长度的扩展节点
• 2：偶长度的叶子节点
• 3：奇长度的叶子节点

当偶长度时，第一个字节的低四位用0填充，当是奇长度时，则将 key[0] 存放在第一个字节的低四位中，这样 HP 编码结果始终是偶长度。 这里为什么要区分节点 key 长度的奇偶呢？这是因为，半字节 1 和 01 在转换为 bytes 格式时都成为<01>，无法区分两者。

例如，上图 “以太坊 MPT 树的哈希计算”中的控制节点1的key 为 [ 7 2 6 f 6 d]，因为是偶长度，则 HP[0]= (00000000) ₂=0，H[1:]= 解码半字节(key)。 而节点 3 的 key 为 [1 6 e 6 5]，为奇长度，则 HP[0]= (0001 0001)₂=17。

下面是 HP 编码算法的 Go 语言实现：

// trie/encoding.go:37
func hexToCompact(hex []byte) []byte {
    terminator := byte(0)
    if hasTerm(hex) {
        terminator = 1
        hex = hex[:len(hex)-1]
    }
    buf := make([]byte, len(hex)/2+1)
    buf[0] = terminator << 5 // the flag byte
    if len(hex)&1 == 1 {
        buf[0] |= 1 << 4 // odd flag
        buf[0] |= hex[0] // first nibble is contained in the first byte
        hex = hex[1:]
    }
    decodeNibbles(hex, buf[1:])
    return buf
}
func decodeNibbles(nibbles []byte, bytes []byte) {
    for bi, ni := 0, 0; ni < len(nibbles); bi, ni = bi+1, ni+2 {
        bytes[bi] = nibbles[ni]<<4 | nibbles[ni+1]
    }
}

在 Go 语言中因为叶子节点的末尾字节必然是 16（Hex 编码的终止符），依据此可以区分扩展节点还是叶子节点。

参考资料

1. https://github.com/ethereum/wiki/wiki/Patricia-Tree
2. https://ethereum.github.io/yellowpaper/paper.pdf#appendix.D
3. https://ethereum.github.io/yellowpaper/paper.pdf#appendix.C
4. https://ethfans.org/toya/articles/588
5. https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/
6. https://arxiv.org/pdf/1909.11590.pdf