IPFS 原理与实践 (31):IPFS 底层基础 2.5.1

阅读数:1 2019 年 12 月 21 日 18:57

IPFS原理与实践(31):IPFS底层基础 2.5.1

(Merkle Tree)

内容简介
这是一部从实现原理和工程实践两个维度深入讲解 IPFS 和 Filecoin 的著作。作者是中文社区内非常有影响力的三位 IPFS/Filecoin 布道者,本书得到了 IPFS&FileCoin 创始人以及 IPFS 官方(协议实验室)的高度认可和强烈推荐。
为 * 大化满足读者需求,书中不仅介绍 IPFS 技术细节、区块链相关知识、Filecoin 项目技术细节,还加入了大量作者们在开发中的经验和技巧。为了适配当下及未来较长时间内读者的实际使用环境,书中所有案例都是基于生态链中较新的软件开发工具和前沿的软件开发技术编写的。
本书分为三大部分:
第一部分 基础篇(第 1 章)
全面介绍了 IPFS 的源起,概念、优势和应用领域,旨在帮助读者了解 IPFS 相关基础背景知识,从宏观层面认识 IPFS 技术所具有的创新性。
第二部分 原理篇(第 2~5 章)
旨在帮助读者深入理解 IPFS 和 Filecoin 的运行原理与工作机制。首先深入分析了分布式哈希表、块交换协议、版本控制、自验证文件系统 Merkle DAG 和 Merkle Tree 等底层基础知识,然后对 IPFS 协议栈中包含的 7 层子协议了进行了剖析,接着解析了 Multi-Format、libp2p、IPLD 三大 IPFS 核心模块,最后用了一整章的篇幅详细剖析了 Filecoin 项目。
第三部分 实战篇(第 6~8 章)
以工程化的方式,从基础至进阶,介绍了 IPFS 技术的实际使用,包括安装、配置、交互、入网、API、内容发布、数据保存、私网搭建等内容,之后通过两个不同风格的实际项目案例向读者展示了基于不同语言所实现的 IPFS 协议栈的使用方法。

  1. Hash

Hash 是一个把任意长度的数据映射成固定长度数据的函数。例如,对于数据完整性校验,最简单的方法是对整个数据做 Hash 运算,得到固定长度的 Hash 值,然后把得到的 Hash 值公布在网上,这样用户下载到数据之后,对数据再次进行 Hash 运算,将运算结果与网上公布的 Hash 值进行比较,如果两个 Hash 值相等,说明下载的数据没有损坏。可以这样做是因为输入数据的任何改变都会引起 Hash 运算结果的变化,而且根据 Hash 值反推原始输入数据是非常困难的。如果从稳定的服务器进行数据下载,采用单一 Hash 进行验证是可取的。但现实中数据的下载会发生各种意外,如链接中断。一旦数据损坏,就需要重新下载,这种下载方式的效率低下。

  1. Hash List

在点对点网络中做数据传输的时候,会同时从多个机器上下载数据,而且可以认为很多机器是不稳定或者不可信的。为了校验数据的完整性,更好的办法是把大的文件分割成小的数据块(例如,分割成 2KB 为单位的数据块)。这样的好处是,如果小块数据在传输过程中损坏了,那么只要重新下载这一块数据即可,不需要重新下载整个文件。那么,如何确定数据块的完整性呢?只需要为每个数据块计算 Hash 值。BT 下载的时候,在下载到真正数据之前,我们会先下载一个 Hash 列表。那么问题又来了,怎么确定这个 Hash 列表本身是正确的呢?答案是把每个小块数据的 Hash 值拼到一起,然后对这个长字符串再做一次 Hash 运算,这样就得到 Hash 列表的根 Hash(Top Hash 或 Root Hash)。下载数据的时候,首先从可信的数据源得到正确的根 Hash,就可以用它来校验 Hash 列表了,然后即可通过校验后的 Hash 列表校验数据块的完整性。

  1. Merkle Tree

Merkle Tree 可以看作 Hash List 的泛化(Hash List 可以看作一种特殊的 Merkle Tree,即树高为 2 的多叉 Merkle Tree)。

在最底层,和 Hash 列表一样,把数据分成小的数据块,有相应的 Hash 与它对应。但是往上走,并不是直接去运算根 Hash,而是把相邻的两个 Hash 合并成一个字符串,然后运算这个字符串的 Hash。这样每两个 Hash 就“结婚生子”,得到了一个“子 Hash”。如果最底层的 Hash 总数是单数,那到最后必然出现一个“单身 Hash”,这种情况就直接对它进行 Hash 运算,所以也能得到它的“子 Hash”。于是往上推,依然是一样的方式,可以得到数目更少的新一级 Hash,最终形成一棵倒挂的树,树根位置就是树的根 Hash,我们把它称为 Merkle Root。

在 P2P 网络下载之前,先从可信的源获得文件的 Merkle Tree 树根。一旦获得了树根,就可以从其他从不可信的源获取 Merkle Tree。通过可信的树根来检查接收到的 Merkle Tree。如果 Merkle Tree 是损坏的或者是虚假的,就从其他源获得另一个 Merkle Tree,直到获得一个与可信树根匹配的 Merkle Tree。

  1. Merkle Tree 的特点

Merkle Tree 是一种树,大多数是二叉树,也可以是多叉树。无论是几叉树,它都具有树结构的所有特点。

1)Merkle Tree 的叶子节点的 value 是数据集合的单元数据或者单元数据 Hash。

2)非叶子节点的 value 是根据它下面所有的叶子节点值,按照哈希算法计算而得出的。

通常,使用哈希算法(例如:SHA-2 和 MD5)来生成数据的 Hash 值。但如果目的仅仅是防止数据不被蓄意的损坏或篡改,可以使用安全性低但效率高的校验算法,如 CRC。

Merkle Tree 和 Hash List 的主要区别是,可以直接下载并立即验证 Merkle Tree 的一个分支。因为可以将文件切分成小的数据块,这样如果有一块数据损坏,仅仅重新下载这个数据块就行了。如果文件非常大,那么 Merkle Tree 和 Hash List 都很大,但是 Merkle Tree 可以一次下载一个分支,然后立即验证这个分支,如果分支验证通过,就可以下载数据了;而 Hash List 只有下载整个 Hash List 才能验证。

  1. Merkle Tree 的应用
  • 数字签名:最初 Merkle Tree 的目的是高效处理 Lamport 单次签名。每一个 Lamport 密钥只能被用来签名一个消息,但是与 Merkle Tree 结合起来可以签名多个消息。这种方法成为一种高效的数字签名框架,即 Merkle 签名方法。
  • P2P 网络:在 P2P 网络中,Merkle Tree 用来确保从其他节点接收的数据块没有损坏且没有被替换,甚至检查其他节点不会欺骗或者发布虚假的块。在 2.2 节中,我们提到了 BitTorrent 使用 P2P 技术来让客户端之间进行数据传输,一来可以加快数据下载速度,二来减轻下载服务器的负担。一个相关的问题是大数据块的使用,因为为了保持 torrent 文件非常小,那么数据块 Hash 的数量也得很小,这就意味着每个数据块相对较大。大数据块影响节点之间进行交易的效率,因为只有当大数据块全部下载下来并通过校验后,才能与其他节点进行交易。为解决上面两个问题:用一个简单的 Merkle Tree 代替 Hash List。设计一个层数足够多的满二叉树,叶节点是数据块的 Hash,不足的叶节点用 0 来代替。上层的节点是其对应孩子节点串联的 Hash。Hash 算法和普通 torrent 一样采用 SHA-1。
  • 比特币:Merkle Proof 最早的应用是 Bitcoin(比特币),它是由中本聪在 2009 年描述并创建的。Bitcoin 的 Blockchain 利用 Merkle proofs 来存储每个区块的交易。而这样做的好处也就是中本聪描述到的“简化支付验证”(Simplified Payment Verification,SPV)的概念:一个“轻客户端”(light client)可以仅下载链的区块头,即每个区块中的 80 字节的数据块,仅包含 5 个元素,而不是下载每一笔交易以及每一个区块。5 个元素为上一区块头的 Hash 值、时间戳、挖矿难度值、工作量证明随机数(nonce)以及包含该区块交易的 Merkle Tree 的根 Hash。

如果客户端想要确认一个交易的状态,它只需简单地发起一个 Merkle Proof 请求,这个请求显示出这个特定的交易在 Merkle Tree 的一个叶子节点之中,而且这个 Merkle Tree 的树根在主链的一个区块头中。但是 Bitcoin 的轻客户端有它的局限。一个局限是,尽管它可以证明包含的交易,但是它不能进行涉及当前状态的证明(如数字资产的持有、名称注册、金融合约的状态等)。Bitcoin 如何查询你当前有多少币?一个比特币轻客户端可以使用一种协议,它涉及查询多个节点,并相信其中至少会有一个节点会通知你关于你的地址中任何特定的交易支出,而这可以让你实现更多的应用。但对于其他更为复杂的应用而言,这些是远远不够的。影响一笔交易的确切性质(precise nature),取决于此前的几笔交易,而这些交易本身则依赖于更为前面的交易,所以最终你可以验证整个链上的每一笔交易。

IPFS原理与实践(31):IPFS底层基础 2.5.1

购书地址 https://item.jd.com/12665074.html?dist=jd

评论

发布