2018-08-16 15:58 区块链 https://www.sohu.com/tag/77545 / 技术 https://www.sohu.com/tag/65790
MerkleDAG 作为 IPFS 的核心数据结构, 它融合了 Merkle Tree 和 DAG 的优点, 今天阿信带大家一起来探究什么是 MerkleDAG, 拆分解说 Merkle Tree,DAG 有向无环图, MerkleDAG 在 IPFS 中的应用.
MerkleDAG 树形结构图
Merkle Tree
Merkle Tree 是由美国计算机学家 Merkle 于 1979 年申请的专利. Merkle Tree 通常也被称作 Hash Tree, 顾名思义, 就是存储 hash 值的一棵树.
1 那么, hash 是什么
? Hash 是一个把任意长度的数据映射成固定长度数据的函数
? 输入数据的改变会得出不同的 hash 结果
2 Hash List
点对点网络传输中, 文件拆分, 拆分后的小的数据块的 hash 组合成了 hash list. 在传输过程中, 如文件损坏了, 只要重新下载损坏部分的数据块即可.
3 Merkle Tree
? Merkle Tree 大多数是二叉树, 也可以多叉树;
? 叶子节点的 value 是数据集合的单元数据或者单元数据 HASH;
? 非叶子节点的 value 是根据它下面所有的叶子节点值, 然后按照 Hash 算法计算而得出的.
? 层层计算而形成的树形结构
DAG 有向无环图
1 DAG 起源
? 2013 年, 以色列希伯来学者在 bitcointalik 提出 GHOST 协议, 引入 DAG 概念, 作为比特币的交易处理能力扩容解决方案 ? 随后, NXT 社区提出用 DAG 的拓扑结构来存储区块 ? 2015 年 9 月, Sergio Demian Lerner 发表了 《DagCoin: a cryptocurrency without blocks》. 交易发起后, 直接广播全网, 跳过打包区块阶段. ? 2016 年 7 月, IOTA 横空出世, 随后 ByteBall 也闪亮登场
2 DAG 介绍
DAG 英文全称为: directed acyclic graph. 有向无环图, 有方向无环路.
假设当你发布新交易时, 那么你的单元会主动同时链接到前面两个有效单元之中, DAG 中的每个新单元, 验证并确认其父单元, 以及父单元的父单元, 慢慢可达创世单元, 并将其父单元的哈希包含到自己的单元里面. 随着时间递增, 所有交易单元相互连接, 形成图状结构, 如若要更改数据, 那就不仅仅是几个单元数据的问题了, 而是整个拓扑图的数据更改. DAG 这个模式相比来说, 要进行的复杂度更高, 更难以被更改.
区块链链式数据结构
DAG 的拓扑数据结构
1 和 2 号是创世单元; 第 3 个单元产生时, 只需要确认 1 号和 2 号的交易; 第 4 个单元产生时, 只需要确认 2 号和 3 号, 以此类推.
区块链的基础是分布式账本, 而分布式账本的基础是分布式网络; 分布式账本是不是一定要是区块链呢? 不一定, 它还可以是 DAG, 也就是有向无环图, DAG 不是区块链, 当然你非要把它看成一条链也没毛病, 但它是一条没有区块的链!
MerkleDAG
1 MerkleDAG 功能
Merkle DAG 拥有如下的功能:
? 内容寻址: 使用多重哈希来唯一识别一个数据块的内容
? 防篡改: 可以方便的检查哈希值来确认数据是否被篡改
? 去重: 由于内容相同的数据块哈希是相同的, 可以很容去掉重复的数据, 节省存储空间
2 MerkleDAG 树形结构构建过程
在 IPFS 网络中, 存储文件时, 首先会将文件切片, 切割成 256KB 大小的文件. 之后循环调用 (MerkleDAG.Add) 方法构建文件 MerkleDAG. 文件 hash 值创建流程: 1: 将切片之后的文件进行 sha-256 运算 2: 将运算结果选取 0~31 位 3: 将选取结果根据 base58 编码, 运算结果前追加 Qm 即为最后结果作为文件的 46 位 hash 值 根据 IPFS 底层代码计算, Merkle DAG 为多叉树结构, 最多为 174 叉树.
3 DAGService 维护
在源代码之中通常使用 DAGService 维护 MerkleDAG, 为 MerkleDAG 提供删除和增加的权限, 源代码如下:
官网: http://ipfsforce.com
公众号: IPFS 原力区
币快报社群: IPFS 原力区
微博: http://weibo.com/ipfsforce
IPFS 原力区
IPFS 原力区是全球第一大 IPFS 价值生态社区, 总部位于上海, 聚集了众多技术大咖和 IPFS 爱好者; IPFS 原力区秉持: 价值, 共建, 共赢, 荣耀的文化理念; 提供全面, 精细, 优质的 IPFS 咨询和技术支持, 将生态中的爱好者转化为 IPFS 支持者和参与者. 未来, IPFS 原力区做好价值文化基因传播, 紧盯人工智能, 量子计算, 大数据等前沿科技, 把 IPFS 区块链技术随时架设在最新的技术基础之上, 推动 IPFS 生态的健康发展. 返回搜狐, 查看更多 https://www.sohu.com/?strategyid=00001
[转帖]MerkleDAG 全面解析 一文读懂什么是默克尔有向无环图
来源: http://www.bubuko.com/infodetail-2898876.html