Merkle Tree

如果对区块链有些基本的了解，那应该经常听到一个词叫merkle tree，那么merkle tree到底是做什么用的呢，这里来简单的探讨一下。

首先我们需要知道在区块链网络中有两种类型的节点，一种节点叫full node，顾名思义，这种节点的特点就是它存储着整个区块链数据的完整备份，包括从区块链创世之初到现在的所有交易，所以这些数据量是很庞大的，会占据惊人的磁盘空间。还有一种节点叫spv(simple payment node)，有时候我们使用的是手机这类设备，存储空间有限，那就只需要下载每个区块的header信息（类似索引）就可以了，这样就会大大节省存储空间和带宽。

这样对spv节点就产生了一个问题，如果我发起了一笔交易，怎样确认这笔交易已经被包含在区块链中了呢？（毕竟节点中没有存储所有的交易信息）

先不管merkle tree，有一个笨办法，在区块header中会存储有一个hash值，这个hash值是这个区块中所有交易的hash值的hash：hash in header = hash(交易1+交易2+交易3+......)。当我们想确认交易X是否存在于区块M时，我们可以询问附近的一个full node，这个full node是不可信任的，它可能会告知我们假信息，所以需要它把区块M的所有交易的hash值都发给我们，然后我们来做比对，[hash in header of block M]（这个值是存储在我们本地区块header中值得信赖的值）是否等于 hash(交易1+交易2+...+交易X+...)，而这些交易的hash值是full node发给我们的。如果相等，表示交易X已经被确认，否则表示这个节点给了我们假信息或者交易未被确认。

似乎很美好，但是这样就又会产生一个问题，如果区块M中包含了一千笔交易，为了确认一笔交易就需要传输这一千笔交易的信息，对速度带宽等的消耗都是很大的。merkle tree就是为了解决这一个问题而产生的（学过算法的同学知道二叉树的时间复杂度是logN）。

观察下图，就是一个典型的merkle tree：

Merkle Tree Example

L1，L2，L3，L4代表区块中的所有的四笔交易，如果我们想确认L3是否被包含在区块中，需要full node给我们哪些信息呢？观察树的结构很容易知道，只需要给hash
1-1和hash 0就可以了，在spv本地block header中的hash值是top hash的值，这样只需要传输2个hash值就可以了，这样传输的信息量就变为了logN。