Merkle 树是一种树形数据结构，用于高效地验证数据完整性和一致性。
它将一组数据通过哈希函数递归地组合，最终生成一个唯一的根哈希（Merkle Root）。
验证数据是否属于集合只需提供一个证明路径（Merkle Proof），验证时间和空间复杂度都很低。
- Merkle 树的基本结构
- 叶子节点: Merkle 树的底层节点，每个叶子节点是原始数据的哈希值。
- 父节点: 每两个相邻的叶子节点的哈希值组合后，再次进行哈希运算，生成父节点。
- 根节点: Merkle 树的顶层节点，由所有数据递归组合而成，称为
Merkle Root
- 构建 Merkle 树的过程
- 数据准备
- 假设有一组数据：[A, B, C, D]。
- 计算叶子节点：
- 对每个数据进行哈希：
- Hash(A), Hash(B), Hash(C), Hash(D)。
- 构造父节点：
- 将相邻的叶子节点组合并哈希：
Parent1 = Hash(Hash(A) || Hash(B))-Parent2 = Hash(Hash(C) || Hash(D))
- 生成根节点
- 再次组合父节点并哈希:
Root = Hash(Parent1 || Parent2)
- 再次组合父节点并哈希:
- Merkle 树验证原理 验证某个数据是否属于集合，需要以下三部分：
- 叶子节点的哈希值: 即被验证数据的哈希值。
- Merkle 证明（Merkle Proof): 包含该节点到根节点路径上的兄弟节点哈希值。
- Merkle 根: Merkle 树的根节点哈希值。 验证步骤：
- 从叶子节点开始，将当前节点与证明路径中的哈希值依次组合并哈希
- 如果最终计算出的哈希值等于 Merkle 根，则证明该节点属于集合
package merkle
import (
"bytes"
"errors"
"crypto/sha256"
"encoding/hex"
)
// MerkleNode 默克尔树节点
type MerkleNode struct {
Left *MerkleNode
Right *MerkleNode
Hash []byte
Data []byte
}
// MerkleTree 默克尔树
type MerkleTree struct {
Root *MerkleNode
Leaves []*MerkleNode
HashFunc func(data []byte) []byte
}
// NewMerkleTree 创建新的默克尔树
func NewMerkleTree(data [][]byte) (*MerkleTree, error) {
if len(data) == 0 {
return nil, errors.New("data cannot be empty")
}
// 创建树实例
tree := &MerkleTree{
HashFunc: sha256Hash,
}
// 创建叶子节点
for _, datum := range data {
node := &MerkleNode{
Hash: tree.HashFunc(datum),
Data: datum,
}
tree.Leaves = append(tree.Leaves, node)
}
// 构建树
root, err := tree.buildTree(tree.Leaves)
if err != nil {
return nil, err
}
tree.Root = root
return tree, nil
}
// buildTree 构建默克尔树
func (m *MerkleTree) buildTree(nodes []*MerkleNode) (*MerkleNode, error) {
if len(nodes) == 0 {
return nil, errors.New("cannot build tree with no nodes")
}
if len(nodes) == 1 {
return nodes[0], nil
}
var parentNodes []*MerkleNode
// 两两配对构建父节点
for i := 0; i < len(nodes); i += 2 {
var left, right *MerkleNode
left = nodes[i]
// 如果是奇数个节点，复制最后一个节点
if i+1 == len(nodes) {
right = nodes[i]
} else {
right = nodes[i+1]
}
// 计算父节点哈希
parentHash := m.HashFunc(append(left.Hash, right.Hash...))
parent := &MerkleNode{
Left: left,
Right: right,
Hash: parentHash,
}
parentNodes = append(parentNodes, parent)
}
// 递归构建上层节点
return m.buildTree(parentNodes)
}
// GetProof 获取默克尔证明
func (m *MerkleTree) GetProof(data []byte) ([][]byte, error) {
// 查找目标叶子节点
var targetLeaf *MerkleNode
for _, leaf := range m.Leaves {
if bytes.Equal(leaf.Data, data) {
targetLeaf = leaf
break
}
}
if targetLeaf == nil {
return nil, errors.New("data not found in tree")
}
proof := make([][]byte, 0)
return m.generateProof(m.Root, targetLeaf.Hash, &proof), nil
}
// generateProof 生成默克尔证明
func (m *MerkleTree) generateProof(node *MerkleNode, targetHash []byte, proof *[][]byte) [][]byte {
if node == nil {
return *proof
}
// 如果是叶子节点，返回证明
if node.Left == nil && node.Right == nil {
return *proof
}
// 查找目标哈希所在的分支
if bytes.Equal(node.Left.Hash, targetHash) {
*proof = append(*proof, node.Right.Hash)
return m.generateProof(node.Left, targetHash, proof)
}
if bytes.Equal(node.Right.Hash, targetHash) {
*proof = append(*proof, node.Left.Hash)
return m.generateProof(node.Right, targetHash, proof)
}
// 递归搜索左右子树
leftProof := m.generateProof(node.Left, targetHash, proof)
if len(leftProof) > 0 {
return leftProof
}
return m.generateProof(node.Right, targetHash, proof)
}
// VerifyProof 验证默克尔证明
func (m *MerkleTree) VerifyProof(data []byte, proof [][]byte) bool {
// 计算叶子节点哈希
currentHash := m.HashFunc(data)
// 逐步计算根哈希
for _, proofElement := range proof {
// 确定证明元素的位置（左或右）
if bytes.Compare(currentHash, proofElement) < 0 {
currentHash = m.HashFunc(append(currentHash, proofElement...))
} else {
currentHash = m.HashFunc(append(proofElement, currentHash...))
}
}
// 验证计算得到的根哈希是否与树的根哈希相同
return bytes.Equal(currentHash, m.Root.Hash)
}
// 辅助函数：SHA256哈希
func sha256Hash(data []byte) []byte {
hash := sha256.Sum256(data)
return hash[:]
}// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
contract MerkleProofVerifier {
/**
* @notice 验证 Merkle 证明
* @param leaf 被验证的叶子节点
* @param proof Merkle 证明数组
* @param root Merkle 根
* @return isValid 是否有效
*/
function verify(
bytes32 leaf,
bytes32[] memory proof,
bytes32 root
) public pure returns (bool isValid) {
bytes32 computedHash = leaf;
for (uint256 i = 0; i < proof.length; i++) {
bytes32 proofElement = proof[i];
if (computedHash <= proofElement) {
// 按顺序拼接哈希
computedHash = keccak256(abi.encodePacked(computedHash, proofElement));
} else {
// 反转顺序拼接哈希
computedHash = keccak256(abi.encodePacked(proofElement, computedHash));
}
}
return computedHash == root;
}
}稀疏Merkle树是Merkle树的一个变体，特别适合处理大规模但实际存储数据较少的场景。 特点：
- 支持高效的存在性证明
- 适合处理稀疏数据（大多数节点为空）
- 可以优化存储空间
- 存储效率
- Merkle树：需要存储所有节点
- 稀疏Merkle树：只存储非空节点和必要的中间节点
- 空间占用
- Merkle树：O(n)，n为总节点数
- 稀疏Merkle树：O(m)，m为非空节点数
- 证明能力
- Merkle树：只能证明存在性
- 稀疏Merkle树：可以证明存在性和不存在性
- 应用场景
- Merkle树：适合连续数据的完整性验证
- 区块链区块数据
- 文件系统校验
- 稀疏Merkle树：适合稀疏数据的状态管理
- 账户系统
- 键值存储
- 权限管理
-
场景: 在区块链中，Merkle 树用于验证交易是否包含在区块中
- 比特币的区块头中包含一个 Merkle 根，用于验证区块内的交易
- 以太坊的 Patricia Merkle Trie 存储账户状态和交易
-
作用
- 高效验证：验证单个交易是否在区块内，只需提供证明路径，复杂度为 O(\log n)
- 节省存储：链上仅存储 Merkle 根，验证过程无需存储所有数据
-
案例: 比特币 SPV（简化支付验证）
- 轻节点无需下载整个区块链
- 通过 Merkle 证明验证交易是否在某个区块内
- 场景: 分布式存储系统（如 IPFS、Filecoin）需要验证文件的完整性和是否被篡改。
- 作用
- 文件完整性验证
- 将文件分片后存储，每个分片生成一个哈希值。
- 使用 Merkle 树计算根哈希，用于验证文件是否被篡改。
- 分布式校验
- 提供分片的证明路径，快速验证数据是否来自可信存储节点。
- 案例: IPFS：
- 文件哈希值由分片的 Merkle 树根计算而成
- 验证下载文件的片段是否属于原始文件
- 场景: 项目方在链上分发代币空投，用户通过链下获取证明并在链上验证领取资格。
- 作用
- 高效分发
- 链上只存储 Merkle 根，用户通过证明路径验证领取资格
- 节省链上存储成本，支持大规模分发
- 防重复领取
- 使用映射记录已领取地址，防止用户重复领取奖励。
- 案例: 去中心化空投：
- 项目方为用户生成空投证明，链上合约验证用户提交的证明路径和领取金额。
- 场景： Layer 2 解决方案（如 Optimism、Arbitrum）使用 Merkle 树存储和验证用户在 Layer 1 和 Layer 2 的状态
- 作用
- 状态提交
- Layer 2 定期将用户状态哈希的 Merkle 根提交到 Layer 1
- 用户可以提供 Merkle 证明，验证状态是否在提交的根中
- 欺诈证明
- 通过 Merkle 证明验证某个交易或状态更新是否合法。
- 案例 Rollup: Optimism 使用 Merkle 树记录用户存款、提现和状态更新
场景: 跨链桥需要验证某个事件是否发生在源链上，以实现可信跨链通信
- 作用
- 事件证明
- 在源链生成事件的 Merkle 树根
- 目标链上通过 Merkle 证明验证事件是否真实发生
- 节省资源
- 无需在目标链存储所有事件数据，仅存储 Merkle 根
- 事件证明
- 案例: 跨链桥
- 通过 Merkle 树验证跨链资产的存款事件，保证跨链资产安全性
- 场景: 分布式账本系统中，需要验证多个节点之间的数据一致性
- 作用
- 快速验证：
- 每个节点计算本地数据的 Merkle 根，根一致则表示账本一致
- 冲突检测
- 如果根不一致，通过 Merkle 树验证找到冲突位置
- 案例: Hyperledger Fabric
- 使用 Merkle 树记录账本状态，验证交易是否被正确记录
- 场景: 在 NFT 项目中，需验证 NFT 元数据的完整性和真实性
- 作用
- 保证数据完整性
- 将 NFT 元数据的哈希生成 Merkle 树根，链上存储根哈希
- 用户提供证明路径验证 NFT 数据是否被篡改
- 节省存储
- 链上仅存储 Merkle 根，元数据存储在链下
- 案例: NFT 项目
- NFT 元数据存储在 IPFS，链上验证元数据与对应 NFT 的绑定关系
- 场景: 去中心化身份系统中，需要验证用户的身份数据是否在特定集合中
- 作用
- 匿名验证：用户提供身份数据的 Merkle 证明，无需暴露完整身份信息
- 数据完整性: 验证用户提交的数据未被篡改。
- 案例: 去中心化社交平台：
- 用户提交 Merkle 证明，证明自己属于某个群体（如 DAO 成员）
Merkle 树广泛应用于区块链和分布式系统的各个领域，提供高效的数据验证和一致性保证。
无论是交易验证、状态更新、空投分发还是跨链通信，Merkle 树都通过其独特的设计，成为不可或缺的技术工具。
Merkle 树验证具备的以下优点也是它被广泛应用的原因
- 高效验证：验证时间复杂度为
O(\log n)，适合大规模数据集合 - 节省存储： 链上仅需存储 Merkle 根，无需存储完整数据集合
- 灵活性：适用于
交易验证、状态验证、事件验证等多种场景 - 数据隐私：提供证明时无需暴露完整数据，保证隐私
- 安全性：Merkle 根唯一对应数据集合，防篡改性强