区块链研习 | 区块链中的默克尔树

6月前 295

回忆一下本系列第一篇文章中,我们讲的区块链描述:


区块链是实现无中心分布式总账的一种技术。除了采用块、链结构的典型区块链以外,还有其他的方式实现分布式总账这个需求。总账技术的基本单元是‘交易’,整个账本是由一条条的交易构成。‘块’类似于账本中的页,每页都记录了若干条交易,把一页一页的账页按照时间顺序装订起来,就形成了一个完整的账本——‘区块链’。‘块’是交易的容器,‘块’通过密码学算法相连接,形成了按照时间序列的‘链’。这种组织账本的好处是由密码学算法保证了无法篡改链上的单独交易,除非整体性的篡改。”


根据描述,我们可以看出来,“块”是交易的容器。每个交易都要放到容器里面,然后把整个容器用密码学算法进行连接,形成了一个完整的链。

这种数据的组织方式最大的好处就是数据易于保持完整,并且从密码学角度看安全性较高。然而,这个好处是有代价的——数据一直不停的增长。

对于比特币系统来说,这个问题并不大,因为截止目前为止,比特币仍然是每10分钟一个区块,每个区块1MB,即便到了100年后,总的数据量也不会大到单机无法处理。但是对于某些企业级应用的区块链系统来说,情况就完全不一样了。每个区块可能会非常大,生成区块的速度也会非常快。这种情况下,区块链的数据量增长是飞快的。

怎么解决数据量过大的问题呢?

在我们传统的数据系统中,也存在数据不断增长,数据量过大的问题。以传统的交易型系统为例,由于系统中的核心设计理念是保存账户的最终状态,只需要把历史的交易过程数据移到其他专门的存储设备上,主机数据库保存账户的最新状态和最近一段时间的交易记录即可。(因此,我们在网银中查阅历史交易时,通常是有时间限制的。)

但是在区块链系统中,尤其是使用UTXO方式存储交易的区块链系统中,保存的都是交易的过程。如果一个账户一直没有交易,它则不会出现在最新的区块中。

那么按照传统数据库删除历史数据的方式,只要一个区块中有一个交易一直没有后续交易(就是没有人使用这个交易的输出账户),为了维护整个区块链系统的密码学完整性和安全性,这个区块就必须保留,同时这个区块之后的所有区块也必须保留。

怎么解决这个问题?其实有很多种办法能够解决,起初,在中本聪设计比特币系统的时候,已经预留了一个最佳的解决方案:默克尔树(Merkle Tree)算法。

在比特币区块链系统中,区块的结构如下图所示:

34


每个区块中的Hash1就是本区块中所有交易的哈希值。但这个哈希值不是把所有交易连成一个长字符串后计算HASH值,而是使用了默克尔树(Merkle Tree)算法来计算获得这个HASH值,我们称之为Merkle根。

35


默克尔树算法并不是直接计算整个字符串的Hash值,而是每个交易都计算一个Hash值,然后两两连接再次计算Hash,一直到最顶层的Merkle根。

默克尔树(Merkle Tree)算法的最大好处就是,每个交易都可以单独直接删除,只保留这个交易的Hash值即可。这样,对整个区块来说,并没有改变他的密码学安全性和完整性,但是数据量可以大大减小。(Hash值32个字节,而一笔交易一般要400多个字节)。如果一个区块中只有一个交易没有后续交易,那么删除其他所有交易,整个区块的数据量会大大减小。

因此,在UTXO的记账模式中,使用默克尔树结构,通常就无需担心数据量一直增长导致数据过大的问题了。

原文发布时间为:2017-12-13
本文作者:敖萌
本文来源:雷锋网,如需转载请联系原作者。

分布式 算法 容器 HASH 区块链

作者

北丐09
TA的文章

相关文章