p2p、分布式,区块链笔记: Merkle-DAG和Merkle-Tree的区别与联系

2024-09-01 14:04

本文主要是介绍p2p、分布式,区块链笔记: Merkle-DAG和Merkle-Tree的区别与联系,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Merkle-DAG和Merkle-Tree的区别与联系

  1. 结构:

    • Merkle-Tree 是一种二叉树结构,每个非叶子节点是其子节点哈希的哈希。它具有层次结构,通常用于验证数据的完整性。
    • Merkle-DAG(有向无环图)是一种更通用的图结构,其一个节点可以有多个父节点和子节点。它允许更复杂的链接关系和非线性结构,适用于记录和追踪变更,支持广泛的并行操作和高效的增量更新。Merkle DAG 类似于 Merkle 树,但没有余额要求,每个节点都可以携带一个有效载荷。在 DAG 中,多个分支可以重新收敛,或者换句话说,一个节点可以有多个父节点。
  2. 用途:

    • Merkle-Tree 通常用于区块链和文件系统中以验证数据块的完整性(如 Bitcoin 和 Git)。
    • Merkle-DAG 用于数据去重和版本控制(如 IPFS),支持更灵活的数据组织和高效的同步。

CODE

  • 项目地址:https://github.com/zaphar/merkle-dag/blob/main/src/dag/mod.rs

NODE结构体

  • node.rs中定义了一个在Merkle DAG(有向无环图)中使用的节点结构体(Node)。每个节点包含一个有效载荷(item)和一组依赖ID(dependency_ids)。节点的唯一标识符(id)是由有效载荷和依赖ID的字节组合而成,确保相同的有效载荷和依赖ID总是有相同的ID。
// 代码位置 https://github1s.com/zaphar/merkle-dag/blob/main/src/node.rs#L51-L62
#[derive(Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(from = "NodeSerde")]
pub struct Node<HW> // <HW> 为泛型参数
whereHW: HashWriter, //  where为泛型约束,泛型参数 HW 必须实现 HashWriter trait
{id: Vec<u8>,item: Vec<u8>,item_id: Vec<u8>,dependency_ids: BTreeSet<Vec<u8>>,_phantom: PhantomData<HW>,
}

add_node函数

函数签名

pub fn add_node<'a, N: Into<Vec<u8>>>(&'a mut self,item: N,dependency_ids: BTreeSet<Vec<u8>>,
) -> Result<Vec<u8>>
  • 'a: 生命周期标注,表明函数借用的是 self 的生命周期。
  • N: Into<Vec<u8>>: 泛型参数 N,它可以转换为 Vec<u8>
  • item: 节点的负载数据,将被转换为 Vec<u8>
  • dependency_ids: 节点的依赖 ID 集合,每个 ID 是 Vec<u8> 类型。
  • Result<Vec<u8>>: 函数返回一个结果,如果成功,返回新节点的 ID;如果失败,返回错误。

函数解释

  • add_node 函数负责将一个带有依赖关系的新节点添加到 Merkle-DAG 中。它首先检查节点是否已经存在,处理依赖关系,并更新节点存储和根集合。该函数确保节点的添加操作是幂等的,即对于相同的输入,结果不会发生变化。

在这里插入图片描述

/// 添加一个新负载及其依赖 ID 集合。此方法将构建一个新节点,并将其添加到 DAG 中。
/// 对于任何给定的输入,该方法是幂等的。
///
/// 不创建节点然后再添加的一个结果是,确保始终满足 merkle-crdt 白皮书中的实现规则。
pub fn add_node<'a, N: Into<Vec<u8>>>(&'a mut self,item: N,dependency_ids: BTreeSet<Vec<u8>>,
) -> Result<Vec<u8>> {// 使用提供的负载和依赖 ID 创建一个新节点实例。let node = Node::<HW>::new(item.into(), dependency_ids.clone());// 获取新创建的节点的 ID。let id = node.id().to_vec();// 检查节点是否已经存在于存储中。if self.nodes.contains(id.as_slice())? {// 如果节点已存在,则返回该节点的 ID。return Ok(self.nodes.get(id.as_slice()).unwrap().unwrap().id().to_vec());}// 初始化一个向量,用于记录需要从根集合中移除的节点。let mut root_removals = Vec::new();// 遍历所有的依赖 ID。for dep_id in dependency_ids.iter() {// 检查每个依赖节点是否存在于存储中。if !self.nodes.contains(dep_id)? {// 如果任何依赖节点不存在,则返回错误。return Err(StoreError::NoSuchDependents);}// 如果某个依赖 ID 存在于根集合中,则将其标记为需要移除。if self.roots.contains(dep_id) {root_removals.push(dep_id);}}// 更新根集合// 将新节点存储到节点存储中。self.nodes.store(node)?; // https://github1s.com/zaphar/merkle-dag/blob/main/src/store.rs// 从根集合中移除被标记的节点。for removal in root_removals {self.roots.remove(removal);}// 将新节点的 ID 添加到根集合中。self.roots.insert(id.to_vec());// 返回新节点的 ID。Ok(id.to_vec())
}

函数调用

  1. TestDag别名类型:

    // https://github1s.com/zaphar/merkle-dag/blob/main/src/test.rs#L19-L22
    type TestDag<'a> = Merkle<BTreeMap<Vec<u8>, Node<std::collections::hash_map::DefaultHasher>>,std::collections::hash_map::DefaultHasher,
    >;
    
    • Merkle 的第一个泛型参数是 BTreeMap<Vec<u8>, Node<std::collections::hash_map::DefaultHasher>>,它是一个键为 Vec<u8>,值为 Node<DefaultHasher> 的映射。
    • 第二个泛型参数是 DefaultHasher,它是一个标准库提供的哈希算法。
  2. 测试函数:

    // https://github1s.com/zaphar/merkle-dag/blob/main/src/test.rs#L26-L27
    #[test]
    fn test_root_pointer_hygiene() {let mut dag = TestDag::new(BTreeMap::new());let quax_node_id = dag.add_node("quax", BTreeSet::new()).unwrap();
    }
    
    • #[test] 属性标记此函数为测试函数。
    • dag 通过 TestDag::new(BTreeMap::new()) 创建一个新的 TestDag 实例,传入一个空的 BTreeMap
    • quax_node_id 调用 dag.add_node("quax", BTreeSet::new()) 方法添加一个新节点,节点 ID 被赋值给 quax_node_idunwrap() 处理可能出现的错误,确保成功添加节点。

CG

  • IPFS白皮书
  • DAG Builder 可视化工具
  • Merkle DAG implementation for IPLD in Python
  • 基于 Merkle-DAG 的并发版本历史系统实现

这篇关于p2p、分布式,区块链笔记: Merkle-DAG和Merkle-Tree的区别与联系的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1127139

相关文章

分辨率三兄弟LPI、DPI 和 PPI有什么区别? 搞清分辨率的那些事儿

《分辨率三兄弟LPI、DPI和PPI有什么区别?搞清分辨率的那些事儿》分辨率这个东西,真的是让人又爱又恨,为了搞清楚它,我可是翻阅了不少资料,最后发现“小7的背包”的解释最让我茅塞顿开,于是,我... 在谈到分辨率时,我们经常会遇到三个相似的缩写:PPI、DPI 和 LPI。虽然它们看起来差不多,但实际应用

GORM中Model和Table的区别及使用

《GORM中Model和Table的区别及使用》Model和Table是两种与数据库表交互的核心方法,但它们的用途和行为存在著差异,本文主要介绍了GORM中Model和Table的区别及使用,具有一... 目录1. Model 的作用与特点1.1 核心用途1.2 行为特点1.3 示例China编程代码2. Tab

Nginx指令add_header和proxy_set_header的区别及说明

《Nginx指令add_header和proxy_set_header的区别及说明》:本文主要介绍Nginx指令add_header和proxy_set_header的区别及说明,具有很好的参考价... 目录Nginx指令add_header和proxy_set_header区别如何理解反向代理?proxy

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

redis+lua实现分布式限流的示例

《redis+lua实现分布式限流的示例》本文主要介绍了redis+lua实现分布式限流的示例,可以实现复杂的限流逻辑,如滑动窗口限流,并且避免了多步操作导致的并发问题,具有一定的参考价值,感兴趣的可... 目录为什么使用Redis+Lua实现分布式限流使用ZSET也可以实现限流,为什么选择lua的方式实现

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

Spring中@RestController和@Controller的使用及区别

《Spring中@RestController和@Controller的使用及区别》:本文主要介绍Spring中@RestController和@Controller的使用及区别,具有很好的参考价... 目录Spring中@RestController和@Controller使用及区别1. 基本定义2. 使

Qt 中 isHidden 和 isVisible 的区别与使用小结

《Qt中isHidden和isVisible的区别与使用小结》Qt中的isHidden()和isVisible()方法都用于查询组件显示或隐藏状态,然而,它们有很大的区别,了解它们对于正确操... 目录1. 基础概念2. 区别清见3. 实际案例4. 注意事项5. 总结1. 基础概念Qt 中的 isHidd

Spring、Spring Boot、Spring Cloud 的区别与联系分析

《Spring、SpringBoot、SpringCloud的区别与联系分析》Spring、SpringBoot和SpringCloud是Java开发中常用的框架,分别针对企业级应用开发、快速开... 目录1. Spring 框架2. Spring Boot3. Spring Cloud总结1. Sprin

Java中的runnable 和 callable 区别解析

《Java中的runnable和callable区别解析》Runnable接口用于定义不需要返回结果的任务,而Callable接口可以返回结果并抛出异常,通常与Future结合使用,Runnab... 目录1. Runnable接口1.1 Runnable的定义1.2 Runnable的特点1.3 使用Ru