如何存储Merkle树

苗，由树根长出树干，树干长出树枝，树枝又长出叶子，最后就这样长成了参天大树。计算机界也有棵树，名叫 Merkle，由一个根节点、一组中间节点和一组叶子节点组成。根节点表示是最终的那个节点，且只有一个。叶子节点可以有很多，但是无法再继续扩散出更多的子节点了。这棵树有什么神奇的作用呢？

01 引言

Merkle 树是一种树型数据结构，其叶子节点是数据块的 hash 值，而非叶子节点是其对应子节点 hash 值串联后字符串的 hash 值。利用 Merkle 树，能够在只有部分数据块的情况下校验数据完整性。因此，Merkle 树通常可以用于 p2p 网络等场景中，从不可信的数据源中取得数据，对数据一边进行同步，一边进行校验。在这些场景中，Merkle 树的引入可以避免对整个大数据集同步完后校验出错，不得不丢弃所有数据，而浪费带宽的问题。

对于区块链平台，客户端通常只需要关注自己账户的信息。在这种情况下，如果客户端完整地同步所有账本信息，效率将会十分低下。因此，在区块链中，一般引入 SPV （Simple Payment Verification） 验证技术，通过构造 Merkle 证明，客户端只需要同步部分数据，就可以达到验证相关数据的目的。这会极大地节省存储空间，减轻终端用户存储和网络传输的负担。

在 Ontology 中，Merkle 树也有不少应用场景，其中之一就是将每个区块的交易根作为叶子节点，构造出一个区块 Merkle 树，用于提供交易上链的存在性证明。本文主要描述 Ontology 在实现 Merkle 树时的相关优化细节。

02 Merkle 树数据结构的存储

在大多数区块链中，Merkle 树一般用在单个区块里，由多个交易的 hash 值作为叶子节点构成。

而在 Ontology 方案中，由于区块 Merkle 树是随着区块高度的增长进行动态增量增长的结构，因此要更加复杂。这就涉及到如何存储 Merkle 树的问题。一般来说，可以考虑如下三种方案：

方案1：内存存储

该方案就是把 Merkle 树存储在内存中。该方案存在两个缺陷。首先，由于没有进行持久化存储，在节点关机重启时，需要遍历所有区块，重新构造出完整的 Merkle 树，相对耗时；其次，随着交易和区块的增长，Merkle 树不断增大，内存的占用也会线性增长，影响扩展性。因此，内存存储方案并非长久之计。

方案2：k-v 型数据库存储

该方案就是把 Merkle 树存储在 k-v 型数据库 （如 LevelDB） 中。由于 k-v 的关系比较简单，用来表示树形关系结构，需要对 key 和 value 进行特定的编码，同时对具体的树节点的检索也需要多次读取，其整体效率比较低下。

方案3：文件存储

由于 Merkle 树的节点都是长度固定的 hash 值，如果能够将树的节点和整数值进行一一映射，那么就可以将整个树压缩为一维数组。要访问特定的树节点时，可以先将其对应的整数值算出来，并将它作为数组的下标，就可以拿到树节点的数据。将这个数组存储在文件里就可以解决树线性增长的问题。

树节点和整数进行映射的方式有多种，最直观的就是根据树的深度一层层编号，然而这种方案有一个问题：树的大小改变后节点的编号和其原先的编号会不一致，导致需要把数据全部读取出来，再按新的编号进行保存，将会大大降低效率。因此，找到一种稳定的节点编号方式是该方案可行的关键。

03 Merkle 树的更新和节点编号策略

采用文件存储的方案除了需要稳定的节点编号方式外，还有另一个问题。由于不断有新的区块节点插入，会导致 Merkle 树节点需要频繁更新，也就是说需要对存储文件进行不停地改写，这也会导致效率降低。

更为复杂的是，这需要一种数据一致性处理机制。我们考虑这样一种场景，在将树节点更新到一半时，区块链节点突然宕机，那么文件里存储的 Merkle 树数据就会产生不一致。

通过对 Merkle 树节点插入的观察可知，Merkle 树中存在两类节点：一种是会随着后续节点的插入，节点值会改变的临时节点；另一种是不会随后续节点插入而改变的恒定节点。不难证明，成为恒定节点的条件是当该节点及其子孙节点构成的子树是一个完全树。另外，临时节点的个数较少，只有 log（n），且可以由恒定节点计算出来，持久化后会因后续节点的插入立马改变。

所以，在 Ontology 的方案中，文件里只保存了恒定节点。同时，一个巧妙的地方是，按恒定节点出现的顺序进行编号，正好就是一种稳定的编号方案。在这种情况下，对文件只有 append 操作，也就避免了因文件改写而导致的数据不一致的问题。

04 Merkle 树的压缩表示

由于恒定节点不变的特性，也就是说其子节点对后续 Merkle 树更新不会有贡献，因此对于那些只需要计算最新的 Merkle 根 hash 值，而不需提供构造证明服务的节点，可以只保存 log（n） 个子完全树的树根节点。这可以代表整个 Merkle 树的状态，同时可以使整个树的存储降至 log（n），方便存储在 LevelDB 的一个 key 中，Merkle 树的更新只需一次读写。其结构定义如下：

type CompactMerkleTree struct {

hashes ［］common.Uint256

treeSize uint32

}

计算 Merkle 树的根 Hash

根据压缩 Merkle 树的定义可知，只需要将 hashes 数组中的 hash 值从右向左依次 fold 计算，即可拿到根 hash。算法如下：

func （self *CompactMerkleTree） Root（） common.Uint256 {

if len（self.hashes） == 0 {

return hash_empty（）

}

hashes = self.hashes

l ：= len（hashes）

accum ：= hashes［l-1］

for i ：= l - 2; i 》= 0; i-- {

accum = hash_children（hashes［i］， accum）

}

return accum

}

其中，hash_empty 函数返回空 hash，hash_children 函数返回两个子节点 hash 对应的父节点 hash 值。

插入新的叶子节点

当有新的叶子节点插入时，会根据 Merkle 树当前状态对该树进行动态更新。插入新的叶子节点算法如下：

func （self *CompactMerkleTree） Append（leaf common.Uint256） {

size ：= len（self.hashes）

for s ：= self.treeSize; s%2 == 1; s = s 》》 1 {

leaf = hash_children（self.hashes［size-1］， leaf）

size -= 1

}

self.treeSize += 1

self.hashes = self.hashes［0:size］

self.hashes = append（self.hashes， leaf）

}

05 Merkle 树增大过程的相关数据变更示意图

Merkle 树在增长过程中，存储在文件中的 hash 值数据和其对应的压缩表示数据变更示意图如下。

图一是 Merkle 树单个节点时的状态：

当在该 Merkle 树中插入另外一个节点 b 时，树的大小增加了1。同时，新节点 b 可以和原节点 a 串联后，计算 hash 值得到 c：

当在该 Merkle 树中再插入另外一个节点 d 时，由于已存在节点形成一棵完全树，因此压缩表示时只要简单加入 d 即可。

下面的图表示了 Merkle 树节点从3个增加到7个的情况。小伙伴们可以根据我们的存储策略进行推导。

06 结论

Merkle 树在很多应用场景中都有着广泛应用。在 Ontology 中，Merkle 树的一个应用场景就是将每个区块的交易根作为叶子节点，构造出一个区块 Merkle 树，用于提供交易上链的存在性证明。

在不需要提供证明服务的情况下，可以使共识节点的性能和存储能力得到极大提升。Ontology 在实现区块 Merkle 树的过程中，只将区块 Merkle 树的关键节点进行存储。通过这种方法，我们只读写一次 LevelDB 就可以更新 Merkle 树，计算复杂度达到 O（log n）。

另外，在需要提供证明服务的情况下，Ontology 实现的方案可以避免频繁地读写数据以及维护树的关系，只需要对相关文件进行 append 操作，极大地简化了数据一致性的容错设计。