Merkle Tree and Zero Knowledge Proof

最近在看的一篇论文中有说到两个我一直都不太清楚的两个概念,今天就花时间总结了一下。

1.Merkle Tree

Merkle Tree

以上是Merkle Tree 工作原理的详细说明,最底层叶子结点表示实际数据的Hash,此后每两个结点连接起来进行 Hash 加密,直到最顶层。 下图引用自上述网址

Merkle Tree and Zero Knowledge Proof

我们总是需要传输文件,而当需要传输确认的文件过大时,对网络的要求是极高的,因此通常需要将文件拆分成很多小的数据块,分批传输。但是如何确保小的数据块是没有被损坏的呢?这就需要用到Mercle Tree了。Mercle Tree 很好的解决了数据验证问题,并且能够很快定位到错误的数据块,这是因为Mercle Tree包含了文件的所有数据块的Hash结果。

应用1:两个机器上各有一个文件,我们需要比对这两个大文件是否是一样的。要求:两个机器上都构建了文件的Merkle Tree

从根节点开始比对,如果根节点一致,继续比对下一层,直到定位到不一致的叶子结点。

Merkle Tree and Zero Knowledge Proof

应用2:区块链中存储交易。

在区块链中,每增加一个交易,就会生成该交易的Hash,这个Hash与之前的交易Hash连接,继续向上生成Hash, 最终得到一个新的根节点。以此保证每添加一个新的交易就会对应不同的梅克尔树根节点。

应用3:区块链中交易的确认

比特币系统如何验证一笔交易的合法性?即,如何确认一笔交易已经被包含在区块中。可以通过merkle tree来实现快速验证。Merkle Tree的根节点是公开可信的,因此当我们想要验证一个交易的hash  HK 是否包含在 Merkle Tree 中时,我们只需要用到由下图中四个蓝色框代表的Hash组成的认证路径即可完成验证。有了蓝色框的Hash,我们就可以计算得到虚线框的值,如果最终得到的根节点与已知公开可信的根节点一致。则说明,Hash值为 HK 的这笔交易包含在区块中。

Merkle Tree and Zero Knowledge Proof

具体认证路径的生成,主要是通过遍历。有专门的算法,有兴趣的可以自行搜索相关的论文 ,参考网址的第三个就有说到怎么生成merkle tree的认证路径。

参考:

https://www.cnblogs.com/fengzhiwu/p/5524324.html

https://www.jianshu.com/p/a6bc56193b57

https://www.tangshuang.net/4117.html

https://www.tangshuang.net/blockchain

 

2. Zero Knowledge Proof 零知识证明

首先,引用一下百度百科对零知识证明的定义:证明者能够在不向验证者提供任何有用的信息的情况下,使验证者相信某个论断是正确的。百度百科同时给出了几个简单的例子用于说明零知识证明的案例:

Merkle Tree and Zero Knowledge Proof

Merkle Tree and Zero Knowledge Proof

这里我们给出一个有关零知识证明的非常经典的例子,来帮助大家理解:

阿里巴巴被强盗抓住,为了保命,他需要向强盗证明自己拥有打开石门的口令,同时又不能把密码告诉强盗。他想出一个解决办法,先让强盗离开自己一箭之地,距离足够远让强盗无法听到口令,足够近让阿里巴巴无法在强盗的弓箭下逃生。

如果强盗举起左手,阿里巴巴就使用口令将石门打开,如果举起右手,就将石门关闭。阿里巴巴就在这个距离下向强盗展示了石门的打开和关闭。如果每次都能正确打开和关闭大门,则证实阿里巴巴确实知道石门的密码。

零知识证明的应用和理论远不止于此,加油学习叭!

参考

https://baike.baidu.com/item/%E9%9B%B6%E7%9F%A5%E8%AF%86%E8%AF%81%E6%98%8E

 

上一篇:区块链技术与应用【肖臻老师】笔记整理之------16-BTC-匿名性


下一篇:比特币系统数据结构 Merkle tree