Merkle树和SPV机制

这篇文章主要介绍比特币中Merkle树的数据结构、原理特点及其应用。同时，我们也会介绍比特币轻钱包的实现基础--简单支付验证（Simple Payment Verification， 即SPV），并详细介绍它的原理机制以及跟Merkle树的关系。

Merkle树是什么

1.比特币中的Merkle树

在讲Merkle树之前，我们来看下比特币上某一个区块它的结构组成，可以看到，里面有一个二进制哈希树根。这个哈希值是当前区块下所有包含的交易以Merkle Tree结构生成的哈希值。

查看区块的链接地址：https://blockchain.info/zh-cn/block-index/1648717

2.Merkle树概念

Merkle Tree，也叫哈希树，是由Ralph Merkle于1979年提出申请的专利。它是一种用做快速归纳和校验大规模数据完整性的树形数据结构。

它具有以下特点：

它是一种树，大多数是二叉树，也可以是多叉树，具有树结构的所有特点。

Merkle Tree的叶子节点是数据块的哈希。

Merkle Tree的非叶子节点的哈希值是根据它下面所有叶子节点的值哈希计算得到，如下图所示。

备注：如果最开始叶子节点是奇数个，可以复制最后一个叶子节点，凑成偶数个。

可以发现，只要存储的叶子节点数据有任何的变动，就会逐级向上传递到相应的父节点，最终使得Merkle树的根节点哈希值发生变化。

3.Merkle树的应用

Merkle树的应用场景有以下几种：

快速比较大量数据：当两个Merkle树的根哈希值相同时，说明所代表的的数据都相同

快速定位修改：如上图，如果交易C发生改变，那么就会导致N2、N5和Merkle Root发生改变。所以，我们想要快速定位，只需要沿着Root==>N5==>N2就可以定位到交易C发生改变。

零知识证明：例如，想要证明一组交易中包含某个交易A，但又不想让对方知道交易A的具体内容，那么就可以构建Merkle树（如上图），向对方公布N0、N1、N4和Root，对方就可以确认交易A的存在，但无法知道交易A的具体内容。

比特币的简单支付认证（SPV）

1.SPV是什么

简单支付认证，即Simple Payment Verification，简称SPV。SPV的目标是为了验证某个交易支付是否存在，以及得到比特币网络多少个确认（多少个区块）。比特币中的SPV功能就应用到了Merkle树的特性。

2.为什么需要SPV机制

我们知道，比特币网络中所有产生的交易均打包进区块中，一般情况下，一个区块中包含几百上千笔交易是很常见的。在2014年4月份，比特币网络中一个全节点要存储、处理所有区块的数据，需要占用15GB的空间，并且每个月以超过1GB的速度在增长，到现在呢？要完整下载比特币的所有区块数据，需要整整200GB以上的空间！！

如果用户要用手机来使用比特币，那完全不够空间去存储这么庞大的数据，而且以后还是逐年继续增长。于是中本聪在比特币白皮书中提出了SPV的概念：不运行全节点也可以验证支付，用户只需要保存所有的区块头就可以了。虽然用户不能自己验证交易，但如果能够从区块链的某处找到符合的交易，就可以知道这笔交易已被网络确认，也可以确认该笔交易得到网络多少笔确认。

这里需要注意的是，SPV强调的是验证支付，不是验证交易。这两个概念是不同的。验证支付，比较简单，只需要判断用于支付的那笔交易是否被验证过，以及得到网络多少次确认（即有多少个区块叠加）。而交易验证则复杂的多，需要验证账户余额是否足够支出、是否存在双重支付、交易脚本是否通过等问题，一般这个操作是由全节点的矿工来完成。

如下图，我们知道比特币中区块结构分成两部分，一个是区块头，包含区块的必要属性，仅80字节大小。另一个是区块体，包含当前区块下的所有交易，一般一个区块包含成百上千笔交易，每笔交易一般要400多字节。

3.比特币网络节点类型

这里需要介绍下比特币网络中几种常见的节点类型：

（1）全节点

包含钱包（支付验证）、矿工、完整区块链数据库、网络路由节点的功能。

（2）SPV节点

就只有简单的支付验证功能

除此之外，还有独立矿工等其他类型的节点，这里不涉及，就不一一介绍。详细的可以参考《精通比特币》一书的第六章比特币网络。

4.SPV验证过程

在SPV节点上，不保存全部区块链数据，不下载区块全部交易，只保存区块头数据。所以这种节点不能验证全部交易，只能用于验证支付（确认支付是在区块链中，以及确认多少次）。截止到现在为止，比特币高度为：521283（时间：2018-05-05 15:41），按照区块头80字节来算，总共也就10MB大小而已（80*521283/1024/1024）,这对整个存储容量的要求就大大减少。

那么，从用户A在购买商品时通过比特币支付，并声称自己已经转了1BTC给商家，到商家验证支付有效（SPV验证），这个过程是怎样的呢？

Step1：SPV节点如果只关心某个支付到自己比特币地址的交易，则可以通过建立布隆过滤器（布隆过滤器是一种基于哈希的高效查找结构，能够快速确定某个元素是否在一个集合内）限制只接收含有目标比特币地址的交易。

Step2：一旦比特币网络中其他当节点探测到某个交易符合SPV节点设置的布隆过滤器条件时，其它节点将以Merkleblock消息的形式发送该区块，Merkleblock消息包含区块头和一条连接目标交易与Merkle根的Merkle路径。

Step3：SPV节点通过该Merkle路径找到跟该交易相关的区块，并验证对应区块中是否存在目标交易。SPV节点所收到的Merkleblock数据量通常少于1KB，只有一个完整区块（大约1MB）大小的千分之一左右。

5.Merkle路径

在上一节中，我们提到了通过Merkle路径可以证明一笔交易是否存在区块中。下面我们通过一个例子来说明下Merkle路径。

如下图，如果需要证明某个区块上是否存在一笔交易C（如上图区块结构所示，我们是可以拿到Merkle树根的哈希值），那么我们只需要N3和N4的哈希值构成的Merkle路径就可以证明，过程如下：

Step1：获取交易C的哈希值，N2=Hash(交易C)

Step2：通过N2和N3的哈希值，得到父节点的哈希值：N5=Hash(N2+N3)

Step3：同上，通过N4和N5的哈希值，得到根节点的哈希值：Root=Hash(N4+N5)

Step4：然后将上一步得到的根哈希值对比区块头中MerkleTree的根哈希值，如果相同，则证明该区块中存在交易C，否则说明不存在

也就是说，对于一个包含4个交易的区块，我们只需要2个哈希节点就可以进行支付验证。

备注：一个哈希大小为32字节

由上表可以看到，当交易数量成几何速度成长时，Merkle路径的开销增长就很缓慢。所以，通过Merkle路径，SPV节点只需要很小的开销就可以快速定位一笔交易。