专栏名称: 奇舞精选

《奇舞精选》是由奇舞团维护的前端技术公众号。除周五外，每天向大家推荐一篇前端相关技术文章，每周五向大家推送汇总周刊内容。

利用 Merkle Tree 高效检测数据变更

奇舞精选 · 公众号 · · 2024-12-30 18:00

正文

本文作者为 360 奇舞团前端开发工程师

在当今数字世界中，如何高效地验证大量数据的完整性是一个重要挑战。无论是云存储同步、区块链交易验证，还是 P2P 文件分享，都需要一个可靠且高效的方案。这就是我们今天要介绍的主角 —— Merkle Tree（默克尔树）。

从哈希函数说起

我们都知道哈希函数可以接受任何输入，不管是单一文本还是一整个文件，都能生成一个唯一的输出，这个输出我们称之为「哈希值」或者「摘要」，它是一个由字符或数字组成的固定长度字符串。

例如，我们有一个叫做 foo.js 的文件，我们可以使用哈希函数 SHA1 生成一个值，如： 5f44557c8c615183ddfc42e82544945ce01f3c2a 。但只要对文件有一丁点的更改，哈希值也会变化，比如我们加入一个空格，它就会变成 490be46b3ce0259122c266f500919022d5046cf0 。我们可以用哈希函数来验证两个文件是否相同，或者文件是否被篡改过。

一个文件当然很简单，但是如果我们有一大批文件呢，单独计算每个文件的哈希值会非常低效，这时有一种数据结构能高效的帮我们搞定这个问题，那就是 Merkle Tree，这种神奇的数据结构能帮我们高效精准地发现一批文件中的变更。

在本文中，我将为大家简单介绍 Merkle Tree 的基础概念和原理，提供一个代码实现，并给出一些应用。

什么是 Merkle Tree？

Merkle Tree（默克尔树）又叫哈希树，通常被实现为二叉树，广泛应用于区块链、文件校验和数据同步等领域，Git 中也使用了类似 Merkle Tree 的结构来存储和验证数据，其由以下几个部分构成：

一个根节点
一组中间节点
一组叶子节点

看上去平平无奇，但是一会儿你就能理解这么分的意义所在了。

我们的 Merkle Tree 是由哈希函数自底向上构建出来的。

以一个目录下的所有文件来构建 Merkle Tree 为例，我们首先计算每一个文件的哈希值，将其作为 Merkle Tree 的一组叶子节点。真实的目录结构其实对我们构建 Merkle Tree 没有什么帮助，我们只需要将叶子节点两两配对（如果无法配对，为了保持二叉树结构，最后一个节点会被复制一次），创建父节点作为「中间节点」或者「分支」就好，让其保存根据子节点的值计算哈希值即可。就这样，按照之前的规则不断向上构建，我们会得到一个根节点。

如下图所示，假设我们有数据块 L1、L2、L3、L4，我们可以构建得到一个这样的 Merkle Tree。

如何，现在你应该能够理解为何我们要将 Merkle Tree 的结构拆解为根节点、中间节点和叶子节点了吧。

Merkle Tree 应用

数据同步与 Merkle Tree

我们想象一个云端同步的例子，我正在使用一款网盘应用，同步我的本地目录和云端目录：

/sync_folder/
    ├── file1.txt
    ├── file2.txt
    ├── file3.txt
    └── file4.txt

此时，我的本地目录和云端目录是同步的，构建的 Merkle Tree 结构为：

            ROOT[7ab2c4e]
            /            \
    [45d31a9]         [88f7d55]
    /        \        /        \
[aaf4c61] [cc628cd] [23a1f22] [9a7c54b]
    |         |         |         |
  File1     File2     File3     File4

但后续我在本地对 file2 进行了修改：

/sync_folder/
    ├── file1.txt
    ├── file2.txt（已修改）
    ├── file3.txt
    └── file4.txt

云盘这时想要发现哪些文件是不不同步的，就可以重新计算 Merkle Tree （红色表示发生变化的哈希值）：

             ROOT[🔴e9f8d2c]
            /            \
    [🔴b7a3c1]         [88f7d55]
    /        \        /        \
[aaf4c61] [🔴d4e5f6] [23a1f22] [9a7c54b]
    |         |         |         |
  File1     File2     File3     File4
          (已修改)

云盘可以通过一层层的比较 Merkle Tree，发现哪些文件和之前是不同的，从而后续对这些文件进行增量同步。

你也许发现了这就是一个二分查找的过程，其时间复杂度为 O(log n) ，相比一个查找对比要高效很多很多：

文件数量    传统方式     Merkle Tree
10         10次比较     ≤ 4次比较
100        100次比较    ≤ 7次比较
1,000      1000次比较   ≤ 10次比较
10,000     10000次比较  ≤ 14次比较
100,000    100000次比较 ≤ 17次比较

我们可以实现一下这个同步检测的例子，大家可以试试：

const crypto = require('crypto');

class MerkleNode {
    constructor(hash, filename = '') {
        this.hash = hash;
        this.filename = filename;
        this.left = null;
        this.right = null;
    }
}

class MerkleTree {
    constructor() {
        this.root = null;
    }

    // 计算数据的哈希值
    static hash(data) {
        return crypto.createHash('sha256').update(data).digest('hex');
    }

    // 构建 Merkle Tree
    buildTree(files) {
        // 创建叶子节点
        const leaves = Object.entries(files).map(([filename, content]) => {
            const hash = MerkleTree.hash(content);
            return new MerkleNode(hash, filename);
        });

        // 构建树
        this.root = this.buildTreeFromNodes(leaves);
        return this.root;
    }

    // 从节点数组构建树
    buildTreeFromNodes(nodes) {
        if (nodes.length === 0) return null;
        if (nodes.length === 1) return nodes[0];

        const parents = [];

        // 每次取两个节点组合
        for (let i = 0; i 2) {
            const left = nodes[i];
            const right = i + 1 1] : null;

            // 计算父节点的哈希值
            const combinedHash = right 
                ? MerkleTree.hash(left.hash + right.hash)
                : left.hash;

            const parent = new MerkleNode(combinedHash);
            parent.left = left;
            parent.right = right;

            parents.push(parent);
        }

        // 递归构建上层节点
        return this.buildTreeFromNodes(parents);
    }

    // 查找不同的文件
    findDifferences(otherTree) {
        const differences = [];
        
        const compare = (node1, node2) => {
            // 如果哈希值相同，说明这个分支下的所有文件都相同
            if (!node1 || !node2 || node1.hash === node2.hash) {
                return;
            }

            // 如果是叶子节点（有文件名），说明这个文件不同
            if (node1.filename) {
                differences.push(node1.filename);
                return;
            }

            // 递归比较左右子树
            compare(node1.left, node2.left);
            compare(node1.right, node2.right);
        };

        compare(this.root, otherTree.root);
        return differences;
    }
}

// 使用示例
function main() {
    // 模拟初始文件内容
    const originalFiles = {
        'file1.txt': 'Hello',
        'file2.txt': 'World',
        'file3.txt': 'Merkle',
        'file4.txt': 'Tree'
    };

    // 模拟修改后的文件内容（file2.txt 被修改）
    const modifiedFiles = {
        'file1.txt': 'Hello',
        'file2.txt': 'JavaScript',  // 修改了这个文件
        'file3.txt': 'Merkle',
        'file4.txt': 'Tree'
    };

    // 构建原始文件的 Merkle Tree（模拟云端）
    const cloudTree = new MerkleTree();
    cloudTree.buildTree(originalFiles);

    // 构建修改后文件的 Merkle Tree（模拟本地）
    const localTree = new MerkleTree();
    localTree.buildTree(modifiedFiles);

    // 查找差异
    const differences = localTree.findDifferences(cloudTree);
    console.log('需要同步的文件:', differences);

    // 打印验证过程
    console.log('\n验证过程:');
    console.log('根节点哈希值比较:');
    console.log('本地:', localTree.root.hash);
    console.log('云端:', cloudTree.root.hash);
}

main();

区块链与 Merkle Tree

在区块链网络中，每个区块都包含了大量的交易信息。为了让轻节点（如手机钱包）能够高效地验证交易，区块链使用了 Merkle Tree 结构。

如果不使用 Merkle Tree，我们将不得不下载整个区块来获取所有的交易数据，这会占用大量的带宽和存储空间。

假设我们的这个区块中包含四笔交易：

          [ROOT]
         /      \
      [A]        [B]
    /    \      /    \
 [T1]   [T2]  [T3]  [T4]
  │      │     │      │
交易1   交易2  交易3   交易4

如果用户进行了「交易1」，那他的轻节点中包含数据：

交易1 的全部数据
经过 PoW 验证的可信的区块头（包含 Merkle Root）

我们进行「交易1」的验证：

向全节点请求 Merkle 证明路径（T2 和 B 的哈希值）
用本地的「交易1」计算 T1
用 T1 和获取的 T2 计算 A
用 A 和获取的 B 计算 ROOT
将计算得到的 ROOT 与区块头中存储的 Merkle Root 进行比对
如果比对一致，就证明这笔交易确实被区块链网络接受了

P2P 与 Merkle Tree

在 BitTorrent 等 P2P 网络中，大文件会被分割成多个小块进行传输。为了确保下载的文件块是完整且未被篡改的，需要一个高效的验证机制，这就是 Merkle Tree 的用武之地。

文件分享

首先，如果用户想分享一个文件，要先生成一个种子文件：

先对文件分块：

大文件 ──切分──> [Block1] [Block2] [Block3] [Block4]
                 256MB   256MB   256MB   256MB

再构建 Merkle Tree：

                  [ROOT: abc123...]
                  /              \
          [H1: def456]     [H2: ghi789]
          /          \     /          \
[B1: aaa111] [B2: bbb222] [B3: ccc333] [B4: ddd444]

这样种子文件就创建好了：

{
    "info": {
        "name": "ubuntu-20.04.iso",
        "piece_length": 262144,  // 256MB
        "pieces": [
            "aaa111...", "bbb222...", 
            "ccc333...", "ddd444..."
        ],
        "merkle_root": "abc123...",
        "length": 1073741824     // 1GB
    },
    "announce": "http://tracker.example.com",
    "nodes": [
        ["node1.example.com", 6881],
        ["node2.example.com", 6881]
    ]
}

文件下载

因为文件被分块了，所以在下载时，我们可以并行下载文件的不同分块：