零点课堂 | 默克尔树的基础数据结构1

默克尔树简介

（正常区块链中的默克尔树）

本文主要介绍了默克尔树的基础数据结构，以及默克尔树相关的应用延伸的起点。

它存在于比特币区块链中，以一种非常有效地节省空间和时间的方式，来帮助验证交易的存在(本文后面会详细介绍!)。作者深入研究了默克尔树，意识到这个数据结构实际上是多么丰富的，所以决定写一篇默克尔树学习笔记。

默克尔树解说

默克尔树构建完成后，看起来是这样：

（这是一个基本的默克尔树结构，中间节点可缩写为H（ab）和H（cd），如果没有缩写的话，根哈希也可以为H（H（H（a）+ H（b）） + H（H（c）+ H（d））））

a、b、c、d是一些数据元素（文件，公钥、私钥，JSON等），H是哈希函数。如果你不是很了解哈希函数，可以把它理解为数据块的“数据指纹”，Hash是一个把任意长度的数据映射成固定长度数据的函数，而根据Hash值反推原始输入数据的特征是几乎不可能的。每个节点都是通过哈希运算父节点得到的，默克尔树的常见结构是二叉树，但也有非二叉树结构的，比如以太坊平上默克尔树。本文只讨论这种最常见的二叉树结构。

自下而上通过哈希运算相同高度的节点，直至生成默克尔树根节点。在生成默克尔树的时候，如果存在单个叶子节点无法匹配成对，就需要特殊处理这个情况，除此之外，树的构造非常简单。

默克尔树构建完成后，就可以在O(log n)时间内使用根哈希对叶子进行验证（这也称为默克尔树证明），验证工作是通过重新创建包含从根到被验证的数据段进行的。在上面的例子中，如果想要验证c（假设我们有根哈希值），那么就需要得到H（d）和H（H（a）+ H（b））。数据c哈希后得到H（c），再将H（c）与H（d）进行哈希运算，然后将H（cd）与H（ab）在进行哈希运算，得到一个最后的哈希值，如果这个哈希值与根哈希相同，则说明c确实是默克尔树中数据的一部分。

在BT下载等情况下，是由另一方提供数据c， H（d）和H（H（a）+ H（b））的，如果你担心这种方法的安全性，请记住在一个哈希函数上不可能找到e值使得H（E）= H（C）。这意味着只要根哈希是正确的，其他人很难作假他们提供的数据。

输出某些数据的验证路径和重新创建通向默克尔树根的分支一样简单。在数字签名方案中使用默克尔树时，验证整个默克尔树及其各个叶子节点自身的数据就很重要，并且这实际上是可以在O(log n)时间内完成。有一些更高级（但很复杂）的算法是可以完成这一输出过程的。

默克尔树的执行方法

下图是完整版本的代码，作者将会在这里解释创建和验证默克尔树的方法。注意build_tree（创建默克尔树）和_audit（验证）方法都是来自较大类的实例方法。

构建树的方法是将叶子添加到堆栈中，并检查堆栈中的前两个节点是否具有相同的高度。当高度相同时，节点有一个“子值”(两个节点哈希值相连后的再次哈希值)，当高度不同时，一个新节点会追加到堆栈中。当最后两个节点高度不同时，需要处理这种边缘情况。

上面的方法在单节点情况下会失败，因为不满足任何条件，所以有一个小方法来处理完整性。

上图是本文要解释的验证过程。公开验证方法会检查一些先决条件，这就是为什么大部分逻辑放在这个私人版本中的原因。

本文由旖旖撰写，零点财经收录，观点仅代表作者本人，绝不代表零点财经赞同其观点或证实其描述。

本文由 零点财经 作者：tao 发表，其版权均为 零点财经 所有，文章内容系作者个人观点，不代表 零点财经 对观点赞同或支持。如需转载，请注明文章来源。