MerkleTreeMerkleTree，通常也被称作Hash Tree，顾名思义，就是存储hash值的一棵树。Merkle树的叶子是数据块(例如，文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。
下面是一幅表示MerkleTree结构的图：
![]()
MerkleTree结构.png那么MerkleTree对我们构造公链有什么用呢？
我们知道完整的比特币数据库已达到一百多Gb的存储，对于每一个节点必须保存一个区块链的完整副本。这对于大多数使用比特币的人显然不合适，于是中本聪提出了简单支付验证SPV(Simplified Payment Verification).
简单地说，SPV是一个轻量级的比特币节点，它并不需要下载区块链的所有数据内容。为了实现SPV，就需要有一个方式来检查某区块是否包含某一笔交易，这就是MerkleTree能帮我们解决的问题。
一个区块的结构里只有一个哈希值，但是这个哈希值包含了所有交易的哈希值。我们将区块内所有交易哈希的值两两进行哈希得到一个新的哈希值，然后再把得到的新的哈希值两两哈希...不断进行这个过程直到最后只存在一个哈希值。这样的结构是不是很像一颗二叉树，我们将这样的二叉树就叫做MerkleTree。
比特币的MerkleTree结构图：
![]()
Bitcoin_MerkleTree.png这样，我们只需要一个根哈希就可以验证一笔交易是否存在于一个区块中了，因为这个根哈希可以遍历到所有交易哈希。相当于一个Merkle 树根哈希和一个 Merkle 路径。
废话少说撸代码[h2]MerkleTree结构[/h2]MerkleTree只包含一个根节点，每一个默克尔树节点包含数据和左右指针。每个节点都可以连接到下个节点，并依次连接到更远的节点直到叶子节点。- //默克尔树type MerkleTree struct { //根节点 RootNode *MerkleNode}//默克尔树节点type MerkleNode struct { //做节点 Left *MerkleNode //右节点 Right *MerkleNode //节点数据 Data []byte}
- //新建节点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}
叶子节点两两哈希形成新的节点，新节点继续两两哈希直到最后只有一个节点。- // 1 2 3 --> 1 2 3 3//新建默克尔树func NewMerkleTree(datas [][]byte) *MerkleTree { var nodes []*MerkleNode //如果是奇数，添加最后一个交易哈希拼凑为偶数个交易 if len(datas) % 2 != 0 { datas = append(datas, datas[len(datas)-1]) } //将每一个交易哈希构造为默克尔树节点 for _, data := range datas { node := NewMerkleNode(nil, nil, data) nodes = append(nodes, node) } //将所有节点两两组合生成新节点，直到最后只有一个更节点 for i := 0; i < len(datas)/2; i++ { var newLevel []*MerkleNode for j := 0; j < len(nodes); j += 2 { node := NewMerkleNode(nodes[j], nodes[j+1], nil) newLevel = append(newLevel, node) } nodes = newLevel } //取根节点返回 mTree := MerkleTree{nodes[0]} return &mTree}
- // 需要将Txs转换成[]bytefunc (block *Block) HashTransactions() []byte { //引入MerkleTree前的交易哈希 //var txHashes [][]byte //var txHash [32]byte // //for _, tx := range block.Txs { // // txHashes = append(txHashes, tx.TxHAsh) //} //txHash = sha256.Sum256(bytes.Join(txHashes, []byte{})) // //return txHash[:] //默克尔树根节点表示交易哈希 var transactions [][]byte for _, tx := range block.Txs { transactions = append(transactions, tx.Serialize()) } mTree := NewMerkleTree(transactions) return mTree.RootNode.Data}
源代码在这,喜欢的朋友记得给个小star，或者fork.也欢迎大家一起探讨区块链相关知识，一起进步！
.
.
.
.[h2]互联网颠覆世界，区块链颠覆互联网![/h2] ---------------------------------------------20180708 16:55
|
|
转播
