Skip to content

Latest commit

 

History

History
32 lines (17 loc) · 4.88 KB

File metadata and controls

32 lines (17 loc) · 4.88 KB

轻节点与默克尔树

轻节点

轻节点是与全节点相对的一个概念,在比特币或者以太坊中,保存全量最新数据的节点被称为全节点,这样的节点可以独立自主的验证所有的交易,但是我们知道无论是比特币亦或是以太坊,全量的数据都是非常庞大的,并且还在飞速的增长中。全节点虽然可以提供全部的功能,但是对于大多数使用者而言只用到了很少的功能,比如发送交易,验证交易。为了使用少量的功能花费昂贵的计算机硬件去保存全量数据显示不是很划算的,同时也限制了比特币和以太坊的应用场景。

为了解决上面说的问题,提出了一个轻节点的概念,显然与全节点相对,轻节点只保存少量数据就可以满足基本的使用需要。

假设有这样一种场景需要用到比特币支付(发送交易),支付完成以后我需要向对方证明这笔交易已经写到区块中了,比较容易想到的办法就是拿到打包交易的对应区块,然后对比区块中的所有交易来确认是否已经被打包其中。

在比特币或者以太坊的场景下,一个区块大概有两三千笔交易,一个交易又包含若干字段,如果逐一比较交易不仅速度慢,而且不安全,因为拿单一的区块是无法知道拿到的块的真伪。这个时候就需要一种方法来解决这些问题。

默克尔树

默克尔树(Merkle Tree)是区块链系统中非常重要的一种数据结构,用于快速判断和校验区块数据的存在性和完整性。默克尔树属于二叉树的一种,由一个根节点,一组中间节点和一组叶子节点组成。

默克尔树有两个很重要的特点,快速比较大量数据是否一致和快速定位大量数据中哪些数据发生了变化。比特币和以太坊基于默克尔树的这两个特点为其轻节点提供默克尔证明。

默克尔树首先计算叶子节点的hash值,然后将相邻两个节点的哈希进行合并,合并完成后计算这个字符串的哈希值,直到根节点为止,其根节点存储的哈希值被称为默克尔根(Merkle Root) 如果是单个节点,可以复制单节点的哈希,然后合并哈希再重复上面的过程。

默克尔树的特点非常的明显,可以高效安全的验证数据结构的内容,当树的内容发生改变时,计算得到的根哈希就会不同,比如p2p网络分块下载文件的时候,可以用来快速校验下载到的数据是否完整,是否遭到破坏,先从可信节点获得一个很小的根哈希,接着通过p2p网络分块接收数据,当数据传输完成后计算根哈希,比较与之前得到的根哈希是否一致,如果一致则表示数据传输没有出错。

除此之外,默克尔树还可支持简化支付验证(Simplified Payment Verification, SPV)协议,即不需要保存全量的区块数据,只保存最长链的区块头即可对交易数据进行校验。这种校验方式也被称为默克尔证明。SPV技术强调的是验证交易是否被支付,而非交易的合法性,简单来说验证的是交易是否已经存在于区块中,并且是否后续有足够多的区块保证了这笔交易只有很低很低的几率被回滚,而非验证交易中的数据是否合法,交易是否有效。

如果我们知道了根哈希,也就是根节点包含的值,需要证明包含data4数据的节点是否在这个集合中,仅需要提供绿色节点包含的值就可以。可以计算出data4的哈希值,然后依次与绿色节点包含的哈希值两两计算哈希,最终就可以得到根哈希,根哈希一致则证明data4在这个区块中。

对于N个交易组成的区块中,获得默克尔证明的路径的算法复杂度仅仅为log2N。意味着如果一个区块如果包含16笔交易那么获得的默克尔证明的路径只有4。当区块打包的交易增长到了4096笔的时候默克尔证明的路径仅仅增长到了12,可见默克尔证明路径的增长是远远要小于区块交易数据增长的。

当拥有了默克尔树和默克尔证明以后,轻节点只用包含区块头,也就是有交易树的根哈希值,当A需要向轻节点证明一笔交易已经打包到指定区块时,只需要提供这笔交易和对应路径上的哈希值即可,这样轻节点就可以在不保存区块体的情况下证明了这笔交易已经上链不可更改了。截止2020年2月底,比特币大约有60万个区块产生,区块头80Byte来计算,保存全量区块头信息也仅仅需要60M左右的存储空间,并且因为保存了全量的区块头,安全性也得到了保证。