Blockchain Ethereum

Ethereum 中的 MPT ( Merkle Patricia Tree )（二）

Ethereum 学习笔记

Posted by Nicodechal on 2019-03-03

概述

本文主要介绍以太坊中的 Merkle Patricia Tree。

Merkle Patricia Tree (MPT)，顾名思义，同时具有基数树和哈希树的特点。一方面，MPT 能够像基数树一样进行键值对的存储和高效的索引，另一方面，其还具备哈希树的数据验证能力。

考虑上篇中提到的哈希树，可以认为是将哈希算法结合到二叉树中，即将二叉树中的子节点指针使用哈希指针代替。MPT 则可以认为是将哈希算法结合到基数树中，将基数树中的子节点指针使用哈希指针代替。

由此可知，所谓的 MPT 其实就是基数树，只不过改用哈希指针链接子节点。这样做的目的是方便存储到 K-V 数据库中，同时给予数据结构数据验证的能力。因此，下面先介绍一下基数树的构建。

基数树的构建

考虑上节提到的基数树如下：

基数树的构建过程需要考虑每个分支的公共前缀。

  1. 初始分支需要考虑所有的键值对（图中单词是键，数字是值）的公共前缀，为 r，因此 r 为根节点。
1
2
3
4
5
6
7
r omane
r omanus
r omulus
r ubens
r uber
r ubicon
r ubicundus
  1. 接着考虑 r 之后的字符情况。由于公共前缀有两种情况 om 和 ub，因此产生分支。
1
2
3
4
5
6
7
8
r:
  om ane
  om anus
  om ulus
  ub ens
  ub er
  ub icon
  ub icundus
  1. 接着每个分支分别得到公共前缀：
1
2
3
4
5
6
7
8
9
10
r:
  om:
    an e
    an us
    ulus 
  ub:
    e ns
    e r
    ic on
    ic undus
  1. 没有更多分支的叶子节点，填入从根节点到该叶子节点的路径上存储的键值对的值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
r:
  om:
    an:
      e
      us
    ulus:
      3 (romulus -> 3)
  ub:
    e:
      ns
      r
    ic:
      on
      undus
  1. 补全剩余叶子节点的值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
r:
  om:
    an:
      e:
        1 (romane -> 1)
      us:
        2 (romanus -> 2)
    ulus:
      3 (romulus -> 3)
  ub:
    e:
      ns:
        4 (rubens -> 4)
      r:
        5 (ruber -> 5)
    ic:
      on:
        6 (rubicon -> 6)
      undus:
        7 (rubicundus -> 7)

示意图如前所示。例如寻找 rubicon 对应的值，流程如下：

  1. 从根节点开始，为 r 与 rubicon 前缀相同，ubicon 进入下一层。
  2. 第二层与 ub 匹配，icon 进入 ub 分支。
  3. 第三层与 ic 匹配， on 进入 ic 分支。
  4. 第四层与 on 匹配，键值匹配结束，取该节点对应值为 6，得到 rubicon -> 6，结束。

下面寻找 rom 对应的值，流程如下：

  1. 从根节点开始，r 匹配，om 进入下一层。
  2. 第二层与 om 匹配，键值匹配结束，该节点没有对应的值，因此键 rom 对应的值未找到，结束。

以太坊中的 Patricia Tree

以太坊中的基数树类似于上一节提到的基数树，不过有一些不同。首先，树使用的字母表为 {0, 1, 2, ..., f}。例如对于键值 do，其 ASCII 码对应的十六进制表示为：64 6f，因此对串 646f 进行前缀匹配（类似上一节的过程，只不过字母表从 {a, b, c, ..., z}，变为 {0, 1, 2, ..., f}）。

其次，为了方便进行存储，以太坊的对前缀树进行了改进，其树节点包含四种类型：

  1. NULL 节点
    表示空串
  2. Branch 节点
    节点包含 17 个元素表示为 [v0, v1, v2, ..., vf, value]，其中 vn 表示前缀中（{0, 1, 2, ..., f}）的一个字母对应的下层节点指针，value 表示一个键值对的值。
  3. Leaf 节点
    节点包含 2 个元素表示为 [v0, value]，其中 v0 表示一个字母组成的串，例如 6e，6ef 等。value 表示一个键值对的值。
  4. Extension 节点
    节点包含 2 个元素表示为 [v0, key]，其中 v0 表示一个字母组成的串。key 表示指向下一层节点的指针。

下面举例说明以太坊中的 MPT 构建，假设需要存储下面键值对：

1
2
3
4
('do', 'verb'), 
('dog', 'puppy'), 
('doge', 'coin'), 
('horse', 'stallion')

将键值转为十六进制串（其中空格只是为了方便描述）：

1
2
3
4
('64 6f', 'verb'), 
('64 6f 67', 'puppy'), 
('64 6f 67 65', 'coin'), 
('68 6f 72 73 65', 'stallion')

首先取所有键值对的公共前缀 6 为根节点，由于该节点不是叶子节点，也没有产生多个分支 （6 是所有键值对的前缀），所以根节点应该是一个 Extension 节点。这里用如下形式表示一个节点，之后相同：

1
${指向节点 X 的指针}: ${节点 X}

得到当前构建的树如下：

1
root: [6, key]

其中 key 表示指向下一层节点的指针，待填写，下同。

接下来，所有键值对中有两种前缀 4 和 8，因此使用 Branch 节点。同时 v4 和 v8 有指向下一层的指针：

1
2
root:   [6, node1]
node1:  [<>, <>, <>, <>, key1, <>, <>, <>, key2, <>, <>, <>, <>, <>, <>, <>, <>]

其中 <> 表示没有值。root 节点中的 key 填为指向新增 Branch 节点的指针 node1。

对于前缀为 4 的分支，所有节点都有相同的公共前缀 6f，同时有一个节点已经完整添加到树中（64 6f），因此添加一个 Extension 节点（不是 Leaf 节点是因为还有未加入的键值以此节点为前缀）；而 8 所在分支只有一个元素，直接添加一个叶子节点，其值为 stallion：

1
2
3
4
root:   [6, node1]
node1:  [<>, <>, <>, <>, node2, <>, <>, <>, node3, <>, <>, <>, <>, <>, <>, <>, <>]
node3:  [6f 72 73 65, 'stallion']
node2:  [6f, key]

然后，由于 node2 对应的 key 值指向的节点 1. 需要以 verb 为值（为 64 6f 对应的值）；2. 不能为 Leaf 节点因为还有未添加的键。因此 key 指向的节点应为 Branch 节点，且其 value 为 verb。同时，此时 puppy 和 coin 有公共前缀字母 6，因此添加的 Branch 如下：

1
2
3
4
5
root:   [6, node1]
node1:  [<>, <>, <>, <>, node2, <>, <>, <>, node3, <>, <>, <>, <>, <>, <>, <>, <>]
node3:  [6f 72 73 65, 'stallion']
node2:  [6f, node4]
node4:  [<>, <>, <>, <>, <>, <>, key, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb']

接下来，未存的键值对前缀为：

1
2
('7', 'puppy'), 
('7 65', 'coin'),

有公共前缀 7，因此添加一个 Extension 节点（不能为 Leaf 节点因为还有未添加的键）：

1
2
3
4
5
6
root:   [6, node1]
node1:  [<>, <>, <>, <>, node2, <>, <>, <>, node3, <>, <>, <>, <>, <>, <>, <>, <>]
node3:  [6f 72 73 65, 'stallion']
node2:  [6f, node4]
node4:  [<>, <>, <>, <>, <>, <>, node5, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb']
node5:  [7, key]

key 对应的节点的 value 为 puppy，同时不能是 Leaf 节点，所以为 Branch 节点，同时，取 coin 对应键值前缀字母 6 形成分支：

1
2
3
4
5
6
7
root:   [6, node1]
node1:  [<>, <>, <>, <>, node2, <>, <>, <>, node3, <>, <>, <>, <>, <>, <>, <>, <>]
node3:  [6f 72 73 65, 'stallion']
node2:  [6f, node4]
node4:  [<>, <>, <>, <>, <>, <>, node5, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb']
node5:  [7, node6]
node6:  [<>, <>, <>, <>, <>, <>, key, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy']

最后，coin 剩余前缀 5，且没有其他节点，因此插入一个叶子节点：

1
2
3
4
5
6
7
8
root:   [6, node1]
node1:  [<>, <>, <>, <>, node2, <>, <>, <>, node3, <>, <>, <>, <>, <>, <>, <>, <>]
node3:  [6f 72 73 65, 'stallion']
node2:  [6f, node4]
node4:  [<>, <>, <>, <>, <>, <>, node5, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb']
node5:  [7, node6]
node6:  [<>, <>, <>, <>, <>, <>, node7, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy']
node7:  [5, 'coin']

为了对前缀进行对齐（例如 node7 的前缀 5 只有半个字节，补全为一个字节方便存储）和区分 Leaf 节点和 Extension 节点，对 Leaf 节点和 Extension 节点按下面规则添加前缀：

  1. 对于 Leaf 节点，如果前缀值长度不是一个字节的整数倍，添加半个字节的前缀 3, 例如 node7 补全为 node7: [35, 'coin']
  2. 对于 Leaf 节点，如果前缀值长度是一个字节的整数倍，添加一个字节的前缀 20，node3 补全为 node3: [20 6f 72 73 65, 'stallion']
  3. 对于 Extension 节点，如果前缀值长度不是一个字节的整数倍，添加半个字节的前缀 1，例如 root 节点补全为 root: [16, node1]
  4. 对于 Extension 节点，如果前缀值长度是一个字节的整数倍，添加一个字节的前缀 00，例如 node2 补全为 node2: [00 6f, node4]

对于上面例子进行补全得到：

1
2
3
4
5
6
7
8
root:   [16, node1]
node1:  [<>, <>, <>, <>, node2, <>, <>, <>, node3, <>, <>, <>, <>, <>, <>, <>, <>]
node3:  [20 6f 72 73 65, 'stallion']
node2:  [00 6f, node4]
node4:  [<>, <>, <>, <>, <>, <>, node5, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb']
node5:  [17, node6]
node6:  [<>, <>, <>, <>, <>, <>, node7, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy']
node7:  [35, 'coin']

以太坊中的 Merkle Patricia Tree

以太坊的基数树中，每个节点使用一个特殊的指针指向，并在父节点中只用该值访问该节点。下面说明该值求法。

首先，由于每个节点都是一个字节数组（已经进行了补齐）node，以太坊首先对字节数组进行 RLP 编码 得到 RLP(node)。接下来定义一个函数 H(x): x >= 32 ? sha3(x) : x，最终指向 node 节点的指针为 H(RLP(node))，有时候也被称为哈希指针。例如上面的 pointer of node7 = hash7 = H(RLP(<0x35, 'c', 'o', 'i', 'n'>)) 。

将上面的例子的基数树使用哈希指针代替得到以太坊中的 MPT：

1
2
3
4
5
6
7
8
rootHash:   [16, hash1]
hash1:      [<>, <>, <>, <>, hash2, <>, <>, <>, hash3, <>, <>, <>, <>, <>, <>, <>, <>]
hash3:      [20 6f 72 73 65, 'stallion']
hash2:      [00 6f, hash4]
hash4:      [<>, <>, <>, <>, <>, <>, hash5, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb']
hash5:      [17, hash6]
hash6:      [<>, <>, <>, <>, <>, <>, hash7, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy']
hash7:      [35, 'coin']

此时只要保存 rootHash，当 MPT 中存储的键值对被篡改时便可以被检测到，因为此时 rootHash 也会发生变化。

在以太坊中，所有的数据最终通过键值对的形式存在了底层的数据库中，相对于直接存储数据：

1
2
3
4
('do', 'verb'), 
('dog', 'puppy'), 
('doge', 'coin'), 
('horse', 'stallion')

以太坊将数据整理成 MPT 再进行存储（此时存储的内容变为 (H(RLP(node)), node) 对）。此时，只要将该树的 rootHash 存储在区块中，就可以防止树中的数据被篡改。

1
2
3
4
5
6
7
8
(rootHash, [16, hash1])
(hash1, [<>, <>, <>, <>, hash2, <>, <>, <>, hash3, <>, <>, <>, <>, <>, <>, <>, <>])
(hash3, [20 6f 72 73 65, 'stallion'])
(hash2, [00 6f, hash4])
(hash4, [<>, <>, <>, <>, <>, <>, hash5, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb'])
(hash5, [17, hash6])
(hash6, [<>, <>, <>, <>, <>, <>, hash7, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy'])
(hash7, [35, 'coin'])

小结

MPT 是以太坊中的重要的数据结构，单个区块中的交易及其对应的交易、以太坊的世界状态、智能合约数据等，都使用了 MPT 的数据结构，并将这些 MPT 的根哈希值存储到了以太坊的区块中，用于数据防篡改和验证。

MPT 基于压缩的前缀树基数树构建，更加节省空间；同时，MPT 提供了方便的数据验证能力，使得只需要得到真实可信的 rootHash，就可以对树中的信息进行验证（同时，验证时不需要获取整棵树，只需要展开相关路径即可，使得验证过程更为简单），为数据提供防篡改的能力。

参考资料

Patricia Tree · ethereum/wiki Wiki
以太坊MPT原理，你最值得看的一篇

FEATURED TAGS
Blockchain Ethereum
FRIENDS