Ethereum 设计准则<<三>>Merkle Patricia Tree

Merkle Patricia Trees

Merkle Patricia Trees(简写MPT) 这个数据结构是由 Alan Reiner 在Ripple协议中设计并实现的. MPT 是以太坊中最基础的数据结构之一, 它被用来存储一个区块中所有的账户状态,交易,收据等等. MPT 是 Merkle 树和Patricia 树的组合. Patricia 是 "Practical Algorithm To Retrieve Information Coded In Alphanumeric"的缩写. 本质是一个基数树(Radix). 其特点是每个节点可以存储一个字符串,整体可以保持字典序. 有兴趣的可以参考 Spec[1]

MPT 兼备了MT 和PT 两种数据结构的属性:

所有的唯一的 key/value 对 映射到一个根哈希值. 这样在一个给定的字典树中, 一个key/value 对的身份无法被造假(除非攻击者有超过2^128的算力)( 其实就是说hash值长度是128bits?)

允许在对数时间复杂度内 更改/添加/删除 一个 key/value 对.

MPT为整个状态树提供了一个高效/易更新的"指纹".

MPT的具体设计包含:

具有两大类节点. kv(叶子) 节点, diverge(含分支,扩展两子类) 节点. kv 节点允许key存储多个四元组(nibble),最大长度是 64个四元组亦即 32 Bytes. 在传统的基数树碰到稀疏树以及不平衡树的情况下可以大大降低树的高度.

设置diverge 节点为16叉树而不是二叉树. 这个设计是为了提高查找效率,但是是一个次优方案. 16叉树可以被二叉树设计范式替换,但是考虑到实现的复杂度比较低,仍然留用.直到版本1.1后会考虑重构.

不区分空值和空哈希值. 这是一个简化的设计. ethereum 系统中缺省值都为0, 空字符串也被表达为0, 但是我们认识到这样做会失去一般性因此是个次优设计.

区分终结和非终结节点.单纯从技术上来说是没有必要在key 前缀中加入终结标志. Ethereum 字典树所采用的key都是静态长度. 采取这样的设计是希望使得它具有一般性, 可以被其它的密码学协议重用.

使用sha3(k) 作为"安全树"的键值. (主要用于在状态/账户的存储树中(智能合约代码)). 这样做主要是使得攻击者无法构造拒绝服务攻击. 可能的攻击路径是构造一个由分支节点构成的深度为64的不可折叠的链条并反复的调用Sload,Sstore指令. 因为sha3(k)会使得构造这样特殊的key异常困难. 因为特定的key.attack模式要匹配到sha3(k.orig), 找到k.orig 是非平凡的工作.

后面附上一个MPT的例子. 下一节我会详细的分解 MPT的spec

[1]https://github.com/ethereum/wiki/wiki/Design-Rationale#merkle-patricia-trees