Authenticated Dynamic Dictionaries in Ethereum

1、Merkle Tree

Merkle Tree 是利用Hash对内容的正确性进行快速鉴定的数据结构,其结构示意图如下:

  • Merkle Tree 父节点包含所有子节点的Hash值;

  • Merkle Tree 的Tree可以是任何形式的Tree,任何经典的tree构造算法都可以经过简单的修改应用到Merkle Tree上;

  • Merkle Tree的Branch Node也可以存储数据,尽管大多数实现中只在Leaf Node上存储数据;

  • Merkle Tree对单个数据的校验最多需要 $O(h)$ 时间,其中 $h$ 为树高,如果树足够平衡,则验证单个节点的复杂度为$O(\log(n))$.

在BitCoin中,Merkle Tree主要用来实现轻节点,轻节点只存Top Hash,当轻节点要验证一笔交易时(比如上图中的L4),则向存有全部数据的完全节点验证,完全节点将L4到root的路径上的所有node(1-1,1-0,1,0,Top Hash),轻节点对根据这条路径计算得到Top Hash,如果计算得到的Top Hash与本地的Top Hash相等,则轻节点就可以相信完全节点传过来的数据。

在Ethereum中,Merkle Tree除用来实现轻节点外,还用来实现增量存储。

2、MPT

为了能够支持高效的检索及动态的插入、删除、修改,Ethereum使用Trie来构建Merkle tree,Ethereum将其命名为Merkle Patricia Tree(MPT),其示意图如下:

Ethereum使用的是一棵16叉Trie树,并进行了路径压缩。可以将其理解为一棵普通的Trie树,只不过指向子节点的指针变成了子节点的Hash。

2.1 Node类型

MPT有三种类型的节点,分别是:Leaf Node、Branch Node、Extension Node。Leaf Node 由一个Key域(nibbles,key的片段)及数据域组成;Branch Node 由分支域(16个指向下一个节点的指针,这里的指针可以理解为KV数据库中的Key)及数据域(如果存有数据,则此数据的Key是从根到达该Node所经过的所有nibbles)组成;Extension Node由Key域(Shared nibbles,这实际上是对路径进行压缩,否则路径的长度就是key的长度,在Node数量不多的情况下,树会非常的不平衡)及分支域(指向下一个Branch Node的指针)组成。

Parity中MPT定义如下:

enum Node {
	/// Empty node.
	Empty,
	/// A leaf node contains the end of a key and a value.
	/// This key is encoded from a `NibbleSlice`, meaning it contains
	/// a flag indicating it is a leaf.
	Leaf(NodeKey, DBValue),
	/// An extension contains a shared portion of a key and a child node.
	/// The shared portion is encoded from a `NibbleSlice` meaning it contains
	/// a flag indicating it is an extension.
	/// The child node is always a branch.
	Extension(NodeKey, NodeHandle),
	/// A branch has up to 16 children and an optional value.
	Branch(Box<[Option<NodeHandle>; 16]>, Option<DBValue>)
}

enum NodeHandle {
	/// Loaded into memory.
	InMemory(StorageHandle),
	/// Either a hash or an inline node
	Hash(H256),
}

注意此处的NodeHandle,我们可以只用H256来作为指向下一个节点的指针,这完全可行且符合协议,但是每次找子节点都要从数据库中查询势必会带来效率上的问题,Parity采用了一个非常巧妙的办法,将查询过的Node都存放到内存中,下次需要找这些节点时直接用指针访问就好。当然,将其存到DB中时还是要将InMemory(StorageHandle)转化成H256格式,实际存储格式如下:

pub enum Node<'a> {
	/// Null trie node; could be an empty root or an empty branch entry.
	Empty,
	/// Leaf node; has key slice and value. Value may not be empty.
	Leaf(NibbleSlice<'a>, &'a [u8]),
	/// Extension node; has key slice and node data. Data may not be null.
	Extension(NibbleSlice<'a>, &'a [u8]),
	/// Branch node; has array of 16 child nodes (each possibly null) and an optional immediate node data.
	Branch([&'a [u8]; 16], Option<&'a [u8]>)
}

2.2 操作

除了最基本的增删改查操作以外,Parity还有一个commit操作,该操作允许只有在调用commit时才重新计算Hash并写入数据库,这使得如果一个node被多次访问,这个node只重新计算一次Hash,重新写入数据库一次。

commit的另一个好处是在交易执行完之后再计算Hash,这相当于做了路径聚合,去掉了重复无用的Hash计算,减少了Hash的计算量。目前Parity在每个交易执行完毕后都会调用commit(),在我们的实现中将commit操作移到了块中所有交易完成以后,提高了效率。自EIP98以后,transaction下的state root已经成了可选项,相信不久Parity也好把commit移到块中所有交易执行完之后。

/// Commit the in-memory changes to disk, freeing their storage and
	/// updating the state root.
	pub fn commit(&mut self) {
		trace!(target: "trie", "Committing trie changes to db.");

		// always kill all the nodes on death row.
		trace!(target: "trie", "{:?} nodes to remove from db", self.death_row.len());
		for hash in self.death_row.drain() {
			self.db.remove(&hash);
		}

		let handle = match self.root_handle() {
			NodeHandle::Hash(_) => return, // no changes necessary.
			NodeHandle::InMemory(h) => h,
		};

		match self.storage.destroy(handle) {
			Stored::New(node) => {
				let root_rlp = node.into_rlp(|child, stream| self.commit_node(child, stream));
				*self.root = self.db.insert(&root_rlp[..]);
				self.hash_count += 1;

				trace!(target: "trie", "root node rlp: {:?}", (&root_rlp[..]).pretty());
				self.root_handle = NodeHandle::Hash(*self.root);
			}
			Stored::Cached(node, hash) => {
				// probably won't happen, but update the root and move on.
				*self.root = hash;
				self.root_handle = NodeHandle::InMemory(self.storage.alloc(Stored::Cached(node, hash)));
			}
		}
	}

	/// commit a node, hashing it, committing it to the db,
	/// and writing it to the rlp stream as necessary.
	fn commit_node(&mut self, handle: NodeHandle, stream: &mut RlpStream) {
		match handle {
			NodeHandle::Hash(h) => stream.append(&h),
			NodeHandle::InMemory(h) => match self.storage.destroy(h) {
				Stored::Cached(_, h) => stream.append(&h),
				Stored::New(node) => {
					let node_rlp = node.into_rlp(|child, stream| self.commit_node(child, stream));
					if node_rlp.len() >= 32 {
						let hash = self.db.insert(&node_rlp[..]);
						self.hash_count += 1;
						stream.append(&hash)
					} else {
						stream.append_raw(&node_rlp, 1)
					}
				}
			}
		};
	}

注:Node在存入数据库之前都要先经过RLP序列化,Node从数据库中取出时要先反序列化。

2.3 FatTrie & SecTrie

Parity对上面的TrieDB进行了一层封装,分别是SecTrie与FatTrie。SecTrie对传进来的Key做了一次Sha3(),用Sha3()后的值作为Key,这样做的原因是:Trie并不是一棵平衡树,攻击者可以构造一棵极端不平衡的树来进行DDos攻击,用Sh3()后的值做Key,这极大增加了攻击难度,使构造极端不平衡的树几乎不可能。FatTrie除了对Key做Sha3()外,还额外将Sha3()前的Key存了下来。

2.4 回滚

被修改或删除的Node并没有从数据库中删去,通过其DBKey(Sha3)仍可以从数据库中取得,每个Block中都存了State Root,如果我们想回滚到某个Block时的State,我们可以通过State Root取出该Node,如果该Node是Leaf Node,则回滚完成;如果该Node是Branch Node或Extension Node,那么该Node中存储了其子节点的DBKey,通过DBkey从数据库中取出其子节点然后进行相同的操作即可。回滚涉及大量的数据库操作,我们可以通过设计数据库缓存来提高效率,幸运的是回滚并不经常发生。

2.5 垃圾回收

意识到过老的Block的旧Node(被更新或被删除的Node)是没用的(没人会丧心病狂到向前回滚1000个块),定期的做垃圾回收可以减小数据库的体积,提高数据库检索效率。目前的方案有:

  • 遍历最近1000个Block的所有的Node并标记,将未标记的Node删除;

  • 最近1000个Block的Node全部存在内存中,年龄超过1000的Blcok的Node如果仍被最近的1000个Block引用,则将其写入磁盘,否则丢弃。

2.6 并行操作

可以采用读写锁来实现。

3、Merkle AVL+ Tree

由于Sha3运算的开销并不低(约$15Cycles/byte$),为了提高效率,我们希望在每次更新树时能够计算Sha3的数量最少,而更新一个节点所需要重新计算的Sha3量约为$m\log_{m}n$,其中 $m$ 为分支数,故当 $m=2$ 时,Sha3的计算量最小。又AVL Tree的平衡性更好(尽管这意味着更多的旋转操作,幸运的是旋转操作并不增加Sha3计算),因此选用AVL Tree来构建Merkle Tree似乎是一个不错的选择,我们简称之为MAT。

3.1 Node 类型

为了简化操作,我们只在叶子节点存放数据(这样可以减少重新计算Sha3的量),MAT有两种类型的Node:Branch Node和Leaf Node:

/// Node types in the AVL.
#[derive(Debug)]
enum Node {
    /// Empty node.
    Empty,
    /// A leaf node contains a key and a value.
    Leaf(NodeKey, DBValue),
    /// A branch has up to 2 children and a key.
    Branch(u32, NodeKey, Box<[Option<NodeHandle>; 2]>),
}

Leaf Node由Key域(不同于MPT,这里存了完整的key)及数据域组成,Branch Node由Key域(这里仍然存储的是完整的Key,其Key与其子树中最左边的叶子节点的Key相同)及分支域(两个分支)组成。

3.2 操作

MAT支持的操作同MPT,不同的是为了保持树的平衡,会有LL、LR、RR、RL四种旋转操作。

4、对比

两种树更新一个node时所需的Sha3计算量对比如下图所示:

测试发现,当node数在$1000,000$时,MPT的平均路径长度为7,MAT的平均路径长度为20,可以推算MPT的Sha3计算量为$16 \times 7 = 112$,MAT的Sha3计算量为$2 \times 20 = 40$,这与上图数据吻合。

4.1 MPT存在的问题

  • trie并不是平衡树,这意味着攻击者可以通过特殊的数据构造一棵很高的树,从而进行拒绝服务攻击。(实际上这很难进行,因为在Ethereum中Key是经过Sha3后的值,想找到特定值的Sha3是困难的。);

  • 内存占用率高。每个Branch Node都16个子节点指针,大多数情况下其子节点的数量并不多;

  • 不易于编码。虽然MPT易于理解,但是编写却非常复杂,MPT的代码量比MAT要高出许多。

4.2 AVL+ 存在的问题

  • 不同的插入顺序得到的AVL Tree并不相同,这意味着不能像MPT那样将DB理解为内存模型,合约设计者必须意识到不同的写入顺序将带来不同的结果,也就是说,AVL天然的不支持合约内的并行;

  • 每个Node节点都存有完整的Key,Key的存储开销要比MPT大;

  • 每个Key的大小是256bit,Key最长可能要做32次u8比较,但从概率上来讲,大部分Node会在前几次比较就得出结果。

  • 由于AVL是二叉树,这意味着AVL的树高要比Trie树高,也就是说AVL操作DB的次数要比Trie树多,从而IO开销要比Trie树高。

由于IO开销,实际性能AVL要比Trie差:

4.3 Ethereum中存在的问题

Ethereum也使用MPT来保存transactions 和 receipts,但transactions 和 receipts 不是动态结构,没有删除与更新需求,没必要使用MPT,使用最简单的Tree来构建Merkle树即可。

5、结语

对性能影响最大的是IO及Sha3的计算,Sha3的计算除使树尽可能的平衡外,似乎并没有好的解决办法,但IO还有很大的优化空间,初步的想法是在内存中维护整个最新state tree,当node被修改时将修改前的旧node写入到缓存队列中,由另一个线程并行的写入到DB中,这样IO基本上不会对state tree产生影响。

但由于公有链会分叉,这使得在内存中维护State Tree变的比较困难, 正因如此,Parity在每次对Trie做新的操作事,都会重新从DB中读取node。但对于采用PBFT的联盟链,由于链不会分叉,可以考虑采用上面的方案优化IO。




参考:

improving-authenticated-dynamic-dictionaries.pdf

Measurements of SHA-3 finalists, indexed by machine

comments powered by Disqus