区块链百科 | 如何理解默克尔树?

能链科技 发布在 海盗号 42664

区块链词条的必知项中,默克尔树当属其中之一。

作为一种重要的数据结构,默克尔树允许区块的数据被零散地传送,而整个区块链数据是完全串联在一起,并且基本不可能中途修改。那么这些默克尔树究竟是如何工作的,他们现在和将来会提供什么样的价值?

 

一、默克尔树概念

 

我们知道 “树”是计算机领域的一个专有术语,特指一种具有分支的数据结构。

与现实中的树不一样的是,默克尔树(Merkle Tree)就像是一棵倒置的“树”,由一个根节点、一组中间节点和一组叶节点构成,但“根”在上部,“叶子”在下部。

默克尔树最早由美国密码学家Ralph C. Merkle在1980年提出,并以其名字命名,是一种高效和安全的组织数据的方法,可被用来快速查询验证特定交易是否存在

下面这张图就是一个典型的默克尔树:(图片来源于网络)

L1-L4最底层:存储着原始的交易数据,也即叶节点包含的数据(value)

Hash L1- HashL4层:即叶节点,是将原始数据进行哈希运算后得到对应的哈希值

Hash0与Hash1层:即中间节点,它们分别是叶节点0-0、0-1和叶节点1-0、1-1的哈希值

Top Hash层:即默克尔树根,是通过对中间节点的数据进行哈希,得到的根节点。

这是默克尔树的运行原理,并且由于每个节点上的内容都是哈希值,所以也叫“哈希树”。

 

二、默克尔树的特点

 

从默克尔树的结构可以看出,任意一个原始的交易数据被修改,叶子节点哈希值就会变更,最终根节点的哈希值就会改变。正是这种逐层记录哈希值的特点,让默克尔树有了一些独特的性质:

首先,默克尔树常见的结构是二叉树,但它也可以是多叉树,具有树结构的所有特点。

其次,默克尔树是从下往上逐层计算的,就是说叶子节点value是数据集合的单元数据或者单元数据Hash;每个中间节点是根据相邻的两个叶子节点组合计算得出的,而根节点是根据两个中间节点组合计算得出的,所以叶子节点是基础。

最后,默克尔树根节点的哈希值实际上代表了对底层所有数据的“数字摘要”。因此在判断两棵默克尔树所指向数据是否完全相同时,我们不需要比较每个叶子节点,而只需比较根节点所保存的哈希。这意味着仅通过保存根节点的哈希值就能标示区块(无需储存区块链中所有的数据),从而维护数据的不可篡改。

 

三、默克尔树的应用价值

 

默克尔树的概念看似简单,应用场景却非常广泛。

比较典型的就是P2P下载。例如我们以前从网站下载一些种子视频时,容易遇到以下问题:只有一个源地址,大家都相互挤占资源,网络下载速度慢;源地址失效之后,所有资源不可得;文件较大下载失败后,需要全部重新下载。但是有了Merkle Tree之后,我们可以同时从多个节点下载数据块,只需要从可以信任的地址获取哈希值进行校验即可,这不仅减少了数据源的网络压力,同时也方便了用户处理数据。

此外,默克尔树还可以被用来快速校验大量的数据。当两个默克尔树根相同时,则意味着所代表的数据必然相同,因此可用来实现零知识证明,这里我们约下期专题介绍。

可以想象,将默克尔树的思想在区块链中应用,使各类数据在生成和流转时,环环相扣且可追溯,实现海量分布式数据的不可篡改、透明与可信

本文链接:https://www.8btc.com/media/606106
转载请注明文章出处

评论
登录 账号发表你的看法,还没有账号?立即免费 注册