Merkle Tree默克尔树
在比特币中Merkle Tree实际上是一个hash树，是个二叉树。它的叶子节点为交易的hash值，然后对相邻的hash值进行拼接，并对拼接后的值再次进行hash运算，然后对相邻结果再次进行hash运算，重复对结果运算并产生新的节点，直至产生最后一个节点，成为跟节点Merkle Root。
1.hash运算采用double hash，即对数据进行两次hash运算。
2.在计算hash值是要保证节点数量为偶数，为奇数的情况，复制最后一个节点并参与运算
HA = SHA256(SHA256(Transaction A))，HAB = SHA256(SHA256(HA + HB))，HABCD = SHA256(SHA256(HAB + HCD))
Merkle 验证路径
获取方法
1.首先对区块中所有的交易进行排序，然后对所有交易进行hash运算并生成merkle tree。
2.查询一笔交易的hash，查询到交易hash后，获取该节点到跟节点的路径，得到merkle路径。
3.获取验证路径，即除merkle root外，在merkle路径上所有的兄弟节点
使用方法
mekle路径是指从一笔交易到merkle root途经的所有节点，验证路径是指除merkle root外，在merkle路径上所有的兄弟节点。当获取到验证路径时，使用交易的hash可以计算出merkle root。如下图所示，HK交易的验证路径为HL、HIL、HMNOP、HABCDEFGH；拥有HK即交易K的hash时，即可计算得到Merkle Root。
Merkle 证明
merkle证明是根据验证路径，验证一笔交易是否存在的过程。具体的验证过程与上述验证路径中说到的过程一致，如果可以根据交易的hash和验证路径计算出的merkle root与获取到的merkle root一致，则说明该笔交易确实存在于区块中。
SPV简易支付验证
SPV（Simplified Payment Verification），在区块链中对于轻节点来说，只需要保存区块链的header信息，可以解决在一些设备上无法存储大量区块链数据问题。区块header保存的信息有，version版本号，pre_hash上一个节点的hash值，timestamp时间戳（区块打包的时间戳），merkle_root根hash，nonce随机数，nBits该区块的复杂度。
简易支付验证的步骤：
1.获取到交易hash后，可以在区块链中获取包含这笔交易的区块及header
2.验证merkle root是否存在于区块链中
3.按照验证路径进行hash运算，比较得到的root与merkle root是否一致。
小结
merkle tree被广泛运用于区块链中，但并不是只有区块链使用它来进行校验。比如一些p2p下载，如迅雷，就需要把文件分割为小块文件，每块都有一个hash，每块从不同的网络节点下载，最后组成一个完整的文件，但是也需要进行hash验证，它也可以使用merkle tree来进行验证。merkle tree也不一定是二叉树，可以是任意树结构。而在以太坊中，merkle验证还不够用，增加了Patricia Tree验证，合起来称为“Merkle Patricia Tree”。
疑问
1.在生成验证路径的时候，需要查找到该笔交易对应的hash，不就已经确定该笔交易是存在的吗？
2.在根据用户提供的交易hash查询区块时，不就确定了该笔交易已经存在于区块链之中了吗？为什么还要进行merkle证明。
