梅克尔树（Merkle tree）是为了解决多重一次签名中的认证问题而产生的，由于梅克尔树结构具有一次签名大量认证的优点,在认证方面具有显著的优势。' v( }8 a" t# M! g# j
如今,梅克尔树的树形结构已经被广泛应用到了信息安全的各个领域,比如证书撤销、区块链数据安全、群密钥协商等等。那它的运行机制究竟是怎么样的呢？* ~3 Y: y: \) j4 o
本期《晓说区块链》，陈晓东先生（维基链首席技术官）将围绕这个话题，为大家解读。7 U; Q: X: ~! E7 N7 ~$ N
网友：经常看到区块链验证交易的内容中，涉及到merkle树相关的内容，请问区块链中merkle树是如何验证的呢？它的具体运行机制是怎么样的？
. f0 S  z% W5 a+ F/ ?$ w5 y陈晓东：首先要理解区块链里面经常使用的梅克尔树（Merkle tree）是什么？
6 s4 |9 S7 C8 B9 u+ X8 }如下图所示：Merkle树是一种二叉树的数据结构，最底层是叶子，内容是对应数据的哈希值，然后每两片相邻的叶子联合起来做一次哈希计算成为上层节点的内容，持续这样的计算就产生了一个最顶层的节点的哈希值。如果叶子层对应的原始数据是由偶数个组合而成，那么自然两两结合配对。如果原始数据点个数为奇数，那么从最左边开始两两结合之后还有一个孤节点数据，它和自身结合配对后计算哈希值。" x0 M8 R' E1 u
, e- @7 A+ x% u  V+ e0 Y8 H2 K
这种特殊结构在比特币区块链代码里面使用到了。如下图所示：比特币的区块头（Block Head）里面包含了一个梅克尔树根, 也就是所有块交易哈希值的关联树计算后得到的顶层哈希值。4 z7 j6 w* [4 k) m3 \# V
) x0 N7 i9 b  R# D2 C
那么，为啥需要这样的数据结构？这就需要从简化支付验证(SPV：Simplified Payment Verification)说起了，也就是说如何验证或确保一个数字货币的交易已经在对应区块链的一个区块中了？一种无脑的方式就是自己搭建一个节点下载和同步好区块链数据，然后通过节点程序查询交易对应的哈希值来判断是否交易已经存在这条已经同步好的数据区块中。这种方法至少有两个弊端：
+ ^1 ]  f' X% f9 U9 v# d数据下载量太大：下载通信量大同时本地存储空间大；
. G+ G1 G, c' J3 e3 [  a4 h" f! G验证计算量大：需要把所有交易哈希值都串起来再计算对应的哈希值去比较是否相同。& U6 h% B8 [! W
中本聪(Nakamoto Satoshi)当初设计这个就是考虑到比特币这条链的数据增长（目前已经在300GB左右）导致普通节点或者终端无法承载所有数据而实现自身验证交易可靠性，因此非常需要一个简单易行而又可靠的方法可以让一个轻节点只需要下载少量数据即可完成交易真实性的验证，这就是梅克尔树数据结构和算法发挥巨大作用了：
1 I& N* r- f3 [8 |, X2 _2 jSPV钱包节点无需下载区块链完整数据，而只需下载区块链的每块不包含交易的头部数据；7 y2 s3 P6 n+ z. n# p
在验证某一个交易真实性的时候，SPV钱包节点只需要把该交易哈希值向网络中连接的全节点（Full Node: 同步了全部区块链数据的节点）发起询问；
. ~/ o  i) s, m) S5 I网络里面的全节点只需要回复最小量必要数据给SPV钱包，即可验证交易真实性；, l  b- R/ G$ ?# C
如果SPV钱包不信任提供交易验证数据的全节点，还可以同时发起多个全节点的询问，来确保交易验证的最大可靠性。
. x/ Q- x6 y7 G3 [: a如下图所示，假如一个区块包含了Ta，Tb，Tc，Td，Te，Tf，Tg，Th等8个交易，而SPV钱包发起了对交易Td真实性的查询。在梅克尔树里面可以快速计算得到各个层级的哈希值，直到梅克尔树根的哈希值。然而被询问的全节点，无需传输整个梅克尔树的节点数据，而只需要传回给SPV钱包四个哈希值：Td, Hc, Hab, Hefgh。也就是说减少了一半的数据量传输。聪明的你会很快发现，所需要传输的验证数据的个数等同于梅克尔树的高度(从底部哈希值开始计算）:3 R. G- U* W2 f  y) \( H- F
5 X6 Z: W/ u. ~- x8 L) A# q3 o
但是如果这个块里面包含的交易个数量变得很大，比如说有1000个，那么需要传输的数据量只需要如下个数：
2 ]# \( C* G2 X: S. V/ t
1 x( B7 W2 b; p$ p/ y+ |也就是少传输了近100倍的数据量！如果块的总交易量继续上升，这个验证数据传输量的相对压缩比例还可以继续增大！！
  b, m5 B- [6 O3 B3 y
2 i) s5 |7 I' c2 }具体证明如下：
# h2 b  E+ q( n3 s' W1 T* M/ |1 R7 \' m% m9 A0 ~# T
然后SPV钱包把计算出来的Habcefgh哈希值和自己同步下载好的区块数据块头里面的梅克尔树哈希值比较相等就行了。如果没有找到相等的，说明交易不可信。可能数据还没有同步过来，也可能交易就根本没有发生，所以暂时还不能相信或者接受/确认这个交易。+ _  S4 R& V8 L' B# F. i
最后笔者这里抛一个问题，这个梅克尔树的数据结构包括每个树节点里面的值是否需要物理存储下来作为区块链的一部分而存在，甚至在网络广播呢？答案是当然不需要了。第一是不需要，因为被询问的全节点可以根据自己全量的交易块里面快速计算出SPV钱包验证需要的相应数据，并且不需要存储梅克尔树的中间层的数据。第二是假如特意存储了这个梅克尔树的全部节点数据，那么存储的数据比只单纯纯粹交易数据或者交易哈希值数据多了不少，明显是有违初衷的，相比其节约的哈希值计算时间的收益是微乎其微的，可以说是得不偿失。