我的区块链技术学习笔记(十八):Merkle树介绍 [复制链接]

1222
 
8btm.com-新币圈 8btm.com-新币圈 8btm.com-新币圈attachments-2018-01-PWwUmS9G5a701a571d9bc. 8btm.com-新币圈 8btm.com-新币圈 8btm.com-新币圈作者: Ivan Kuznetsov  吴寿鹤等
8btm.com-新币圈 8btm.com-新币圈著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
8btm.com-新币圈 8btm.com-新币圈

8btm.com-新币圈 8btm.com-新币圈在这篇文章中,我还想要再讨论一个优化机制。
8btm.com-新币圈 8btm.com-新币圈
8btm.com-新币圈 8btm.com-新币圈上如上面所提到的,完整的比特币数据库(也就是区块链)需要超过 140 Gb的磁盘空间。因为比特币的去中心化特性,网络中的每个节点必须是独立,自给自足的,也就是每个节点必须存储一个区块链的完整副本。随着越来越多的人使用比特币,这条规则变得越来越难以遵守:因为不太可能每个人都去运行一个全节点。并且,由于节点是网络中的完全参与者,它们负有相关责任:节点必须验证交易和区块。
8btm.com-新币圈 8btm.com-新币圈另外,要想与其他节点交互和下载新块,也有一定的网络流量需求。在中本聪的 比特币原始论文 中,对这个问题也有一个解决方案:简易支付验证(Simplified Payment Verification, SPV)。SPV 是一个比特币轻节点,它不需要下载整个区块链,也不需要验证区块和交易。相反,它会在区块链查找交易(为了验证支付),并且需要连接到一个全节点来检索必要的数据。这个机制允许在仅运行一个全节点的情况下有多个轻钱包。
8btm.com-新币圈 8btm.com-新币圈
8btm.com-新币圈 8btm.com-新币圈为了实现 SPV,需要有一个方式来检查是否一个区块包含了某笔交易,而无须下载整个区块。
8btm.com-新币圈 8btm.com-新币圈这就是 Merkle 树所要完成的事情。比特币用 Merkle树来获取交易哈希,哈希被保存在区块头中,并会用于工作量证明系统。到目前为止,我们只是将一个块里面的每笔交易哈希连接了起来,将在上面应用了SHA-256 算法。虽然这是一个用于获取区块交易唯一表示的一个不错的途径,但是它没有利用到 Merkle 树。
8btm.com-新币圈 8btm.com-新币圈来看一下 Merkle 树:
8btm.com-新币圈 8btm.com-新币圈 8btm.com-新币圈 8btm.com-新币圈 8btm.com-新币圈1240 8btm.com-新币圈 8btm.com-新币圈 8btm.com-新币圈
8btm.com-新币圈 8btm.com-新币圈每个块都会有一个 Merkle 树,它从叶子节点(树的底部)开始,一个叶子节点就是一个交易哈希(比特币使用双 SHA256哈希)。叶子节点的数量必须是双数,但是并非每个块都包含了双数的交易。因为,如果一个块里面的交易数为单数,那么就将最后一个叶子节点(也就是Merkle 树的最后一个交易,不是区块的最后一笔交易)复制一份凑成双数。
8btm.com-新币圈 8btm.com-新币圈从下往上,两两成对,连接两个节点哈希,将组合哈希作为新的哈希。新的哈希就成为新的树节点。重复该过程,直到仅有一个节点,也就是树根。根哈希然后就会当做是整个块交易的唯一标示,将它保存到区块头,然后用于工作量证明。
8btm.com-新币圈 8btm.com-新币圈Merkle 树的好处就是一个节点可以在不下载整个块的情况下,验证是否包含某笔交易。并且这些只需要一个交易哈希,一个 Merkle 树根哈希和一个 Merkle 路径。
8btm.com-新币圈 8btm.com-新币圈最后,来写代码:
8btm.com-新币圈 8btm.com-新币圈type MerkleTree struct { RootNode *MerkleNode}type MerkleNode struct { Left *MerkleNode Right *MerkleNode Data []byte}先从结构体开始。每个 MerkleNode 包含数据和指向左右分支的指针。MerkleTree 实际上就是连接到下个节点的根节点,然后依次连接到更远的节点,等等。
8btm.com-新币圈 8btm.com-新币圈让我们首先来创建一个新的节点:
8btm.com-新币圈 8btm.com-新币圈func NewMerkleNode(left, right *MerkleNode, data []byte) *MerkleNode { mNode := MerkleNode{} if left == nil && right == nil { hash := sha256.Sum256(data) mNode.Data = hash[:] } else { prevHashes := append(left.Data, right.Data...) hash := sha256.Sum256(prevHashes) mNode.Data = hash[:] } mNode.Left = left mNode.Right = right return &mNode}每个节点包含一些数据。当节点在叶子节点,数据从外界传入(在这里,也就是一个序列化后的交易)。当一个节点被关联到其他节点,它会将其他节点的数据取过来,连接后再哈希。
8btm.com-新币圈 8btm.com-新币圈func NewMerkleTree(data [][]byte) *MerkleTree { var nodes []MerkleNode if len(data)%2 != 0 { data = append(data, data[len(data)-1]) } for _, datum := range data { node := NewMerkleNode(nil, nil, datum) nodes = append(nodes, *node) } for i := 0; i <span style="font-size:inherit;color:rgb(199,107,41);">

本版积分规则

发表主题 回复
mailtopia,把去中心化做到极致!

(c) 2015-2018 8BTM Inc. M链、₥币 All Rights Reserved 智能硬件IoT产品:福州智垒电子科技有限公司

网站备案证书号: 闽ICP备18010811号  Ƀ猫商城 IoT&BlockChain:微物联(福州)网络科技有限公司 SiteMap