hello，大家好，我们第四期的区块链技术分享来啦，这一次让大家久等了~~
这一期我们分享merkletree——默克尔树。看到本期文章标题的时候，可能大部分人已经这样了
虽然默克尔树大家很陌生，但是提到默克尔树相关的应用，大部分程序员肯定接触过。merkletree最大的应用场合就是在点对点网络，Git版本控制系统、IPFS协议、比特币以及以太坊等等。同时merkletree也是区块链面试大概率会被问到的问题，所以这一期我们就来聊一下比特币网络中的merkletree。
01merkletree的数据结构
merkletree是计算机科学家RalphMerkle在年发明的。就是这位大佬（找不到好看的图了，大家将就看）
论文题目是《Adigitalsignaturebasedonaconventionalencryptionfunction》翻译成中文大概的意思是：基于常规加密函数的数字签名，旨在构建更好的数字签名。这个是merkletree的起源。
那么在比特币网络中，merkletree是如何应用的？
在区块链网络中，所有的区块呈链状连接。
每个区块展开可以分为区块头blockheader和区块体blockbody。关于区块头blockheader的字段解释，请参考区块链技术之哈希指针。
根据上面的图可以看出，所有的交易都存储在blockbody里面，blockbody就是一颗merkletree，并且只有叶子节点存储的是交易，也就是图中的tx（transaction），因此叶子节点也被称为datablock，非叶子节点存储的都是哈希值。
merkletree就是一个hash二叉树，父节点是两个子节点的doublesha的结果，叶子节点就是交易的content的doublesha结果；
最下面那一层就是交易数据datablock，每一个交易都可以计算出一个hash，从而层层向上，得到merkleroot。
但是由于blockchain里面都merkle运算要求叶子节点是偶数，所以，当一个区块内包含当交易数量为奇数时，把最后一个交易复制一份，凑成偶数。
最后就是把merkleroot保存在区块头中，交易数据被保存在区块体中，其实中间当那些hash并没有被保存，它们只是运算过程数据。
默克尔树大多用来进行完整性验证，比如分布式环境下，从多台主机获取数据，怎么验证获取的数据是否正确呢，只要验证Merkle树根哈希一致，即可。
例如，上图中tx1数据块被篡改了，那么错误会传导到计算hash(tx1)，接着传导到计算hash(hash(tx1)+hash(tx2))，最后传导到根哈希，导致根哈希的不一致。因此，任何底层数据块（datablocks）的变化，最终都会传导到根哈希，也就是区块头中的默克尔根。
02merkleproof
那么说了这么多，merkletree到底有什么用呢？
在比特币网络中，merkletree一个重要的用途就是提供merkleproof。
在解释merkleproof之前，我们先讲一下比特币网络中的节点。
2.1什么是节点？
在加密货币中，凡是连接到该网络的任何计算机，都被称为节点。
在区块链中，存在一种冗余备份的现象。
如果所有节点都需要保存全网的所有交易及其他数据信息，则不可避免的会出现一些弊端，比如，用户想创建一个自己的区块链节点进行项目开发，而不需要参加共识过程（不需要挖矿），那么进行数据的同步将是一项特别庞大的工作，既耗时又费资源。
2.2全节点和轻节点
因此，这个时候比特币网络中的节点就可以分为两类：全节点和轻节点。
全节点，保存有全网交易数据，又能完成相关验证交易，独立完成与对等节点的连接。这类节点在本地保存了一个完整的区块链网络（保存了所有区块的blockheader和blockbody），在其上可进行任何查询、交易的验证与广播，正因为有这样的节点存在，更加使得去中心化成为了可能，同时使得区块链网络更加安全。
全节点一直在线，最重要的是参与挖矿，寻找最长合法链并辨别分叉。
轻节点，轻节点不需要保存所有交易内容，利用merkletree的特性，它只需包含blockheader以及与自己相关的交易细节，并通过Merkle证明来判断交易是否在当前的区块链交易列表中。
轻节点并不一直在线，与全节点不同，它只能检测哪一条是最长链，但无法知道是否是最长合法链，因为轻量级节点无法验证大多数交易的合法性，也无法验证区块链网络发布的区块的正确性。
例如，手机上的比特币的钱包的应用，就是一个轻节点，只保存blockheader。
这个时候存在一个问题，如何向一个轻节点证明，某个交易已经被写入到区块链里面？
解答这个问题之前，我们再区分两个名词：支付验证和交易验证。
交易验证非常复杂，涉及到验证是否有足够余额可供支出、是否存在双花、脚本能否通过等等，通常由运行全节点的矿工来完成。
支付验证则比较简单，只判断用于“支付”的那笔交易是否已经被验证过，并得到了多少的算力保护（多少确认数）。
如何向一个轻节点证明，某个交易已经被写入到区块链里面？指的是“支付验证“，而不是“交易验证”。这个就要用到merkleproof。
某个轻节点想知道图中标为黄色的tx交易是不是被写到区块链里面？轻节点没有保存交易列表，只保存了根哈希值。
1.那么这个轻节点就会向某个全节点发出请求，请求给出包括这个待验证支付的merkleproof。
2.全节点收到请求后，只要把图中红色的H（）发给轻节点；
3.轻节点在本地就可以计算出H（）；
4.那么轻节点就可以计算出一个merkleroot，轻节点只需要将计算出的根哈希值与blockheader里面的存储根哈希值进行比较，就可以验证这个交易是不是被写入了区块链。
因此，SPV（SimplifiedPaymentVerification，简单支付验证，这个概念比特币白皮书里面提到过，可以参考[]比特币白皮书中英文翻译及解析）验证的过程：
1.从网络上获取并保存最长链的所有blockheader至本地;
2.计算该交易的hash值tx_hash;
3.定位到包含该tx_hash所在的区块，验证blockheader是否包含在已知的最长链中;
4.从区块中获取构建merkletree所需的hash值;
5.根据这些hash值计算merkle_root_hash;
6.若计算结果与blockheader中的merkle_root_hash相等，则交易真实存在。
7.根据该blockheader所处的位置，确定该交易已经得到多少个确认。
这个过程里面还用到了一个重要的数据结构叫bloomfilter，布隆过滤器。布隆过滤器的应用不止在SPV的验证，以太坊的数据结构里面也用到了布隆过滤器，如果你是一个产品经理你肯定知道UV这个重要的指标，那么布隆过滤器在UV统计中也发挥了重要的作用。所以，下一期我们分享布隆过滤器和SPV。
03总结
1.merkletree就是一个hash二叉树，父节点是两个子节点的doublesha的结果，叶子节点就是交易的content的doublesha结果；
2.最下面那一层就是交易数据，每一个交易都可以计算出一个hash，从而层层向上，得到merkleroot。但是由于blockchain里面都merkle运算要求叶子节点是偶数，所以，当一个区块内包含当交易数量为奇数时，把最后一个交易复制一份，凑成偶数。最后就是把merkleroot保存在区块头中，交易数据被保存在区块体中，其实中间当那些hash并没有被保存，它们只是运算过程数据。
3.merkletree被广泛运用于区块链中，但其实P2P下载中merkletree的应用更为广泛。
OK，本期分享就这么多，下期我们分享bloomfilter布隆过滤器和SPV验证。
本文参考：
《区块链技术与应用》公开课；
《区块链：技术驱动金融》。