从区块链到分布式账本系列之九

写在前面

这是<从区块链到分布式账本>系列第九篇.

大周末的有点犯懒, 本篇计划更新一点简单的内容: Merkle Tree (默克尔树).

关于Merkle Tree, 我在从区块链到分布式账本系列之三 - 区块链简介 这篇里面介绍到区块链的时候, 简单展示了一下. 这篇更新计划中, 稍微往前走一步, 多聊一点这个技术点.

Merkle树

先来看下下图, 对Merkle树有一个直观上的认识.

(图片来自互联网, 侵删)

从图中可以看出来, 默克尔树本质上是一种哈希树 (哈希前面已经简单介绍了).

首先这里的树, 在计算机中作为一种重要的数据结构, 是一种存储管理数据的逻辑结构. 这棵树是由一个根节点, 一组中间节点, 和一组叶子节点组成的. 其中最下面一层的叶子节点存储的是数据块的哈希值, 然后叶子节点的父节点存储叶子节点的哈希值汇总后的哈希值, 依次类推, 直到产生Merkle的根节点.

至此, Merkle树就介绍完了😓.

Merkle 更多点

如果是关于介绍Merkle树本身的, Merkle其实并不是很复杂的结构, 那么此篇可以到此结束了. (略有点敷衍了)

Merkle树作为一个密码学领域内的算是比较常用的工具, 当然也用在了我最近的论文里面. 这里结合信息安全领域的一些内容, 再简单多聊一些.

本质上看, 默克尔树的最重要特点是什么? 应该就算底层的任何数据变动都会传递到其父亲节点, 然后直到根节点. 这源于哈希函数的单向性, 以及逆向困难性. 那么默克尔树可以用来做什么事情呢? 简单来说就是其应用价值. 除去我们之前说的比特币中的使用到了默克尔树, 其实后续以太坊里(另一种基于区块链的智能合约系统)也使用到了默克尔树的变种, Merkle Patricia Tree.

但从本质上看默克尔树, 它可以用来快速比较大量数据, 即为大数据生成其对应的Merkle树, 然后需要对比两个大数据是否一致的时候, 直接比较其默克尔树的根节点即可确保两个大数据是否一致了. 根据这个特点, 进一步可以联想到P2P下载中, 也就是我们说的点对点下载工具, uTorrent, BitTorrent. 我们下载电影常用的所谓的种子文件(torrent)其中就应用到了这项技术. 这里的P2P下载技术原理, 这里不再扩展开来. 总之, 主要使用的就是Merkle树的快速对比验证功能.

那么还有什么应用呢? 比如说快速发现数据的修改点. 如果我们事先保留一份数据的Merkle树, 然后如果一个数据某一部分发生变化的时候, 我们先生成这个数据新的Merkle树, 然后根据两个树的差别, 从根节点开始, 就可以一路顺着下去迅速定位数据的修改点.

再往前推进一步, 讲个新的概念, 如何用在零知识证明中去. 当然, 我们先科普下零知识证明是什么. 零知识证明也是密码学领域中一个重要的分支. 用一个通俗的例子来介绍. 假设A拥有一个房间的钥匙, 他需要向B证明他拥有了房间的钥匙, 但是又不能让B知道房间里面的样子, 也不能让B看到钥匙的模样. 那么怎么办呢? 就是A从房间里面拿出某个东西, 这个东西大家都知道只有这个房间有. 那么B就可以相信A拥有了房间的钥匙. 这个过程中就可以简单概括为零知识证明. 那么怎么使用默克尔树来做零知识证明呢?

比如, 我们有一串数据(d1, d2, d3, …, d10), 那么我们怎么怎么其中包含了数据d2呢. 我们先构造一颗默克尔树, 然后公布d2到根节点这条路径上的节点, 以及其兄弟节点. 那么其他验证者, 就可以根据这些信息算出来, d2是存在的, 但是却没有办法知道d2的具体内容.

待续…

坚持原创技术分享,您的支持将鼓励我继续创作!
0%