MerkleTree与零知识证明

  • R4y 
  • 未分类

默克尔树这个数据结构,至于区块链就是他的骨架了。 之前的文章对默克尔树是什么做了个十分十分简单的介绍。最近啃书,又看见了这个MerklerTree结构的介绍。对于其精妙之处再一次的感到。所以记录之。

默克尔树简介

默克尔树,又名是哈希树。关于其较详细的简介可以看看之前的文章

什么是默克尔树

现在简单讲是一个哈希构成的二叉树了。

其主要的特性有

  • 最下面的叶子节点时包含的时存储数据和其哈希值
  • 非叶子节点的值是他的两个孩子节点的内容的Hash

在逻辑上讲,他们的父节点就是子节点的摘要。任何的数据改变将会最终的传递到根节点上。也正是这种性质成就了精巧的区块链体系。


默克尔树的作用

大量数据比较

由于默克尔树的所有的存储数据都是存在于其叶子节点上,所有的非叶子节点是孩子节点的哈希。所以我们进行大文件比较时候。我们从根节点依次递归。每次找到当前的高度的存在hash差异节点。并且进入下一个高度。周而复始便可以找到我们存在差异的叶子节点。

所以根据这样的方法可以很快的找到差异数据块。如果只是进行文件的本身的对比,那么只需要对比根哈希即可。

快速定位修改

其实和上面的对比,这个差不多。我们的文件发生了根哈希改变,那么我们根据深度依次递归,找到了我们的最终变化的叶子节点就好了


零知识证明 (zero-knowledge proof)

这里是一个比较重要的点,所以把他放在最后。这个技术已经被很多的加密货币所采用比如较为有名的ZCash(零币)。在零币体系中就是使用了merkleTree的零知识证明的这一应用特性,实现了其招牌的匿名性。

“零知识证明”-zero-knowledge proof,是由S.Goldwasser、S.Micali及C.Rackoff在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下,使验证者相信某个论断是正确的。

这个是不是听着比较玄乎?不告诉你这个内容,又使你相信这个是真的。怎么做到呢?我们从下图入手。

MKT

这个图所绘制的是一个十分简单的实现的默克尔树。

如果我要向其他人证明我是数据A的拥有者,却不可向其他人公布任何关于A的信息,那么要怎么做呢?

证明如下:我们可以公布Habcd,Hcd,Hb的值。我作为拥有者只需要提高我的数据的Hash即可。作为验证者只需要进行验证

Habcd == H(H(a,b),Hcd);

这样的一个等式即可,如果返回是True ,那么可以说明,你就是这个数据的 拥有者了,整个的过程是不需要涉及到数据A的数据信息的。


我们进一步把这个证明贴近我们的生活中去,举个简单的例子:

A要向B证明自己拥有某个房间的钥匙,假设该房间只能用钥匙打开锁,而其他任何方法都打不开。这时有2个方法:

  1. A把钥匙出示给B,B用这把钥匙打开该房间的锁,从而证明A拥有该房间的正确的钥匙。

  2. B确定该房间内有某一物体,A用自己拥有的钥匙打开该房间的门,然后把物体拿出来出示给B,从而证明自己确实拥有该房间的钥匙 。

后面这个方法属于零知识证明。好处在于在整个证明的过程中,B始终不能看到钥匙的样子,从而避免了钥匙的泄露。

详细的ZCash的匿名转账的实现原理

后面的话

此文其实只是对以区块链技术的加密体系的初探。对新的知识做了粗浅的了解,不看也罢

留下点什么吧