详解以太坊中的Merkle Patricia Tree（一）

type

status

date

slug

summary

需求背景

以太坊的数据结构主要包含两个核心部分：世界状态（World State）和区块（Block）。世界状态是以太坊在某一时刻所有账户的状态集合，包括两种类型的账户：

外部账户（EOA, Externally Owned Account）：由用户控制的账户，拥有私钥

合约账户（Contract Account）：由智能合约代码控制的账户

而区块则记录了导致状态变化的所有交易信息。大致的结构如下：

以世界状态为例，针对所有账户的数据，其数据结构至少需要满足以下两个需求：

高效地写入和查询

高效可靠地验证

虽然我们已经知道以太坊中最终使用了Merkle Particia Tree作为组织这些数据的数据结构，但是为了理解选择这个数据结构的理由，不妨对比HashMap这种简单的数据结构，从而更加清晰地了解Merkle Particia Tree的优势所在。

为什么不用HashMap

之所以以HashMap作为对比，是因为它在基础数据结构中具有O(1)的读写性能，看似是一个不错的选择。以账户数据为例，我们可以构造如下的HashMap：

如果要查询和写入某个地址的余额，其操作都是O(1)级别的复杂度，因而基本能够满足需求1，高效的写入和查询

但是在以太坊中，共识机制是必须的。以世界状态为例，假定有两个节点各自维护着一份世界状态的HashMap：

Address	Balance
address1	balance1
address2	balance2
address3	balance3

Address	Balance
address1	balance1'
address2	balance2'
address3	balance3'

如何验证这两组世界状态是否一致呢？只能通过逐行比较。针对每一个地址都相应地比较自己和对方的余额是否一致，这个过程的时间复杂度为O(N)。但是在以太坊的世界中，存在着大量账户以及频繁的交易。每一笔交易都会导致世界状态的变化，针对一笔交易就必须完整地遍历所有的账户做验证，这样的实现方式显然是不可取的。

第二个问题是，以太坊中的节点分为全节点和轻节点，全节点拥有完整的世界状态数据，而轻节点则没有，因此轻节点无法实现这种遍历全量数据达成共识的方式。

此外，世界状态不光是当前状态，也需要能够随时查阅历史状态。如果对于每一笔交易，都是直接更新当前的HashMap，那么历史状态就得不到保存。要保存历史状态，则必须将当前的HashMap快照存储后再更新。这必将导致大量的数据冗余，无法高效地利用存储空间。

最后一个关键的问题是，假设有一个新加入以太坊网络的节点，需要获取当前的世界状态，必然需要向网络中的其他节点请求。那么应该如何防止收到的数据不是被恶意篡改的呢？假定世界状态中有两个账户：

但是恶意节点传输过来的世界状态数据是：

为了防范恶意节点，就需要同时比较多个节点所发送过来的数据，而且要确认数据正确性至少需要51%的节点发来的全量数据都是相同的。这种验证方式增加了太多无谓的网络和计算资源的开销。

因此，在以太坊的场景中，使用HashMap这种简单的数据结构其缺陷在于：

每次验证共识的过程时间复杂度为O(N)，无法支持高频大规模的数据验证

轻节点难以高效工作，因为需要获取和验证全量数据

存储历史数据时空间开销过大

防范恶意节点和数据正确性验证的成本过高

引入Merkle Tree

Merkle Tree基本结构

Merkle Tree（默克尔树）是由Ralph Merkle在1979年发明的一种数据结构。它是一种树形数据结构，每个叶子节点存储数据的哈希值，而每个非叶子节点存储其子节点哈希的组合哈希。

以世界状态为例，Merkle Tree中叶子节点为每个账户的信息，非叶子节点均为哈希值。构造的过程如下：

针对每个账户状态计算出其哈希值

针对这些哈希值两两组合，再计算出哈希值

循环往复，直到计算出根哈希值，最终构成一个树形结构

基于哈希的树形结构，几乎完美克服了简单的Hashmap在以太坊场景下的缺陷：

快速数据验证。整棵树中只要稍有变动，就会反映到根哈希的变动，因此可以通过根哈希的比较快速验证数据是否被篡改，这个过程为O(1)，而HashMap为O(N)

轻节点可用。因为只需要比较根哈希，而不是全量账户数据，使得轻节点也能正常工作

存储空间优化。假定Account4的状态变化了，则会形成如下的Merkle Tree：

这棵新的Merkle Tree中，实际上只有四个节点发生了变化，即Account4'， Hash4'，Hash34'和Root Hash'，剩下则都是复用了之前的节点。没有变动的数据总是只有一份，被多个历史状态引用，相较于HashMap每次都需要快照全量数据，节省了很多空间。

高效的密码学证明。如前文所述，HashMap是无法廉价且安全地验证其他节点发来的数据是否被篡改。但是在Merkle Tree下则可以轻松地做到这一点，验证过程如下：

当前节点拥有世界状态的根哈希值，并能够确定其正确性（具体如何确定并并与本文内容强相关，所以请假定它就是正确的）
其他节点发来某个账户的状态，以及验证路径，这个路径被称作Merkle Proof
当前节点按照验证路径验证计算出根哈希值，与自己持有的根哈希值对比，如果一致，则数据正确无误。不一致则视作被篡改

以上图为例，要验证其他节点发来的Account(0x123)的状态是否正确，只需要计算几次哈希值最后比较根哈希即可，这大大减少了对与网络中其他节点的依赖，不需要在100个人中有51个人告诉你这是真的你才敢相信。同时，这个验证过程实际上不需要获取node3和node4的数据，只需要知道它们的哈希值branch2，相比与HashMap的全量数据比较，Merkle Tree的验证过程显然高效得多。

需要额外考虑的情况

有序性

基本的Merkle Tree还有一个重要的问题，即在计算哈希值时，Hash(A, B)和Hash(B, A)的结果并不一定相等。因此参数的顺序会直接影响最终的根哈希值。所以，在实现Merkle Tree时，还需要将叶子节点按照一定的规则排序。我们可以假定，在世界状态中，按照每个账户的地址大小进行排序，再两两组合计算哈希，那么只要数据一致按照这个规则最终得到的根哈希值就必然是相等的。

奇数个节点

如果世界状态中的账户数量为奇数，两两组合时会剩下一个孤立的节点，此时可以将这个节点复制一份，与自身进行哈希

代码实现

实现思路

需要一个节点类，或用于表示叶子节点即账户状态，或用于表示非叶子节点即哈希值

需要一个Tree以组织节点实例，并提供如下方法

新增叶子节点，即向世界状态中添加一个账户状态
更新叶子节点，即更改世界状态中的某一个账户状态
验证，即给定根哈希和Merkle Proof，校验数据正确性

Java示例

Node类

BasicMerkleTree类