Merkle tree有什么用途呢？一个用途就是提供merkle proof。比特币中的节点分为两类，一类是全节点，还有一类是轻节点。全节点是保存整个区块的内容，就是block header和block body，全节点是都有的，它有交易的具体信息。但是轻节点，比如像手机上的比特币钱包的应用就属于轻节点，它只保存block header。这就带来一个问题，如果需要向一个轻节点证明某个交易是写入到区块链里，该怎么做？比如，你要向我转一笔账。你告诉我说，你转给我钱的交易已经写到区块链里了，这个支付已经完成了。我是个轻节点，我怎么知道这个交易是不是已经被写入到区块？这就要用到merkle proof找到这个交易所在的位置。从你转给我钱的交易区块往上，一直到根节点这条路径，这条路径就是merkle proof。
用上图来展示这个过程，最上面一行是一个小型的区块链，把其中的一个区块的merkle tree展现出来了，最下面一行是它里面包含的交易。假设某个轻节点想知道黄色的这个交易是不是被包含在了这棵merkle tree里面。由于轻节点没有保存交易列表，没有这棵merkle tree的具体内容，只有一个根哈希值。那怎么办呢，这个轻节点怎么才能知道这个黄色交易是不是被包含的？这个轻节点向某个全节点发出请求，请求一个能够证明这个黄色的交易被包含在这棵merkle tree的merkle proof全节点。收到这个请求之后，只要把图中标为红色的这三个哈希值，发给这个轻节点就行了。有了这些哈希值之后，轻节点在本地可以计算出图中标为绿色的这三个哈希值。首先算出黄色交易的哈希值，就是最下面绿色的这个哈希，然后和旁边红色的哈希值，就是全节点提供的右边这个红色的哈希值拼接起来，可以算出上一层节点里的那个绿色的哈希，然后再和它这一层左边那个红色的哈希值拼接起来可以算出再上一层的那个绿色的哈希值，一直做下去就可以算出整棵树的根哈希值。轻节点把这个根哈希值和block header里的根哈希值比较一下，就能知道这个黄色的交易是不是在merkle tree里了。
轻节点收到这样一个merkle proof之后只要从下往上验证，沿途的这些哈希值是否正确的就行了。如果我想知道你给我转账的交易是不是真的写到了这个区块里。作为一个轻节点，只有block header，block header里只有根哈希值。现在传给我这样一个路径，我检查一下，这些哈希值算的是否都正确。这里注意，查的时候只能查所在分支上的哈希值。旁边分支的哈希值是查不了。因为没有旁边分支的交易内容，所以旁边分支哈希值的正确性我是不能确定的。只要验证我有数据的交易所在的分支是否符合要求，最后对根节点取哈希，和我保存的block header里的哈希值是一样的就行。这是merkle tree的性质，如果对树中任何一个部位做了修改，都会影响到根哈希值。如果根哈希值是保持不变的，那说明里面所有的内容都没有被修改过。
引申一下。这个过程似乎有一点不安全。因为我们验证的时候只能验证交易所在的分支，旁边分支的哈希值没有办法验证。这个情况从表面上看好像给篡改数据提供了一定的自由度。比如，有人伪造一个交易的内容，内容改了之后，所在区块的哈希值就不对。但是旁边分支的哈希值是不用验证的，理论上可以取任意的数。那我能不能调整一下旁边分支这个不用验证的哈希值，使得整个节点的哈希指保持不变，这样反映到上一层的话，相应的哈希指针就不用变了。
这个在实际中是不可行的，原因就是我们上节文章里讲的collision resistance性质。这是在人为制造哈希碰撞。即使给你这个自由度，旁边分支的哈希值可以随便，也制造不出这样的哈希碰撞的，这是collision resistance的性质。
上面讲的是merkle proof可以证明merkle tree里面包含了某个交易，所以这种证明也叫做proof of member，或者叫proof of inclusion。对于轻节点来说，收到这样一个merkle proof，要验证它复杂度是多少，时间和空间的复杂度是多少？如果最底下一层一共有n个交易的，那么merkle proof的复杂度是对数级别的。这个是比较高效的。
能不能证明merkle proof里面没有包含某个交易呢，就是现在正的是proof of membership，能不能证明proof of non-membership？有一个最简单的证明方法，就是把整棵树传给这个轻节点，轻节点收到之后，验证一下这个树的构造都是对的，即每一层的哈希值都是正确的。说明这棵树里只有这些叶节点，没有别的节点。那要找的这个交易不在里面就证明了proof of non-membership。这是种比较低效的方法，问题在于它的复杂度是线性的，不是对数级别的。有没有比较高效的方法，能证明不存在。如果不对叶节点的排列顺序做任何假设的话，那是没有更高效的方法。因为要找的某个交易，可能出现在叶节点中任何位置，除非把整个交易都发过去，否则怎么知道要找的那个交易不在里面。
但是如果对这些叶节点的排列顺序做一些要求，比如按照交易的哈希值排序，对每个交易的内容取一次哈希，按照哈希值从小到大排序，那么这样是有一个好的证明方法的。要查的那个交易，先算出一个哈希，然后看看如果它在里面的话，应该是在哪个位置。比如说是在某两个数据块之间，然后我提供的merkle proof是什么呢。是这两个数据块都要往上到根结点。轻节点收到这样一个证明之后，验证一下这两个交易往上的路径都是正确的，最后根结点算出来的哈希值也是没有被修改过的，就说明这两个节点在原来的merkle tree里面确实是相邻的节点。要找的那个交易如果存在的话，应该是插在这两个之间的，但是它没有出现，所以是不存在的。这个复杂度也是对数的，代价是要排序。这种排好序的叫做sorted merkle tree。比特币中没有用到这种排好序的merkle tree，因为比特币当中并不需要做这种不存在证明，没有这种硬性需求，所以比特币中的merkle tree不要求排序。
这就是本节要讲的比特币中的两种最基本的结构，一个是区块链，一个merkle tree，都是用哈希指针来构造的。除了这两种结构之外，哈希指针还能用在什么地方？只要数据结构是无环的，都可以用哈希指针来代替普通的指针。有环的话会有一定的问题，比如，对于一个循环链表，如果用普通指针的话，是完全合法的，但如果是哈希指针的话就会有问题，就变成循环依赖了，最后哪个区块都定不下来，就出现循环了，所以有环的不行，没有环的情况下都可以用哈希指针。