updated:

详解以太坊Merkle Patricia Tree

项目地址

虚假的形式化定义（误

我们首先给出Merkle Patricia Tree（以后称为Trie）的形式化定义，然后研究这样的定义背后的设计目的：

首先，Trie的作用其实并不是仅仅是提供键值对之间的映射，而是提供一个32 byte的序列或空序列到一个键值对集合的映射:

（

其中为一个键值对的键，为一个键值对的值。

特别的，键的表示形式为4位整型序列（nibbles），我们可以通过将原本键的每一个字节拆成高4位和低4位来得到这样的序列。

后面我们会看到，这些所有的键值对构成了一个类似radix tree的数据结构，我们定义这棵树的节点为，其中表示对于一个键值对，若在该子树中，那么该子树中对应的键为。不难看出，代表整颗树的根。

该集合对应的32 bytes值表示为

其含义为：首先将该集合对应的radix tree的根节点使用RLP编码，然后使用Keccak256算法求哈希，得到的值便是该集合对应的32 byte键。该键被称为Trie的根哈希，得益于Keccak256哈希算法的抗碰撞性，我们可以认为一个根哈希可以决定唯一的一个Trie。

  • Keccak256的有关资料参见这里
  • RLP（Recursive Length Prefix）编码是一种能将任意结构化数据编码为二进制表示的二进制编码，该编码在以太坊黄皮书的附录B中同样有形式化定义。笔者在该项目中使用了自己编写的RLP序列化和反序列化serlp

接下来我们研究上面提到的radix tree节点的形式化定义：

首先定义一个键值对集合中键的最长共同前缀的长度表示为：

那么的定义为：

可以看到，这是一个递归定义，表示当前层的子树中包含的键值对，其大小在递归的过程中递减。我们可以看到该式定义了三种类型的节点，从上到下分别是LeafNode, ExtensionNode, BranchNode。我们通过一个例子进行解释：

假设有下面的键值对集合：

1
2
3
4
5
6
{
    (01e45a, 1),
    (01f45a, 2),
    (01058c, 3),
    (01, 4)
}

这些键值对构造出的radix tree如下：

可以看到，我们按照上述定义将这些键值对插入树中，最后所有数据在逻辑布局上都存在于根节点中，对根求hash后根hash到该树的映射构成一个Trie，我们可以保证对该树的任何修改操作都会导致根hash改变，因此我们可以保证该数据结构的不可篡改性。

同时我们可以发现，Trie是一个functional data structure，我们的每一次修改都创建了一个新的Trie（因为根hash发生了变化），因此只需要将根hash和对应的树插入到一个键值数据库中，并且在之后的每次修改后都插入新的hash和新的树，那么只要知道过去某个状态下Trie的根hash，我们就能回退到当时的状态。

真实的形式化定义

看了上面的形式化定义，我们惊讶的发现所谓的Merkle Patricia Tree居然仅仅是一个radix tree加上了一个哈希。但仔细思考后我们会发现下面几个问题：

  1. 我们每次更新Trie中存储的数据时，即使是仅仅更新了一个字节，也需要对一整棵树进行拷贝，以此保证我们总是能回退到过去的状态
  2. 这个定义漏掉了对空子树的表示，我们从定义中找不到前面例子中BranchNode中没有子树的几个位置存有什么数据。
  3. 将nibbles存储到数据库中时每4个比特位都要占用一个字节的空间，导致了一倍的空间浪费。

再回头看之前的定义，可以发现它最大的问题是将所有数据在逻辑上存放在了一处，这导致任何操作都是对整体的操作。下面的定义通过新引入的一个结构将Trie从一个整体分割成了多个小Trie的集合：

其中：

可以看到，该定义大致有两处修改：

  1. 我们使用了一种被称为hex-prefix 的编码对nibbles进行编码，它将两个nibble编码成为一个字节。同时能够编码进一些额外的数据（例如节点的类型）。详细的形式化定义在以太坊黄皮书的附录C中。
  2. 我们额外引入了一个函数，该函数的形式化定义解释如下：
    1. 当子树为空时，将其表示为，注意这个值可以认为是空字符串，其RLP编码为0x80.
    2. 当子树的RLP编码长度小于32位时，我们直接将其嵌入到父节点中
    3. 当子树的RLP编码长度大于等于32位时，我们将该子树的根哈希作为键，子树的RLP编码作为值存放在数据库中，然后仅仅在父节点中保存该根哈希。

的结果为32字节，推测32这个临界值是由此而来，这样反序列化RLP编码的数据时我们就可以仅凭数据的长度判断它是根哈希还是一颗被嵌入的子树。

不难看出，每一处修改都对应解决了上面提出的问题。最重要的修改笔者认为是当子树过大时将其单独存放在数据库中，而仅仅在父节点中存放其索引。这一修改直接将原本不可分割的Trie变成了多个小Trie的组合（这些小Trie存放在一个键为根哈希，值为树的RLP编码的数据库中）。这保证下面几个特点（假设所有的子树都没有嵌入父节点，这样的情况极为常见）

  1. 在更新或插入数据时，我们仅仅需要更新查找路径上的几个节点，而不是整个Trie
  2. 没修改过的节点会在Trie的不同版本之间共享
  3. 从磁盘加载Trie时可以按需加载，如果一个值没有被访问到，那么它永远不会被加载到内存中

实现Trie

实现Trie的过程不过多赘述，直接严格按照形式化定义进行实现即可。注意到我们要实现的Trie是一个functional data structure，使用函数式编程思想进行实现会更为顺利。

重点逻辑

数据类型基本照抄形式化定义即可，其中定义中的对应的数据结构比较重要：

1
2
3
4
5
6
pub(crate) enum Subtree {
    /// this field will be encoded into 0x80 with RLP encoding
    Empty,
    Node(Box<MptNode>),
    NodeKey(KecHash)
}

实际上，在我们插入值时，不管子树的RLP编码大小是否大于32字节，都会被插入到Subtree::Node中，这是为了保证在对树频繁操作时所有数据都在内存中，我们只要保证数据持久化到数据库中后严格按照形式化定义即可。在数据的持久化过程中，我们会对Trie的根节点调用node_collapse方法，该方法会递归将所有过大的子树折叠到数据库中，然后为相应的子树返回一个Subtree::NodeKey：

1
2
3
4
5
6
7
let (dbkey, rlp) = node_collapsed.encode();
// after collapsing, a node either keeps unchanged, or part of it is committed to database,
// in the later case, the node must contains a database key, whose length is 32
// so the rlp length of collapsed node must exceed the 32 byte limit
assert!(rlp.len() >= 32);
db.insert(&dbkey, rlp);
Subtree::NodeKey(dbkey)

最后，不管根节点的大小是多少，我们都将其存入数据库，将其根哈希作为Trie根。

其余的按照定义来就好咯～

测试

最后，我们选取一个以太坊公链上的区块对我们的实现进行验证（这里使用的样例参考了merkle-patricia-trie）：

测试代码在这里，测试使用的区块在这里。运行测试可以看到测试通过，不再赘述。

https://github.com/M4tsuri/mpt-rs/blob/main/tests/test_proof.rs也提供了对revert的测试。

Merkle Proof

到这里，我们还没有提到Trie带来的另一个巨大的优势，我们首先提出下面这一问题：

我们知道，以太坊的世界状态是一个从账户地址到账户状态的映射，这些映射构成的键值对集合便存放在trie中。然而目前以太坊的世界状态的大小数量级已经达到了100GB，让每个人都保存一份这样的数据以进行查询显然是不现实的。

那么我们思考能否将世界状态放到一些特定的节点上，当我们想要验证某个账户余额时，只需向这些节点进行查询即可。然而稍加思索便可以意识到这样的操作在不可信的环境下极为脆弱，我们必须能够验证这些节点返回的数据是否正确。实际上我们的Trie实现已经解决了这个问题，即Merkle Proof的构造，它构成了以太坊中light node存在的理论基础。

假设用户需要某个保存有全部世界状态的节点向我们证明某个账户的存在性，同时用户手中只有当前世界状态的根哈希，那么用户只需发出一个包含该账户地址的请求，该节点收到该请求后会进行Merkle Proof的构建。首先，它会创建一个空的KV数据库ProofDb，然后从根节点开始查找该键，并且在将查到过程中途径的所有子树都放到ProofDb中，最后返回ProofDb给用户。为了对Merkle Proof进行校验，用户使用自己保存的世界状态根哈希在ProofDb中查找根节点并构建Trie，这个Trie是世界状态的一个仅包含所请求账户的子集，用户在其中查找该账户，若查找结果与Proof结果相同，说明验证成功。

此方案的有效性在于根哈希可以证明子树的有效性，子树中保存的哈希进一步证明了子树的子树的有效性。因此只要用户信任自己保存的根哈希以及哈希算法的抗碰撞性，就可以建立起一条信任链。

一个示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#[test]
fn test_proof() {
    let a = "a".to_string().repeat(1);
    let b = "b".to_string().repeat(20);
    let c = "c".to_string().repeat(35);
    let d = "d".to_string().repeat(400);

    let mut trie: Trie<MapDb, _, _> = Trie::new();

    trie = trie.insert(&"aaaa", &a);
    trie = trie.insert(&"aaaab", &b);
    let old_root_hash = trie.commit().unwrap();
    trie = trie.insert(&"aaaa", &c);
    trie = trie.insert(&"aa", &d);
    let new_root_hash = trie.commit().unwrap();

    // proof of existence 
    let (proof, exists) = trie.prove::<MapDb>(&"aaaa");
    assert_eq!(exists, true);
    // verify with old hash, this should fail
    assert!(!verify_prove(&old_root_hash, &proof, &"aaaa"));
    // verify with the newest hash, should success
    assert!(verify_prove(&new_root_hash, &proof, &"aaaa"));

    // proof of non-existence
    let (proof, exists) = trie.prove::<MapDb>(&"a");
    assert_eq!(exists, false);
    // both should fail
    assert!(!verify_prove(&old_root_hash, &proof, &"a"));
    assert!(!verify_prove(&new_root_hash, &proof, &"a"));
}

捐赠

如果本文为你带来了帮助，可以向m4tsuri.eth转账进行捐赠:)

← Prev 智能合约中的函数调用 | 编译原理前端基础知识 Next →