做树就得有根--详解Merkle

    在上一篇文章中有说到，区块头中包含三组数据，一组是父区块哈希值，一组是与挖矿有关的数据（难度、时间戳、Nonce），还有一组是Merkle树根。

今天就来说一下Merkle树根。

    有Merkle树根，那么必然有着Merkle树。Merkle树用专业一点的解释是：这是一种哈希二叉树，它是一种用作快速归纳和校验大规模数据完整性的数据结构。

    我以一个外行人的眼光来看，那么这就是一个世界杯的赛程安排图，不过参赛队伍可能高达几千组。

    那么我们先来看一场足球预算赛，一开始有8支球队参加，每个球队有32个人（不要问我为什么这么多），每次对战结束后，在这两队总共64名选手中挑选出更为优秀的32名队员。

预选赛

    从图上可以看出，只需要通过三级比赛，就可以挑选出的这256名球员中最优秀的32名。

    而Merkle树的结构，与这场赛程安排图一模一样。

    在比特币中，通过对每个交易进行两次SHA256运算（因此也把这种加密哈希算法叫做double-SHA256），把这个交易的信息浓缩成为32字节的字符串。

    交易数据Ha是球队a，交易数据Hb是球队b，通过哈希运算，得到一个新的交易数据Hab。而交易数据Hab在与另一个小组的交易数据Hcd连在一个经过哈希运算，得到一个新的交易数据Habcd。重复上面的过程，最终得到一个交易数据Habcdefgh，即得到了Merkle根。

    有一点需要注意，就跟每一个新的球队只需要32名球员一样，每次经过哈希运算后得到的数据都是32字节的字符串。Habcdefgh看起来比Ha长很多，但是他们的数据大小都只有32字节。

    这样设计的好处在于，在证明区块中某个特定交易是否真实时只需要计算以2为底N的的对数次（数学符号最难打了，我不打）。

    我知道有很多人已经忘了对数是什么意思了，那么就从图例中来看，为了证明交易数据Ha是否真实只需要找到Hb、Hcd、Hefgh三组数据(红色标记)共计96个字节，经过计算三次哈希计算得出最终的Habcdefgh，并验证该值是否与区块头中注明的Merkle根是否匹配即可确认Ha是否真实。

计算路径

    随着交易越多，该模型的效果越强大。16个交易，需要4次计算；32个交易，需要5次计算；65536个交易，需要16次计算...这就叫指数级降低！

指数降低

    总结一下Merkle树及树根的意义：

    第一.再多的交易数据都可以浓缩到一个32字节的字符串中。

    第二.指数级减小交易验证的难度。