hello，大家好，我们第四期的区块链技术分享来啦，这一次让大家久等了

~~

这一期我们分享merkle tree——默克尔树。看到本期文章标题的时候，可能大部分人已经这样了

虽然默克尔树大家很陌生，但是提到默克尔树相关的应用，大部分程序员肯定接触过。merkle tree 最大的应用场合就是在点对点网络，Git 版本控制系统、IPFS 协议、比特币以及以太坊等等。同时merkle tree也是区块链面试大概率会被问到的问题，所以这一期我们就来聊一下比特币网络中的merkle tree。

merkle tree的数据结构

merkle tree是计算机科学家Ralph Merkle在1987年发明的。就是这位大佬（找不到好看的图了，大家将就看）

论文题目是《A digital signature based on a conventional encryption function》翻译成中文大概的意思是：基于常规加密函数的数字签名，旨在构建更好的数字签名。这个是merkle tree的起源。

那么在比特币网络中，merkle tree是如何应用的？

在区块链网络中，所有的区块呈链状连接。

每个区块展开可以分为区块头block header和区块体block body。关于区块头block header的字段解释，请参考区块链技术之哈希指针。

根据上面的图可以看出，所有的交易都存储在block body里面，block body就是一颗merkle tree，并且只有叶子节点存储的是交易，也就是图中的tx（transaction），因此叶子节点也被称为data block，非叶子节点存储的都是哈希值。

merkle tree就是一个hash二叉树，父节点是两个子节点的double sha256的结果，叶子节点就是交易的content的double sha256结果；

最下面那一层就是交易数据data block，每一个交易都可以计算出一个hash，从而层层向上，得到merkle root。

但是由于blockchain里面都merkle运算要求叶子节点是偶数，所以，当一个区块内包含当交易数量为奇数时，把最后一个交易复制一份，凑成偶数。

最后就是把merkle root保存在区块头中，交易数据被保存在区块体中，其实中间当那些hash并没有被保存，它们只是运算过程数据。

默克尔树大多用来进行完整性验证，比如分布式环境下，从多台主机获取数据，怎么验证获取的数据是否正确呢，只要验证Merkle树根哈希一致，即可。

例如，上图中tx1数据块被篡改了，那么错误会传导到计算hash(tx1)，接着传导到计算hash(hash(tx1)+hash(tx2))，最后传导到根哈希，导致根哈希的不一致。因此，任何底层数据块（data blocks）的变化，最终都会传导到根哈希，也就是区块头中的默克尔根。

merkle proof

那么说了这么多，merkle tree到底有什么用呢？

在比特币网络中，merkle tree一个重要的用途就是提供merkle proof。

在解释merkle proof之前，我们先讲一下比特币网络中的节点。

2.1 什么是节点？

在加密货币中，凡是连接到该网络的任何计算机，都被称为节点。

在区块链中，存在一种冗余备份的现象。

如果所有节点都需要保存全网的所有交易及其他数据信息，则不可避免的会出现一些弊端，比如，用户想创建一个自己的区块链节点进行项目开发，而不需要参加共识过程（不需要挖矿），那么进行数据的同步将是一项特别庞大的工作，既耗时又费资源。

2.2 全节点和轻节点

因此，这个时候比特币网络中的节点就可以分为两类：全节点和轻节点。

• 全节点，保存有全网交易数据，又能完成相关验证交易，独立完成与对等节点的连接。这类节点在本地保存了一个完整的区块链网络（保存了所有区块的block header和block body），在其上可进行任何查询、交易的验证与广播，正因为有这样的节点存在，更加使得去中心化成为了可能，同时使得区块链网络更加安全。全节点一直在线，最重要的是参与挖矿，寻找最长合法链并辨别分叉。
• 轻节点，轻节点不需要保存所有交易内容，利用merkle tree的特性，它只需包含block header以及与自己相关的交易细节，并通过Merkle证明来判断交易是否在当前的区块链交易列表中。轻节点并不一直在线，与全节点不同，它只能检测哪一条是最长链，但无法知道是否是最长合法链，因为轻量级节点无法验证大多数交易的合法性，也无法验证区块链网络发布的区块的正确性。例如，手机上的比特币的钱包的应用，就是一个轻节点，只保存block header。

这个时候存在一个问题，如何向一个轻节点证明，某个交易已经被写入到区块链里面？

解答这个问题之前，我们再区分两个名词：支付验证和交易验证。

交易验证非常复杂，涉及到验证是否有足够余额可供支出、是否存在双花、脚本能否通过等等，通常由运行全节点的矿工来完成。

支付验证则比较简单，只判断用于“支付”的那笔交易是否已经被验证过，并得到了多少的算力保护（多少确认数）。

如何向一个轻节点证明，某个交易已经被写入到区块链里面？指的是“支付验证“，而不是“交易验证”。这个就要用到merkle proof。

某个轻节点想知道图中标为黄色的tx交易是不是被写到区块链里面？轻节点没有保存交易列表，只保存了根哈希值。

1. 那么这个轻节点就会向某个全节点发出请求，请求给出包括这个待验证支付的merkle proof。

2. 全节点收到请求后，只要把图中红色的H（）发给轻节点；

3. 轻节点在本地就可以计算出H（）；

4. 那么轻节点就可以计算出一个merkle root，轻节点只需要将计算出的根哈希值与block header里面的存储根哈希值进行比较，就可以验证这个交易是不是被写入了区块链。

因此，SPV（Simplified Payment Verification，简单支付验证，这个概念比特币白皮书里面提到过，可以参考[001]比特币白皮书中英文翻译及解析）验证的过程：

1. 从网络上获取并保存最长链的所有block header至本地;

2. 计算该交易的hash值tx_hash;

3. 定位到包含该tx_hash所在的区块，验证block header是否包含在已知的最长链中;

4. 从区块中获取构建merkle tree所需的hash值;

5. 根据这些hash值计算merkle_root_hash;

6. 若计算结果与block header中的merkle_root_hash相等，则交易真实存在。

7. 根据该block header所处的位置，确定该交易已经得到多少个确认。

这个过程里面还用到了一个重要的数据结构叫bloom filter，布隆过滤器。布隆过滤器的应用不止在SPV的验证，以太坊的数据结构里面也用到了布隆过滤器，如果你是一个产品经理你肯定知道UV这个重要的指标，那么布隆过滤器在UV统计中也发挥了重要的作用。所以，下一期我们分享布隆过滤器和SPV。

总结

1. merkle tree就是一个hash二叉树，父节点是两个子节点的double sha256的结果，叶子节点就是交易的content的double sha256结果；

2. 最下面那一层就是交易数据，每一个交易都可以计算出一个hash，从而层层向上，得到merkle root。但是由于blockchain里面都merkle运算要求叶子节点是偶数，所以，当一个区块内包含当交易数量为奇数时，把最后一个交易复制一份，凑成偶数。最后就是把merkle root保存在区块头中，交易数据被保存在区块体中，其实中间当那些hash并没有被保存，它们只是运算过程数据。

3. merkle tree被广泛运用于区块链中，但其实P2P下载中merkle tree的应用更为广泛。

OK，本期分享就这么多，下期我们分享bloom filter布隆过滤器和SPV验证。

本文参考：

• 《区块链技术与应用》公开课；
• 《区块链：技术驱动金融》。