持续创作，加速成长！这是我参与「掘金日新计划 · 6 月更文挑战」的第6天，点击查看活动详情

GO语言和默克尔树

默克尔树

默克尔树是一个二叉树，由一组hash后形成的数值节点组成，其叶子节点存放基础数据，从根节点开始每个节点都是由其左右节点联合在一起计算hash得到的。

* 优点*：

1、 任意节点的变化都会导致整棵树的变化

     2、树的任意部分子树都可以作为小型树进行传递和使用

代码实现

分步实现三层默克尔树

1、定义默克尔树的数据结构

```go package main

import ( "crypto/sha256" "fmt" ) //定义默克尔树的节点结构体 type MerkleNode struct { Left *MerkleNode Right *MerkleNode Data []byte } //定义默克尔树结构(树形结构) type MerkleTree struct { RootNode *MerkleNode //只记录一个根节点，任意一个根节点都可以追溯全部节点。 } ```

2、构造节点函数

go //创建节点 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) //将[32]byte转换为byte[] mNode.Data=hash[:] } //赋值 mNode.Left=left mNode.Right=right return &mNode }

3、将节点组建为树

```go func NewMerkleTree(data [][]byte)MerkleTree{ //定义一个结构体类型的切片 var nodes []MerkleNode //确保节点为2的整数倍 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 < len(data)/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 } ```

4、遍历函数

```go func showMerkleTree(root *MerkleNode){ if root ==nil{ return }else{ PrintNode(root) } showMerkleTree(root.Left) showMerkleTree(root.Right) }

func PrintNode(node *MerkleNode){ fmt.Printf("%p\n",node) if node!=nil{ fmt.Printf("left[%p],right[%p],data(%x)\n",node.Left,node.Right,node.Data) }

} ```

5、调用测试

go func main(){ data:=[][]byte{ []byte("node1"), []byte("node2"), []byte("node3"), []byte("node4"), } tree:=NewMerkleTree(data) showMerkleTree(tree.RootNode) }

打印结果

可写检验代码： ```go //检验 func check(node *MerkleNode)bool { if node.Left==nil{ return true } prevHashes:=append(node.Left.Data,node.Right.Data...) hash32:=sha256.Sum256(prevHashes) hash:=hash32[:] return bytes.Compare(hash,node.Data)==0

} 然后再打印函数修改一下就好了 go func PrintNode(node *MerkleNode){ fmt.Printf("node:%p\n",node) if node!=nil{ fmt.Printf("left[%p],right[%p],data(%x)\n",node.Left,node.Right,node.Data) fmt.Printf("检验代码打印check:%t\n",check(node)) }

} ``` 检验结果