区块链技术架构分析（3）-默克尔树（merkle tree）

Answer 1

默克尔树（Merkle tree）是一种哈希二叉树，发明于1979年。在计算机科学中，二叉树结构中每个节点最多有两个子树，通常分别称为“左子树”和“右子树”，树结构用于快速数据查询。默克尔树由根节点、一组中间节点和一组叶节点组成。叶节点包含数据或其哈希值，中间节点则是其两个孩子节点内容的哈希值，根节点由其两个子节点内容的哈希值组成。默克尔树的特点是底层数据变动会传递至其父节点，直至树根，且查询时间复杂度为 O(logn)。

默克尔树应用模式包括：
- 快速比较大量数据：当两个默克尔树根节点相同时，意味着所代表的数据必然相同。
- 快速定位修改：如修改某数据，会影响到特定路径的哈希值，从而快速定位修改位置。
- 零知识证明：通过默克尔树，可以证明数据中包含特定内容，而无需暴露其他内容信息。
- 分布式系统应用：在分布式存储中，每台机器构建一颗默克尔树，通过根节点比较快速确定数据一致性，节省比对时间和数据传输量。

在比特币系统中，默克尔树用于快速归纳区块数据完整性，将数据分组哈希运算，最终产生根哈希值。这种结构提高了比特币区块链运行效率和可扩展性，支持简化支付验证协议（SPV），在不运行完整节点的情况下，也能对交易数据进行检验。