数据结构与算法-默克尔树(Merkle tree)

数据结构与算法-默克尔树(Merkle tree)

引用

CSDN

1.

https://blog.csdn.net/qq_28053637/article/details/136772460

一、定义

哈希树（hash tree；Merkle tree）又称为默克尔树，因为概念是由拉尔夫·查尔斯·默克尔 1979 年提出并申请专利。

Merkle 树是一种首先在计算机科学领域实现的数据结构。

每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签 ，如下图所示

二、默克尔树的作用

能够有效地验证集合中元素的存在，而无需透露整个集合本身；是通过生成 Merkle 证明（也称为 Merkle 路径或身份验证路径）来完成的。

准确性：默克尔树可以轻松访问和分析，以检查数据是否准确

低存储：它们将块数据压缩为更小的大小，而不是单独存储每个交易。

对于区块链至关重要：它们已经成为区块链网络运营和为用户服务的重要组成部分。

三、应用领域

在区块链和去中心化技术的世界中，数据完整性至关重要。确保存储在区块链上的信息准确且防篡改是一项根本挑战。

每个区块包含一组交易，默克尔树保证它们的一致性和有效性。通过将 Merkle 根包含在区块头中，区块链技术可以有效验证区块的内容。这使得网络节点能够验证交易的完整性，而无需存储和处理块内的每个单独交易，从而增强可扩展性并减少计算开销。

3.1、区块链核心应用体现在以下几个方面：

1、交易数据的高效存储与验证

• 在区块链中，每一个区块包含多笔交易记录。每笔交易经过哈希运算后形成一个哈希值，作为默克尔树的叶子节点。

• 通过不断两两组合相邻节点并再次哈希，最终形成一个唯一的顶层哈希值，即默克尔根（Merkle Root）。

• 区块头仅需存储这个默克尔根，而非所有交易的具体内容，大大减少了存储需求，同时允许任何人通过默克尔证明（Merkle Proof）快速验证某个特定交易是否存在于区块中，且未被篡改。

2、轻量级客户端验证

• 轻客户端（SPV，