剖析区块链-五:核心技术之merkle树

在区块链中, merkle树充当着一个代表性的角色,一个区块中的所有交易信息都被它归纳总结,大大提高区块链的效率。下面先讲一下区块链(以比特币系统为例)中为什么要用merkle树这个方法,并且引申出比特币轻钱包的实现基础--简化支付验证(SPV)。不会像单纯讲技术那样枯燥的,相信用过btc钱包的都会对本文感兴趣。

大家都知道,比特币网络中所有产生的交易都要打包进区块中,一般情况下,一个区块中包含几百上千笔交易是很常见的。由于比特币的去中心化特性,网络中的每个节点必须是独立,自给自足的,也就是每个节点必须存储一个区块链的完整副本。在2014年4月,比特币网络中一个全节点要存储、处理所有区块的数据,需要占用15GB的空间,并且随着越来越多的人使用比特币,每个月以超过1GB的速度在增长。到如今,完整的下载比特币所有的区块数据,也就是运行一个全节点,需要200GB以上的空间...

这样的规则随着日益剧增的全节点所需空间,越来越难以让人遵守,难道让每个人都去运行一个全节点吗?还有节点就是区块链网络中的完全参与者,他们要遵守节点必须验证交易和区块,再加上想要与其他节点交互、下载新区块,对网络流量也是有一定要求的,节点要做的会越来越麻烦,并且效率低下。

于是中本聪在比特币白皮书中提出了对这个问题的解决方案:简化支付验证(Simplified Payment Verification, SPV)。SPV 是一个比特币轻节点,也就是我们大部分人在电脑安装的轻量级的比特币钱包,理论上来说,要验证一笔交易,钱包需要遍历所有的区块找到和该笔交易相关的所有交易进行逐个验证才是可靠的。但有了SPV就不用这么麻烦了,它不需要同步下载整个区块链的数据即不用运行全节点就可以验证支付,也不需要验证区块和交易,用户只需要保存所有的区块头就可以了。要知道,区块头包含着区块的必要属性,仅80个字节大小,而区块体当中包含着成百上千笔交易,每笔交易一般要400多个字节大小。

这里需要注意的是,SPV强调的是验证支付,不是验证交易。这两个概念是不同的。验证支付,比较简单,只需要判断用于支付的那笔交易是否被验证过,以及得到网络多少次确认(即有多少个区块叠加)。而交易验证则复杂的多,需要验证账户余额是否足够支出、是否存在双重支付、交易脚本是否通过等问题,一般这个操作是由全节点的矿工来完成。

为了实现SPV,需要有一种方式来检查一个区块是否包含了某笔交易,而不用去下载整个区块。这就是merkle树所要完成的事。先来看看什么是merkle树吧。

1.概念

Merkle tree(默克尔树),常叫它merkle树,是一种哈希二叉树,在计算机科学中,二叉树是每个节点最多有两个子树的树结构,每个节点代表一条结构化数据。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现数据快速查询。

2.结构

由一个根节点、一组中间节点和一组叶节点组成。叶节点包含存储数据或其哈希值,中间节点是它的两个孩子节点内容的哈希值,根节点也是由它的两个子节点内容的哈希值组成。所以Merkle树也称哈希树。

3.特点

技术特点就不多讲了,主要特点就是:底层(叶子节点)数据的任何变动,都会逐级向上传递到其父节点,一直到Merkle树的根节点使得根节点的哈希值发生变化。

4.总结原理

区块链中每个区块都会有一个 Merkle 树,它从叶子节点(树的底部)开始,一个叶子节点就是一个交易哈希。叶子节点的数量必须是双数,但是并非每个块都包含了双数的交易。如果一个块里面的交易数为单数,那么就将最后一个叶子节点(也就是 Merkle 树的最后一个交易,不是区块的最后一笔交易)复制一份凑成双数。

从下往上,两两成对,连接两个节点哈希,将组合哈希作为新的哈希。新的哈希就成为新的树节点。重复该过程,直到仅有一个节点,也就是树根。根哈希然后就会当做是整个块交易的唯一标示,将它保存到区块头,然后用于工作量证明。

以上就是对于merkle树的介绍,感兴趣的话,后面不妨跟着阿深一起一层层剥开区块链,欢迎大家转发评论。如果对你有帮助不胜荣幸。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181018A0H94700?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券