区块链中的另外一个数据结构是Merkle tree，在比特币中使用的就是这种结构：
可能没有听说过Merkle tree，但一定听说过binary tree(二叉树)。
Merkle tree和binary tree的区别：Merkle tree用哈希指针代替了普通的指针
每个框内的两个哈希值，在一起取哈希，就是上框内的哈希值，如下图箭头表示：
这种数据结构的好处在于，只要记住根哈希值，就能检测出该树下的任何数据是否篡改。
圆圈内黄色的tx被修改，那么必然导致上方绿色的H()被修改，从而导致了上方绿色的H()被修改，从而导致了上方绿色的H()被修改，最终导致了root hash这个值的修改。
Merkle tree的作用
Proof of Inclusion
Merkle proof可以证明merkle tree里面包含了某个交易，所以这种证明又叫proof of membership或 proof of inclusion。
比特币网络参与者包括全节点和轻节点，全节点保存了区块的所有信息，包括block header和block body，而轻节点只保存了block header。
假设某个轻节点想要知道某笔交易是否写入了某区块中，应当怎么做？（类似A向B买东西，使用比特币支付，A告诉B这笔交易已完成，钱已付，在某区块中，B是轻节点，B如何验证这比交易在区块链中？）
使用Merkle proof就可以解决这个问题，具体操作步骤如下：假设下图中的黄色交易是这笔交易。
- 全节点收到了B请求验证这笔交易的信息，全节点可以看到这笔在merkle tree中的位置，他给B提供三个数据，即上图中红色的H()。
- B在本地通过运算得到上图中绿色的H()，再和获得的红色H()一起，再在本地算出上方的绿色H()，再和获得的红色H()一起，再在本地算出上方的绿色H()，最终算到root hash值。
- B将算出来的root hash值与本地的root hash值进行对比，相等则表示这笔交易存在该区块中。
为什么全节点不直接告诉B结果呢？因为不能保证这个全节点是友善的。
那是否有可能全节点为帮助A伪造交易，向B提供的哈希值（即上图中红色的H()）是经过调整的，使B最终算出来的root hash值与本地的root hash值一致呢？
答案是几乎不可能！因为哈希的collision resistance和不可逆两个特性，制造不出这样的哈希碰撞。
对于一个轻节点来说，验证一个merkle proof 复杂度是多少?假设最底层有n个交易，则merkle proof 复杂程度是θ(log(n))。
Proof of Non-Inclusion
上述我们为了证明某个交易在区块中，本质是proof of membership或者是proof of inclusion。上述方法的复杂度为对数级别。
那我们是否可证明某个交易不在区块中呢？即proof of non-membership问题。
方式1：遍历一遍树。这么做的复杂度是n
方式2：对所有叶节点（即交易）取哈希，将哈希值有小到大排列，将待查找的交易的哈希值，利用二分法进行查找。这么做的复杂度降为log n文章来源：https://www.toymoban.com/news/detail-832853.html
这种排好序的merkle tree称为 sorted merkle tree。比特币中没有用到这个sorted Merkle tree，因为不需要不存在证明。文章来源地址https://www.toymoban.com/news/detail-832853.html
到了这里，关于区块链的数据结构（二）——默克尔树（Merkle Tree）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
