第9章：Merkle DAG
9.1 Merkle树原理
Merkle树（哈希树）是一种二叉树结构，其中每个叶节点是数据块的哈希值，每个非叶节点是其子节点哈希值的哈希。这种结构提供了高效的数据完整性验证。
Merkle树结构：
Root Hash
/ \
Hash A Hash B
/ \ / \
Hash1 Hash2 Hash3 Hash4
| | | |
Data1 Data2 Data3 Data4验证过程：
class MerkleTree {
constructor(leaves) {
this.leaves = leaves.map(data => this.hash(data));
this.tree = this.buildTree(this.leaves);
}
buildTree(leaves) {
if (leaves.length === 1) return leaves;
const nextLevel = [];
for (let i = 0; i < leaves.length; i += 2) {
const left = leaves[i];
const right = leaves[i + 1] || left; // 奇数情况处理
nextLevel.push(this.hash(left + right));
}
return this.buildTree(nextLevel);
}
// 生成证明路径
getProof(leafIndex) {
const proof = [];
let currentIndex = leafIndex;
let currentLevel = this.leaves;
while (currentLevel.length > 1) {
const siblingIndex = currentIndex % 2 === 0 ? currentIndex + 1 : currentIndex - 1;
if (siblingIndex < currentLevel.length) {
proof.push({
hash: currentLevel[siblingIndex],
direction: currentIndex % 2 === 0 ? 'right' : 'left'
});
}
currentIndex = Math.floor(currentIndex / 2);
currentLevel = this.getParentLevel(currentLevel);
}
return proof;
}
// 验证证明
static verifyProof(leafHash, proof, rootHash) {
let computedHash = leafHash;
for (const proofElement of proof) {
if (proofElement.direction === 'right') {
computedHash = hash(computedHash + proofElement.hash);
} else {
computedHash = hash(proofElement.hash + computedHash);
}
}
return computedHash === rootHash;
}
}9.2 DAG（有向无环图）结构
IPFS使用Merkle DAG（有向无环图）作为核心数据结构，与简单的Merkle树相比，DAG提供了更灵活的链接机制。
DAG特性：
- 有向性：链接有方向，从父节点指向子节点
- 无环性：不存在循环路径
- 内容寻址：每个节点通过哈希值标识
- 不可变性：节点内容改变会改变其哈希值
DAG结构示例：
Website Root
/ \
Index.html CSS/
/ \
Images/ main.css
/ | \
logo.png header.jpg bg.pngDAG操作：
class MerkleDAG {
constructor() {
this.nodes = new Map();
}
// 创建节点
createNode(data, links = []) {
const node = {
data: data,
links: links.map(link => ({
name: link.name,
cid: link.cid,
size: link.size
}))
};
// 计算节点CID
const cid = this.computeCID(node);
this.nodes.set(cid.toString(), node);
return { cid, node };
}
// 获取节点
getNode(cid) {
return this.nodes.get(cid.toString());
}
// 遍历DAG
async *traverse(cid, visited = new Set()) {
if (visited.has(cid.toString())) {
return; // 避免循环（虽然DAG理论上无环）
}
visited.add(cid.toString());
const node = this.getNode(cid);
if (!node) {
throw new Error(`Node not found: ${cid}`);
}
yield { cid, node };
// 递归遍历子节点
for (const link of node.links) {
yield* this.traverse(link.cid, visited);
}
}
// 查找路径
async resolvePath(rootCid, path) {
const parts = path.split('/').filter(p => p);
let currentCid = rootCid;
for (const part of parts) {
const node = this.getNode(currentCid);
if (!node) {
throw new Error(`Node not found: ${currentCid}`);
}
const link = node.links.find(l => l.name === part);
if (!link) {
throw new Error(`Link not found: ${part}`);
}
currentCid = link.cid;
}
return currentCid;
}
}9.3 内容验证和完整性
Merkle DAG提供了强大的内容验证机制：
完整性验证：
class ContentVerifier {
// 验证单个节点
verifyNode(node, cid) {
const computedCID = this.computeCID(node);
return computedCID.equals(cid);
}
// 验证子图完整性
async verifySubgraph(rootCid, verifier) {
for await (const { cid, node } of this.dag.traverse(rootCid)) {
if (!verifier(node, cid)) {
return {
valid: false,
error: `Invalid node: ${cid}`,
node: node
};
}
}
return { valid: true };
}
// 验证文件完整性
async verifyFile(fileCid, expectedSize = null) {
let totalSize = 0;
const chunks = [];
for await (const { cid, node } of this.dag.traverse(fileCid)) {
if (node.data) {
totalSize += node.data.length;
chunks.push(node.data);
}
}
// 验证总大小
if (expectedSize && totalSize !== expectedSize) {
return {
valid: false,
error: `Size mismatch: expected ${expectedSize}, got ${totalSize}`
};
}
// 重新组合并验证哈希
const combinedData = Buffer.concat(chunks);
const computedCID = await this.computeFileCID(combinedData);
return {
valid: computedCID.equals(fileCid),
size: totalSize,
data: combinedData
};
}
}9.4 版本控制和分支管理
Merkle DAG天然支持版本控制：
版本历史：
class VersionControl {
constructor(dag) {
this.dag = dag;
this.versions = new Map();
}
// 创建新版本
createVersion(baseCid, changes, versionName) {
// 1. 获取基础版本
const baseNode = this.dag.getNode(baseCid);
// 2. 应用变更
const newNode = this.applyChanges(baseNode, changes);
// 3. 创建新节点
const { cid: newCid } = this.dag.createNode(newNode.data, newNode.links);
// 4. 记录版本信息
this.versions.set(versionName, {
cid: newCid,
parent: baseCid,
timestamp: Date.now(),
changes: changes
});
return newCid;
}
// 创建分支
createBranch(baseCid, branchName) {
const branch = {
name: branchName,
head: baseCid,
created: Date.now(),
versions: [baseCid]
};
this.branches.set(branchName, branch);
return branch;
}
// 合并分支
async mergeBranches(sourceBranch, targetBranch, mergeStrategy = 'recursive') {
const sourceHead = this.branches.get(sourceBranch).head;
const targetHead = this.branches.get(targetBranch).head;
// 找到共同祖先
const commonAncestor = await this.findCommonAncestor(sourceHead, targetHead);
if (!commonAncestor) {
throw new Error('No common ancestor found');
}
// 根据策略执行合并
switch (mergeStrategy) {
case 'recursive':
return this.recursiveMerge(commonAncestor, sourceHead, targetHead);
case 'octopus':
return this.octopusMerge([sourceHead, targetHead]);
default:
throw new Error(`Unknown merge strategy: ${mergeStrategy}`);
}
}
// 获取版本差异
async getDiff(cid1, cid2) {
const nodes1 = await this.collectNodes(cid1);
const nodes2 = await this.collectNodes(cid2);
const diff = {
added: [],
removed: [],
modified: []
};
// 比较两个版本的节点
for (const [cid, node] of nodes2) {
if (!nodes1.has(cid)) {
diff.added.push({ cid, node });
} else if (JSON.stringify(nodes1.get(cid)) !== JSON.stringify(node)) {
diff.modified.push({
before: nodes1.get(cid),
after: node,
cid: cid
});
}
}
for (const [cid, node] of nodes1) {
if (!nodes2.has(cid)) {
diff.removed.push({ cid, node });
}
}
return diff;
}
}9.5 实际案例分析
让我们通过一个实际的文件系统案例来理解Merkle DAG的应用：
文件系统实现：
class IPFSFileSystem {
constructor(dag) {
this.dag = dag;
}
// 添加文件
async addFile(filePath, content) {
// 1. 创建文件节点
const fileNode = {
type: 'file',
data: content,
metadata: {
name: filePath.split('/').pop(),
size: content.length,
created: Date.now(),
modified: Date.now()
}
};
const { cid: fileCid } = this.dag.createNode(fileNode, []);
// 2. 更新目录结构
await this.updateDirectory(filePath, fileCid);
return fileCid;
}
// 创建目录
async createDirectory(dirPath) {
const dirNode = {
type: 'directory',
data: null,
metadata: {
name: dirPath.split('/').pop(),
created: Date.now(),
modified: Date.now()
}
};
const { cid: dirCid } = this.dag.createNode(dirNode, []);
// 如果是子目录，更新父目录
if (dirPath.includes('/')) {
await this.updateDirectory(dirPath, dirCid);
}
return dirCid;
}
// 读取文件
async readFile(fileCid) {
const fileNode = this.dag.getNode(fileCid);
if (!fileNode || fileNode.type !== 'file') {
throw new Error('Invalid file node');
}
return {
content: fileNode.data,
metadata: fileNode.metadata
};
}
// 列出目录内容
async listDirectory(dirCid) {
const dirNode = this.dag.getNode(dirCid);
if (!dirNode || dirNode.type !== 'directory') {
throw new Error('Invalid directory node');
}
const contents = [];
for (const link of dirNode.links) {
const childNode = this.dag.getNode(link.cid);
contents.push({
name: link.name,
type: childNode.type,
size: childNode.metadata?.size || 0,
cid: link.cid
});
}
return contents;
}
// 验证文件系统完整性
async verifyFileSystem(rootCid) {
const errors = [];
for await (const { cid, node } of this.dag.traverse(rootCid)) {
// 检查节点类型
if (!['file', 'directory'].includes(node.type)) {
errors.push({
type: 'invalid_type',
cid: cid,
message: `Invalid node type: ${node.type}`
});
}
// 检查文件大小
if (node.type === 'file' && node.metadata) {
const actualSize = node.data ? node.data.length : 0;
if (actualSize !== node.metadata.size) {
errors.push({
type: 'size_mismatch',
cid: cid,
message: `Size mismatch: expected ${node.metadata.size}, got ${actualSize}`
});
}
}
// 检查目录链接
if (node.type === 'directory') {
for (const link of node.links) {
const childNode = this.dag.getNode(link.cid);
if (!childNode) {
errors.push({
type: 'missing_child',
cid: cid,
childCid: link.cid,
message: `Missing child node: ${link.cid}`
});
}
}
}
}
return {
valid: errors.length === 0,
errors: errors,
totalNodes: (await this.dag.traverse(rootCid)).length
};
}
}
// 使用示例
async function demonstrateFileSystem() {
const dag = new MerkleDAG();
const fs = new IPFSFileSystem(dag);
// 创建文件
const file1Cid = await fs.addFile('/documents/report.txt',
Buffer.from('This is a quarterly report'));
const file2Cid = await fs.addFile('/documents/summary.txt',
Buffer.from('Executive summary'));
// 创建目录
const dirCid = await fs.createDirectory('/documents');
// 验证文件系统
const verification = await fs.verifyFileSystem(dirCid);
console.log('文件系统验证结果:', verification);
return { file1Cid, file2Cid, dirCid };
}这个案例展示了如何使用Merkle DAG构建一个完整的文件系统，包括文件存储、目录管理、完整性验证等功能。通过Merkle DAG的特性，我们获得了数据完整性、版本控制、去重等天然优势。