【1期三团Day-7 苏江】秒懂Merkle Tree 与SPV

jeg06666mcw

本文作者：苏江，微信公众号：苏江。

首发于“申龙斌的程序人生”公众号。

这篇文章对于刚刚接触区块链的读者有点难，适合有一定程序背景知识的朋友阅读，普通用户需要了解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 在区块链的应用实现了**简单快速验证**的功能。

---------------------------

这里对区块链专业知识感兴趣的同学，可以加入申龙斌同学的**区块链生存训练**饭团，共同学习。