前言：
默克尔树属于二叉树的一种，如果数据结构的基础比较弱，没关系，在阅读文章的时候记录下不懂的地方，然后有针对性的去搜索学习。
本文会分三个部分来解释和论证为什么“默克尔树” 能支撑比特币的底层交易系统：
什么是默克尔树
默克尔树的特性
在比特币中的应用
什么是默克尔树？
由一个根节点，一组中间节点和一组叶子节点组成。根节点表示是最终的那个节点，且只有一个。叶子节点可以有很多，但是不能再扩散也就是没有子节点了。想象一棵树，由树根长出树干，树干上长出树枝，树枝长出叶子，好！收！叶子上不会再长出叶子。如果还是理解不了就看看下面这张图：
图解：
Root: 这个就是根节点，所有的子节点汇总到这里，像一棵倒立的树。
Hash: 能将任意长度的二进制明文映射为较短的二进制串的算法，也叫“哈希”算法，如MD5，SHA系列等，哈希后的结果也称哈希值。
Data0...Data3: 这些代表的是具体的原始数据
B0,B1...B3: 这些是把原始数据进行哈希运算后得到对应的哈希值
这时候有的同学要喊了，老师！你刚交的“叶子节点不能再扩散了，但是图中B0和Data0是什么关系”。这个问题很好，Data0和是B0是对应的关系，也就是说B0的哈希值对应的是Data0这一条数据，唯一对应的。
现在重点来了，一个简单的默克尔树就是像上图中显示的那样，有以下三步：
-
第一步把最底层的Data0...Data3这四条数据，每一条单独进行Hash，得出4个哈希值作为叶子节点。
第二步把相邻的两个叶子节点的哈希值拿出来再进行Hash，如B0+B1 Hash后得出B4。
第三步递归执行这样的Hash操作，直到最终Hash出一个根节点，就结束了。
这就是默克尔树的运行原理，在图中展现是：B0+B1 Hash得出B4，B2+B3 Hash得出B5，B4+B5 Hash得出Root根节点。由于每个节点上的内容都是哈希值，所以也叫“哈希树”。
默克尔树的特性：
敏感的同学马上会思考“既然讲默克尔树，那么它一定会有与众不同的地方”，没错，它有三大特性：
第一特性：任意一个叶子节点的细微变动，都会导致Root节点发生翻天覆地的变化，可以用来判断两个加密后的数据是否完全一样
第二特性：快速定位修改，如果Data1中数据被修改，会影响到B1，B4和Root，当发现根节点Root的哈希值发生变化，沿着Root - > B4 - > B1最多通过O(logn)时间即可快速定位到实际发生改变的数据块Data1.
第三特性：零知识证明，它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。比如怎么证明某个人拥有Data0...Data3这些数据呢？创建一棵如图所示的默克尔树，然后对外公布B1，B5，Root；这时Data0的拥有者通过Hash生成B0，然后根据公布的B1生成B4，再根据公布的B5生成Root，如果最后生成的Root哈希值能和公布的Root一样，则可以证明拥有这些数据，而且不需要公布Data1，Data2，Data3这些真实数据。如图：
在比特币中的应用：
首先介绍一个概念：默克尔路径，上图中Root - > B4 - > B1 这就是一条路径，表示从根节点到叶子节点所经过的节点组成的路径。
比特币中，默克尔树被用作归纳一个区块中的所有交易，同时生成整个交易集合的数字签名，且提供了一种校验区块是否存在某交易的高效途径，就是默克尔路径。生成默克尔树需要递归地对各个子节点进行哈希运算，将新生成的哈希节点插入到默克尔树中，直到只剩一个哈希节点，该节点就是默克尔树的根节点。
假设一个区块中有16笔交易，根据上文提到的公式O(logn) 可以算出16的对数是4，也就是要找到这个区块中的任意一笔交易，只需要4次就可以了，它的默克尔路径会保存4个哈希值，可能同学们对这个高效率的查找没有感觉，我们来看一个统计，刺激一下：
解释一下，
一笔交易大概250 Byte左右
路径数代表哈希值的数量，路径数是4表示这条路径存了4个哈希值，每个哈希值是32 Byte
区块大小 = 交易数 * 250 Byte
路径大小 = 路径数 * 32 Byte
可以看出，当区块大小由16笔交易（4KB）增加至262144笔交易（65MB）时，为证明交易存在的默克尔路径长度增长极其缓慢，仅仅从128字节到576字节。有了默克尔树，一个节点能够仅下载区块头（80字节/区块，里面包含上一区块头的哈希值，时间戳，挖矿难度值，工作量证明随机数，包含该区块交易的默克尔树的根哈希值），然后通过从一个满节点回溯一条小的默克尔路径就能认证一笔交易的存在，而不需要存储或者传输大量区块链中大多数内容，这些内容可能有几个G的大小。这种不需要维护一条完整的区块链的节点，又被称作简单支付验证（SPV）节点，它不需要下载整个区块而通过默克尔路径去验证交易的存在。再来献上一张V神画的图，在比特币网络中找出了TX3的默克尔路径：
总结：
介绍了什么是默克尔树，以及它的三个特性和在比特币中的应用。核心就是将大量数据进行哈希运算后增加其分布式索引性能，通过维持一个较小的高效索引(默克尔路径)进而管理复杂的大量数据。
参考链接：
https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/
閱讀更多 5分鐘機器學習 的文章
