本文由 Poly Enterprise 团队出品

前情回顾

在上一篇《“无奈”的中本聪与梅克尔树的“多余”》的文章中， Poly Enterprise 团队介绍了梅克尔树的基本结构和生成节点的规则。在面对叶子节点不满足一棵满二叉树叶子数量要求的情况，中本聪的做法简单：直接复制最后一个节点，强行凑齐一棵满二叉树。虽然不胜优雅，但也解决了问题，引入的额外信息也通过UTXO的唯一编号来避免双花攻击。

梅克尔山脉的必要性

为了解释梅克尔山脉的必要性，我们需要回顾一下梅克尔树的弊端。梅克尔树使用的前提是已知所有的数据。同样的，为了声明一个区块之内的所有交易，也必须提前已知所有待声明的交易。SPV节点在获得区块头以后，便得知了关于此区块之内所有被记录的交易的声明，即梅克尔树根。

此时，即使SPV节点向不同的全节点去质询此区块记录的不同的交易，它依然有信心断定，自己依照证据所得出的结论同样有效。通过梅克尔树根，既能维持对交易记录完整性的承诺，又能保护SPV节点免受对单一全节点的依赖性，从而避免单一故障点风险。

梅克尔树根能够对“静态数据”提供完整性承诺，“静态”意味数据不增不减不变。举个例子，一部电影成品就可以看作是静态数据。当用户通过P2P网络下载一部电影时，首先向一个可信节点获取该电影文件的梅克尔树根，然后从其它陌生节点下载该电影不同的片段并在本地完成组合，只要计算组合文件的梅克尔树根依旧和信任节点提供的树根相同，那么即可确认该组合文件是完整且正确的。

但在区块链领域，“静态数据”并不常见，每一种链都在一直产生新的区块，即待声明的数据会不停地增加新的内容。此时，SPV节点为了缓解存储要求，选择只同步区块链的头，通过梅克尔树根去验证区块内交易的正确性。

随着行业的蓬勃发展，应用于不同场景的区块链项目日益增多。为了支持不同区块链之间的跨链交易，需要保存越来越多的不同的区块链的头部数据，验证节点所面临的存储压力会越来越大。

于是，斯坦福大学的博士生Benedikt等人在一篇发表于国际密码研究学会(IACR，密码学领域的顶级协会)的论文中提出了一种新型的区块头结构，其中一个字段用来保存梅克尔山脉的根哈希，通过某区块的MMR根哈希就能对此区块之前所有的区块信息做一次声明。这样，验证节点最终需要保存某区块链的最新区块即可，几乎可以说是颠覆了之前SPV节点所面临的困境。

下面来介绍一下基于梅克尔树的变体 —— 梅克尔山脉。

梅克尔山脉是什么？

Peter Todd发明了梅克尔山脉，他的思路是这样的：既然有时候会出现凑不齐一棵满二叉树的情况，那干脆就拆成几个高度较低的满二叉树(也就是山)，然后再通过山峰求取最后的根。父节点的生成规则是这样的：当同一高度出现左右2个兄弟节点，即合并生成1个父节点。而高度为0的最底层节点，即代表新增的数据。一个叶子数量为7的MMR结构如下所示：

从1开始，按照生成的顺序对节点进行编号。我们把每个满二叉树称作一座山，山顶的节点叫做山峰。最后按照从最低山峰向最高山峰的顺序，计算MMR的根哈希。在上例中，设最低峰为P11、次低峰为P10、最高峰为P7，则根哈希如下：

root = Hash(Hash(P11+P10) + P7)

当再来一个节点(编号为12)，则叶子数量为8的MMR结构如下所示：

此时根哈希即为最高峰P15。

root = P15

如果想要证明某叶子节点存在于MMR中，规则十分简单：

1. 构造子树从叶子节点到山峰的 merkle proof

2. 拱起右侧山峰，计算其mmr root，结果加入proof

3. 将左侧山峰依照自右向左的顺序加入proof

只要验证该节点最后依照证据能够计算获得相同的MMR根，即证明通过。

梅克尔山脉的应用

梅克尔山脉结构可以随着叶子数量的增长而动态变化，天然地适应了区块链不断出块的特点。假设以最新区块之前的所有区块作为叶子节点，其构成的MMR结构的根哈希保存在最新区块的头部。这意味着，每一个区块其实隐藏了之前所有区块的信息，即使不保存所有区块的头部，验证节点也能根据MMR根哈希判断最新区块是否有效。

假设当验证节点收到最新区块，为了证明该区块确实属于诚实最长链的最新区块，验证节点会继续向证明节点质询之前若干个区块(即叶子)的信息，证明节点必须提供关于被质询区块的MMR证据，用来证明该区块确实与最新区块同属于一条链。因为MMR根哈希承诺了之前所有的区块，恶意节点无法产生属于诚实分叉上区块的MMR证据，也不能通过提前准备好诚实最长链上的区块来欺骗验证节点。

只有当所有被质询的区块都能提供正确的MMR证据，加以被质询区块的有效性(例如正确的PoW)得到验证，验证节点才会选择相信它所收到的最新区块确实属于诚实最长链上的最新区块。

Benedikt在他的论文里面提供了一种采样算法，如果存在恶意节点造假，该采样算法能够以极高的概率命中无效区块，从而断定收到的最新区块不属于诚实的最长链。

将MMR结构应用在区块链上，需要修改区块头部的数据结构，这相当于一次硬分叉。鉴于目前比特币网络的自治情况，要想达成这样的共识，难度不小。目前来看，尽管MMR短期内获得社区一致认可与支持的可能性尚且不高，但由于区块链行业将面对的越来越多的跨链交易，终有一天对于方便高效的区块信息验证的需求会引起人们对于MMR的兴趣。

注：以上图片来自于Onchain

参考资料：

[1] FlyClient: Super-Light Clients for Cryptocurrencies

[2] MMR说明文档，

https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md