深入理解以太坊系列(9): Merkle Patricia树

Merkle Patricia树(MPT)是以太坊的主要数据结构。在以太坊每个区块头中,存有三个根值。stateRoot(用于存储所有账户状态)、transactionsRoot(用于存储区块中的交易数据)、和receiptsRoot(用于存储区块中的收据数据),他们都使用了MPT数据结构。所有在以太坊中使用的Merkle树实际上都是MPT。

MPT是Merkle树和Patricia树的结合,其结构具有以下特性:
高安全性:每个唯一键值对唯一映射到根的哈希值。难以破解(除非攻击者有~2^128 的算力);
易修改性: 增、删、改键值对的时间复杂度是对数级别。

在以太坊设计原理中具体的描述了MPT设计时曾做出过的一些决策:
1. 有两类节点
KV节点和离散节点。KV节点的目的是为了提高效率。如果在特定区域树是稀疏的,KV节点可作为一个“快捷方式”,代替深度为64的树。

2. 离散节点是16进制,不是二进制
目的是为了让查找更有效率。但现在认识到这种选择并不理想,因为16进制树的查找效率在二进制中可以通过批次存储节点来模拟。

3. 空值(empty value)与非会员(non-membership)之间没有区别
为了简化逻辑,以太坊中未设置的值默认为0,空字符串也用0表示。然而,这样做牺牲了一些通用性,因而并不是最优的。

4. 终节点和非终节点的区别
技术上,标识一个节点“是否是终节点”是没必要的,因为以太坊中所有的树都被用于存储静态密钥长度,但为了增加通用性,我们还是会添加这个标识,以期望以太坊的MPT的实现方式能够被其他加密货币原样采纳。

5. 采用SHA3(k)作为密钥(在状态树和账户存储树中使用)
使用SHA3(k),通过设置离散节点的链的深度为64,以及反复调用SLOAD 和 SSTORE指令,使那些企图对树采取DoS攻击的行为变得非常困难。不过,这也让穷举树的节点变得困难,如果你希望你的客户端有穷举的能力,最简单的方法是维持一个sha3(k) -> k的数据库映射。