IPFS技术解读：Merkle DAG中的Merkle树到底是什么？

大家都知道，Merkle DAG是IPFS系统的基本组成部分，是其功能的基础，它们允许对大数据结构进行有效和安全的验证。当然，Merkle DAG并不是IPFS团队发明的，它来来自于Git数据结构，它是在Merkle tree基础上构建的(IPFS团队一直是一个很努力的团队，并不是直接拿来使用，而是在此基础上修改更适合项目的使用)。

因此，想要摸透IPFS技术，了解一些Merkle tree基础知识是很有必要的， 今天笔者就告诉大家什么是Merkle tree?

Merkle tree是由美国计算机学家merkle于1979年申请的专利， Merkle Tree通常也被称作Hash Tree，顾名思义，就是存储hash值的一棵树。

密码哈希函数

简单地说，哈希函数是用于将任意大小(输入)的数据映射到固定大小输出的任何函数。散列算法应用于数据输入，并且得到的固定长度输出称为散列。许多散列算法广泛公开，可根据您的需要进行选择。

来自任意输入的结果散列不仅固定长度，输入也是完全唯一的，并且函数本身是确定性的。也就是说，无论您在同一输入上运行多少次函数，输出总是相同的。例如，如果您将以下数据集作为输入，则结果输出对于每个输入都是唯一的。请注意，在第二个和第三个示例中，即使输入的差异只有一个字，结果输出也完全不同。这非常重要，因为它允许对数据进行“指纹识别”。

加密哈希函数，来自维基百科的图像

由于输出(示例中的散列和)长度始终与使用的散列算法确定的相同，因此可以仅通过其生成的散列来识别大量数据。对于包含大量数据的系统，能够以固定长度输出存储和识别数据的好处可以节省大量存储并有助于提高效率。

在区块链中，散列算法用于确定区块链的状态。区块链是包含数据的链表，以及指向前一个区块的哈希指针，创建一个连接块链，因此名称为“区块链”。每个块通过散列指针彼此连接，散列指针是前一个块内的数据的散列以及前一个块的地址。通过以这种格式链接数据块，前一个块的每个结果散列表示区块链的整个状态，因为先前块的所有散列数据被散列为一个散列。这通过诸如此类的输出(散列)表示(在SHA-256算法的情况下)。

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

上面的哈希是它之前的区块链的整个状态的指纹。新块之前的区块链状态(作为散列数据)是输入，结果哈希是输出。尽管可以使用没有Merkle树的加密哈希，但它效率极低且不可扩展。使用散列以串行格式将数据存储在块中是耗时且麻烦的。

正如您将看到的，Merkle树允许通过Merkle校样轻松解决数据完整性以及将数据映射到整个树。

Merkle树和Merkle证明

以1979年获得专利的Ralph Merkle命名，Merkle树基本上是数据结构树，其中每个非叶节点是其各自子节点的散列。叶节点是树中节点的最低层。首先，它可能听起来很难理解，但如果你看一下下面常用的数字，它将变得更容易理解。

二进制哈希树的示例，来自维基百科的图像

重要的是，注意左侧的非叶节点或“分支”(由Hash 0-0和Hash 0-1表示)是它们各自的子L1和L2的散列。此外，请注意分支哈希0是如何连接其子级的哈希，分支哈希0-0和哈希0-1。

上面的例子是被称为二元Merkle树的Merkle树的最常见和最简单的形式。如您所见，顶部哈希是整个树的哈希，称为根哈希。从本质上讲，Merkle树是一种数据结构，可以采用“ n ”个哈希值并用单个哈希表示它。

树的结构允许有效地映射任意大量的数据，并且能够容易地识别该数据发生变化的位置。这个概念使Merkle证明成为可能，有人可以验证数据的散列是否在树的一直向上和正确的位置是一致的，而不必实际查看整个散列集。相反，他们可以通过仅检查散列的一小部分而不是整个数据集来验证数据块是否与根散列一致。

只要根哈希是公知的和可信的，任何想要对数据库进行键值查找的人都可以使用Merkle证明来验证数据库中数据的位置和完整性。一个特定的根。当根哈希可用时，可以从任何不可信任的源接收哈希树，并且可以一次下载树的一个分支，立即验证数据完整性，即使整个树尚不可用。

Merkle树结构最重要的好处之一是能够通过类似的散列机制验证任意大的数据集，该机制用于验证更少量的数据。该树有利于将大量数据分发到可管理的较小部分，其中尽管总体上较大的数据大小，但是用于验证完整性的屏障大大减少。

根哈希可以用作整个数据集的指纹，包括整个数据库或表示区块链的整个状态。在以下部分中，我们将讨论比特币和其他系统如何实现Merkle树。

比特币采用的加密哈希函数是SHA-256算法。这代表“安全散列算法”，其输出长度固定为256位。比特币中Merkle树的基本功能是存储并最终修剪每个块中的事务。

如前所述，区块链中的块通过前一个块的哈希值连接。在比特币中，每个块包含该块内的所有事务以及由以下各项组成的块头：

阻止版本号

上一个块哈希

时间戳

挖掘难度目标

杜撰

Merkle Root哈希

下图来自比特币白皮书，并说明了Merkle树如何适应每个区块。

交易由矿工包含在块中，并作为Merkle树的一部分进行散列，从而导致存储在块头中的Merkle根。这种设计有许多不同的好处。

最值得注意的是，如白皮书中所述，这允许存在简单支付验证(SPV)节点，也称为“轻量级客户端”。这些节点不必下载整个比特币区块链，只需下载最长链的块头。SPV节点可以通过查询其对等节点来实现这一点，直到他们确信他们正在操作的存储块头是最长链的一部分。然后，SPV节点能够通过使用Merkle证明来将事务映射到特定Merkle树，该特定Merkle树具有作为最长链的一部分的块头中的相应Merkle树的根哈希。

此外，比特币的Merkle树的实现允许修剪区块链以节省空间。这是仅将根哈希存储在块头中的结果，因此，可以通过去除Merkle树的不必要分支来修剪旧块，同时仅保留Merkle证明所需的那些。

IPFS中以 Merkle树 为基础的 MerkleDAG

Merkle DAG拥有如下的功能：

• 内容寻址：使用多重哈希来唯一识别一个数据块的内容

• 防篡改：可以方便的检查哈希值来确认数据是否被篡改

• 去重：由于内容相同的数据块哈希是相同的，可以很容去掉重复的数据，节省存储空间

Merkle树是分布式版本控制系统(如Git和IPFS)的重要组成部分。它们能够轻松确保和验证P2P格式的计算机之间共享数据的完整性，这使得它们对这些系统非常有用。