科普 | 默克尔树的基础数据结构

时间:2021-07-05 20:01来源:www.jddiban.com作者:未知点击:

导读:
扫描关注公众号

除去区块链和BT下载,默克尔树还能在任何需要有效测试不同性的系统中被应用:

证书颁发机构(CAs)用默克尔树作为证书透明性的一种办法。在这里,公钥私钥对被视为默克尔树的叶子。这是CAs用来预防某个CA可能耍无赖并试图在某个范围的所有者不知晓证书的状况下对该范围的证书进行认证的一种机制。 高度可伸缩的数据库,如ApacheCassandra和DynamoDB,二手网络上复制数据库的问题。这个过程被叫做“反熵”,ApacheCassandra博客和AmazonDynamoDB论文对其进行了较为深入的描述。 RSA的数字签名替代品,在这样的情况下,默克尔树的根充当公钥,单个节点用作一次性签名。近期,大家做了更多的工作来推进这种技术,由于理论上它可以抵抗量子计算攻击(和RSA不同,默克尔树为当今大部分公钥密码术提供了支持)。

输出某些数据的验证路径和重新创建通向默克尔树根的分支一样容易。在数字签名策略中用默克尔树时,验证整个默克尔树及其各个叶子节点自己的数据就非常重要,并且这事实上是可以在O(logn)时间内完成。有一些更高级的算法是可以完成这一输出过程的。

下图是完整版本的代码,作者将会在这里讲解创建和验证默克尔树的办法。注意build_tree和_audit办法都是来自较大类的实例办法。

默克尔树构建完成后,就可以在O(logn)时间内用根哈希对叶子进行验证,验证工作是通过重新创建包含从根到被验证的数据段进行的。在上面的例子中,假如想要验证c,那样就需要得到H和H+H)。数据c哈希后得到H,再将H与H进行哈希运算,然后将H与H在进行哈希运算,得到一个最后的哈希值,假如这个哈希值与根哈希相同,则说明c确实是默克尔树中数据的一部分。

a、b、c、d是一些数据元素,H是哈希函数。假如你不是非常知道哈希函数,可以把它理解为数据块的“数据指纹”,Hash是一个把任意长度的数据映射成固定长度数据的函数,而依据Hash值反推原始输入数据的特点是几乎不可能的。每一个节点都是通过哈希运算父节点得到的,默克尔树的容易见到结构是二叉树,但也有非二叉树结构的,譬如ETH平上默克尔树。本文只讨论这种最容易见到的二叉树结构。

默克尔树的应用确实不少,在任何特定范围的默克尔树应用都是需要长篇大论来论述的,在这里大家只做容易的介绍。

上面的办法在单节点状况下会失败,由于不满足任何条件,所以有一个小技巧来处置完整性。

上图是本文要讲解的验证过程。公开验证办法会检查一些先决条件,这就是为何大多数逻辑放在这个私人版本中是什么原因。

默克尔树讲解

在平台的BTC和数字货币技术课程中,作者学习了怎么用基于哈希的数据结构来验证点对点互联网系统中数据完整性的入门知识。该课程中提到的核心数据结构之一是默克尔树,它存在于BTC区块链中,以一种很有效地节省空间和时间的方法,来帮验证买卖的存在(本文后面会详细介绍!)。作者深入研究了默克尔树,意识到这个数据结构事实上是多么丰富的,所以决定写一篇默克尔树学习笔记。

默克尔树构建完成后,看着是如此:

本文主要介绍了默克尔树的基础数据结构,与默克尔树有关的应用延伸的起点。

和H,假如没缩写的话,根哈希也可以为H+H)+H+H)))

自下而上通过哈希运算相同高度的节点,直至生成默克尔树根节点。在生成默克尔树的时候,假如存在单个叶子节点没办法匹配成对,就需要特殊处置这个状况,此外,树的架构很简单。

默克尔树的实行办法

构建树的办法是将叶子添加到堆栈中,并检查堆栈中的前两个节点是不是具备相同的高度。当高度相同时,节点有一个“子值”(两个节点哈希值相连后的第三哈希值),当高度不同时,一个新节点会追加到堆栈中。当最后两个节点高度不同时,需要处置这种边缘状况。

默克尔树在区块链中应用,近年来引起了大家的广泛关注。在很多点对点互联网系统中(不止是区块链),个人需要可以从不受信赖的一方获得数据,并证明他们发送给他们的内容是他们想要的真实内容。BT文件(种子文件)就是一个例子:当你下载一个BT文件时,你会收到其他人在网上“播种”的BT文件,但你如何能确定这部分文件真的,是你要下载的内容,而不是垃圾或恶意软件呢?默克尔树可以对从他们接收到的数据进行身份验证,以解决这个信赖问题。

类似的问题也适用于像BTC和ETH如此的数字货币:假如有人声称另一个同行在买卖中向他们支付了成本,那样互联网上的一个节点怎么样验证买卖是不是真的发生了呢?一种办法是,节点可以存储过去发生过的完整买卖历史记录,但,就节点的时间和空间本钱而言,这是不现实的。默克尔树提供了一种解决方法,可以为互联网上的节点节省时间和空间。通过每一个区块中的买卖数据创建默克尔树,可以在O(logn)时间内审计买卖。除此之外,它为一些BTC推广客户端提供了新的解决方法,可以节省空间,只存储默克尔树根,无需存储历史每一笔买卖,这创造了巨大的价值!

本文主要介绍了的基础数据结构,与默克尔树有关的应用延伸的起点。

默克尔树简介

在BT下载等状况下,是由另一方提供数据c,H和H+H)的,假如你担忧这种办法的安全性,请记住在一个哈希函数上不可能找到e值使得H=H。这意味着只须根哈希是正确的,别的人非常难作假他们提供的数据。

默克尔树的应用

相关文章
推荐文章

热门标签

区块链技术_区块链入门教程_区块链技术投资_库链网

Copyright © 2002-2021 库链网 (http://zhangjiakouyouxuanjiancai.com) 网站地图 TAG标签 备案号:

声明: 本站文章均来自互联网,不代表本站观点 如有异议 请与本站联系 本站为非赢利性网站