默克尔树(Merkle Tree)解释

要了解区块链,您需要了解它所基于的基本原理。它的主要特征可能是默克尔树,有时也称为哈希树。多亏了它,区块链可以同时有效和透明的运作。该概念在1979年由拉尔夫·默克尔(Ralph Merkle)教授申请了专利。现在,它有助于解决大型分散式网络中的问题。

什么是默克尔树,它与加密货币有什么关系?让我们在Changelly的这篇文章中一起探寻吧!

默克尔树基础知识

默克尔树是树状的完整数据结构,在其叶顶点中有来自数据块的哈希值,而内部顶点包含通过在子顶点中添加值而得到的哈希值。这将所有元素之间相互联系起来。最后,它看起来像这样。

Merkle-Tree

哈值希是转换哈希函数的结果。它是根据特定算法将任意长度的输入数据数组转换为指定长度的输出字符串的功能。

默克尔树有什么用?

在集中式系统中,信息的准确性不是问题,因为其所有组件都依赖一个集中式节点。当您收到转入您的银行帐户的资金时,您无需担心资金的真实性。

但是,在分散的网络中,一切都不是那么简单。每个节点都负责所传输信息的准确性,因此,由于网络上的交易数量众多,验证完整卷的真实性并非易事。至少在没有默克尔树的情况下是如此。它使您可以优化使用哈希显示数据的过程。文件系统使用默克尔树检查信息中的错误,并使用分布式数据库来同步记录。

在区块链上,哈希树可简化付款验证(SPV)。SPV客户端称为轻量级客户端(因为它们仅存储区块标题,而不存储其内容),以验证交易信息,不重新计算所有哈希值,而是要求默克尔树提供证明。它由一个根和一个分支组成,该分支包括从请求的事务到根的哈希值,因为客户端不需要有关其他操作的信息。当添加所请求的哈希并将它们与根进行比较时,客户端将确保事务已在其位置。这种方法允许您处理任意数量的数据,因为仅下载了必要的哈希,它可以大大减少网络上的负载。例如,具有五个最大大小的事务的区块的大小超过500 KB。在相同情况下,默克尔证明的大小不会超过140个字节。

默克尔树如何在比特币中运作

哈希函数是将输入数据转换为指定长度的位字符串的过程。接收到的字符串(哈希)在很大程度上取决于传入数据的数组。即时整个数组中一个字符发生了变更,则生成的哈希将采用完全不同的值。

比特币区块中的所有交易都是十六进制格式的字符串。它们被哈希运算并显示为事务标识符(txid)。直到收到该区块的单个哈希值为止,该区块中的所有txid进行均会被哈希运算。在此过程中,将构建默克尔树:

  1. 首先,计算txid(交易ID)本身,即交易哈希值;
  2. 然后,根据交易哈希值的总和计算哈希值。 默克尔树是二进制的-也就是说,在每个新的哈希步骤中,树元素的数量必须为偶数。如果该区块的事务数为奇数,则将复制最后一个的哈希并将其添加到自身;
  3. 根据交易哈希值总和来计算新的哈希值。该过程一直持续到获得单个哈希(根节点)为止。并在区块标题中指示。
merkle-tree in depth

在比特币区块链中,默克尔树是使用SHA-256双哈希构建的。这是哈希运算“Hello”字符串的示例:

第一轮SHA-256:

2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

第二轮SHA-256:

9595c9df90075148eb06860365df33584b75bff782a510c6cd4883a419833d50

默克尔树原理

编译默克尔树的过程类似于数据折叠。 多亏了它,交易或任何其他信息阵列的庞大列表可以在一行中表示。 令人惊奇的是,如果在这些相同事务的列表中的某处,我们仅更改一个符号,则树的下一层和最终的哈希将完全不同。 这意味着树的顶部也会改变。

换句话说,您不能将一个事务替换为该区块中的另一个事务,也不能更改现有事务的数据。 这就是为什么默克尔树被认为是在区块链中记录交易的有效方法。 还有默克尔证明(Merkle Proof)的概念。 这是使用哈希值验证信息有效性的原理。 无需检查整个数据数组,只需检查树中的各个哈希就足够了,这大大减少了整个过程的计算能力开销。

默克尔树的其它版本

本文讨论了拉尔夫·默克尔发明的概念的最简单的二进制版本。 在其中,每个“父”哈希都有两个“继承人”。 在比特币中,使用SHA-256双重哈希构建哈希树。

ethereum merkle tree

对这个概念有更复杂的解释。 例如,以太坊使用前缀默克尔树。 每个以太坊区块报头一次包含三个这样的树:关于事务,有关其执行和状态的信息。 与二叉树不同,前缀节点的值还取决于与其他节点的连接。 该值是动态的而非固定的。 可以更改它而不必重新计算树的所有哈希值。


Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注