本文作者：苏江，微信公众号：苏江。
首发于“申龙斌的程序人生”公众号。
这篇文章对于刚刚接触区块链的读者有点难，适合有一定程序背景知识的朋友阅读，普通用户需要了解SPV（简易支付验证）的概念，知道默克尔树的基本原理也有助于理解轻钱包的概念。
Merkle tree（默克尔树）是一种数据结构，通常是一个二叉树（也有可能是多叉树），它以特定的方式逐层向上计算，直到顶部。Merkle tree最为常见和最简单的形成是二叉默克尔树。
在比特币的设计里，也使用了Merkle tree的数据结构，只不过里面存放的数据内容都是哈希值(HASH)。
哈希算法是一种摘要算法，你给它输入一个任意长的数据A，经过HASH运算后，它返回给你固定长度的数据B，也称B为“数据指纹”。这种哈希算法理论上是不可逆的，所以构成了加密数字货币设计的基础。
比特币的每一笔交易，都有一个交易ID，是一串很长的数字，如T1、T2、T3.....。
每个transaction ID进行哈希运算，生成一个哈希值H1, H2, H3等。然后相邻的两个哈希值相加之后，再进行哈希计算，形成它的父节点，以次类推，一直到根节点，形成默克尔树。
根节点的哈希值就是比特币单独一个区块的哈希值。比特币的每一个区块都可以通过其区块头的“前一个区块的哈希值”字段引用前一区块，形成一个区块链条。Merkle tree的根哈希值则可以确保区块中所有交易的真实性。
如果恰巧交易ID的总共数量为奇数个呢？那么排在最后的这个交易ID就copy自己一份，凑成偶数。
在比特币的设计里，有一点非常重要，一定要把所有的交易（transaction）按顺序排列下来，通过时间戳的功能就可以做到，如果顺序有误，那根哈希的结果就会大相径庭。
比特币的Merkle tree只存哈希值，没有任何实质的内容，实质的内容存在尾部的每笔交易里。
比特币为什么要用Merkle tree呢？
因为比特币有一个SPV功能，即：Simple Payment Verification（简单支付验证）。比特币的Merkle tree就是用来支持SPV功能。
SPV client 是个轻量级的客户端，SPV Client 只会下载所有的区块的头部信息，而不会下载交易部分，所以整个client下载比较快。
这里的头部信息仅包含5项内容，数据块大小为80字节：
上一区块头的哈希值
时间戳
挖矿难度值
工作量证明随机数（nonce）
包含该区块交易的梅克尔树的根哈希
SPV的目标是为了验证某个支付是否真实存在，并得到多少个确认。比如我向你转了一笔比特币，我告诉你我已经转了，那你如何验证这笔支付的真实性呢？
支付验证的过程很简单，只是判断这笔支付交易是否得到了区块链节点共识验证，并得到了多少的确认数即可。
1）首先计算待验证支付的交易哈希值。
2）节点从区块链网络上获取并存储最长链的所有区块到本地。
3）节点从区块链获取待验证支付对应的Merkle tree 哈希认证路径。
4）根据认证路径，计算Merkle tree的根哈希值，将计算结果与本地区块头中的Merkle tree的根哈希值相比较。
5）如果一致则说明支付真实有效。
6）根据区块头所处的位置，确定该支付已经得到的确认数量。
第3步中，假设你的交易是HK, 则计算根哈希值的办法是找到HL、HIJ、HMNOP 和 HABCDEFGH，这里有一种专门的遍历算法可以得到。
总的来说，Merkle tree 在区块链的应用实现了简单快速验证的功能。
--- END ---
↓↓↓ “阅读原文”参加区块链生存训练
