Merkle Tree，通常也被称作Hash Tree，顾名思义，就是存储hash值的一棵树。Merkle树是一种数据结构，Merkle树的叶子是数据块(例如，文件或者文件的集合)的hash值。非叶节点是其对应子节点串联字符串的hash。
image
第一笔hash：
16f0eb42cb4d9c2374b2cb1de4008162c06fdd8f1c18357f0c849eb423672f5f
大小端转换为：
5f2f6723b49e840c7f35181c8fdd6fc0628100e41dcbb274239c4dcb42ebf016
第二笔hash：
cce2f95fc282b3f2bc956f61d6924f73d658a1fdbc71027dd40b06c15822e061
大小端转换为：
61e02258c1060bd47d0271bcfda158d6734f92d6616f95bcf2b382c25ff9e2cc
将两个拼接在一起：
5f2f6723b49e840c7f35181c8fdd6fc0628100e41dcbb274239c4dcb42ebf01661e02258c1060bd47d0271bcfda158d6734f92d6616f95bcf2b382c25ff9e2cc
将上面拼接的字符串进行两次hash如下：
第一次hash结果：
9b2ec096d49fee8b310752082d63d8fe198386ae2172d90533d9186bb28df63d
将上面计算出的hash值再次进行hash：
525894ddd0891b36c5ff8658e2a978d615b35ce6dedb5cb83f2420dbcd40a0c7
大小端转换即为结果：
c7a040cddb20243fb85cdbdee65cb315d678a9e25886ffc5361b89d0dd945852
package main
import (
"encoding/hex"
"crypto/sha256"
"fmt"
)
func ReverseBytes2(data []byte){
for i,j :=0,len(data) - 1;i<j;i,j = i+1,j - 1{
data[i],data[j] = data[j],data[i]
}
}
func main(){
//字符串hash转换为字节
hash1,_:= hex.DecodeString("16f0eb42cb4d9c2374b2cb1de4008162c06fdd8f1c18357f0c849eb423672f5f")
hash2,_:= hex.DecodeString("cce2f95fc282b3f2bc956f61d6924f73d658a1fdbc71027dd40b06c15822e061")
//大小端的转换
ReverseBytes2(hash1)
ReverseBytes2(hash2)
//拼接在一起
rawdata:=append(hash1,hash2...)
//double hash256
firsthash:=sha256.Sum256(rawdata)
secondhash:= sha256.Sum256(firsthash[:])
merkroot := secondhash[:]
//反转，与浏览器当中的数据对比
ReverseBytes2(merkroot)
fmt.Printf("%x",merkroot)
}
merkle树实战
func min(a int,b int) int{
if(a>b){
return b
}
return a
}
//默克尔树节点
type MerkleTree struct{
RootNode *MerkleNode
}
//默克尔根节点
type MerkleNode struct{
Left *MerkleNode
Right *MerkleNode
Data []byte
}
//生成默克尔树中的节点，如果是叶子节点，则Left，right为nil ，如果为非叶子节点，根据Left，right生成当前节点的hash
func NewMerkleNode(left,right *MerkleNode,data []byte) *MerkleNode{
mnode := MerkleNode{}
if left ==nil && right==nil{
mnode.Data = data
}else{
prevhashes := append(left.Data,right.Data...)
firsthash:= sha256.Sum256(prevhashes)
hash:=sha256.Sum256(firsthash[:])
mnode.Data = hash[:]
}
mnode.Left = left
mnode.Right = right
return &mnode
}
//构建默克尔树
func NewMerkleTree(data [][]byte) *MerkleTree{
var nodes []MerkleNode
//构建叶子节点。
for _,datum := range data{
node:= NewMerkleNode(nil,nil,datum)
nodes = append(nodes,*node)
}
//j代表的是某一层的第一个元素
j:=0
//第一层循环代表 nSize代表某一层的个数，每循环一次减半
for nSize :=len(data);nSize >1;nSize = (nSize+1)/2{
//第二条循环i+=2代表两两拼接。 i2是为了当个数是基数的时候，拷贝最后的元素。
for i:=0 ; i<nSize ;i+=2{
i2 := min(i+1,nSize-1)
node := NewMerkleNode(&nodes[j+i],&nodes[j+i2],nil)
nodes = append(nodes,*node)
}
//j代表的是某一层的第一个元素
j+=nSize
}
mTree := MerkleTree{&(nodes[len(nodes)-1])}
return &mTree
}
全部代码
package main
import (
"crypto/sha256"
"encoding/hex"
"fmt"
)
func min(a int,b int) int{
if(a>b){
return b
}
return a
}
//默克尔树节点
type MerkleTree struct{
RootNode *MerkleNode
}
//默克尔根节点
type MerkleNode struct{
Left *MerkleNode
Right *MerkleNode
Data []byte
}
//生成默克尔树中的节点，如果是叶子节点，则Left，right为nil ，如果为非叶子节点，根据Left，right生成当前节点的hash
func NewMerkleNode(left,right *MerkleNode,data []byte) *MerkleNode{
mnode := MerkleNode{}
if left ==nil && right==nil{
mnode.Data = data
}else{
prevhashes := append(left.Data,right.Data...)
firsthash:= sha256.Sum256(prevhashes)
hash:=sha256.Sum256(firsthash[:])
mnode.Data = hash[:]
}
mnode.Left = left
mnode.Right = right
return &mnode
}
//构建默克尔树
func NewMerkleTree(data [][]byte) *MerkleTree{
var nodes []MerkleNode
//构建叶子节点。
for _,datum := range data{
node:= NewMerkleNode(nil,nil,datum)
nodes = append(nodes,*node)
}
//j代表的是某一层的第一个元素
j:=0
//第一层循环代表 nSize代表某一层的个数，每循环一次减半
for nSize :=len(data);nSize >1;nSize = (nSize+1)/2{
//第二条循环i+=2代表两两拼接。 i2是为了当个数是基数的时候，拷贝最后的元素。
for i:=0 ; i<nSize ;i+=2{
i2 := min(i+1,nSize-1)
node := NewMerkleNode(&nodes[j+i],&nodes[j+i2],nil)
nodes = append(nodes,*node)
}
//j代表的是某一层的第一个元素
j+=nSize
}
mTree := MerkleTree{&(nodes[len(nodes)-1])}
return &mTree
}
func ReverseBytes3(data []byte){
for i,j :=0,len(data) - 1;i<j;i,j = i+1,j - 1{
data[i],data[j] = data[j],data[i]
}
}
func main(){
//测试网站下的5个hash是否能够生成merkleRoot
//https://www.blockchain.com/btc/block/00000000000090ff2791fe41d80509af6ffbd6c5b10294e29cdf1b603acab92c
//传递hash
data1,_:=hex.DecodeString("6b6a4236fb06fead0f1bd7fc4f4de123796eb51675fb55dc18c33fe12e33169d")
data2,_:=hex.DecodeString("2af6b6f6bc6e613049637e32b1809dd767c72f912fef2b978992c6408483d77e")
data3,_:=hex.DecodeString("6d76d15213c11fcbf4cc7e880f34c35dae43f8081ef30c6901f513ce41374583")
data4,_:=hex.DecodeString("08c3b50053b010542dca85594af182f8fcf2f0d2bfe8a806e9494e4792222ad2")
data5,_:=hex.DecodeString("612d035670b7b9dad50f987dfa000a5324ecb3e08745cfefa10a4cefc5544553")
//大小段转换
ReverseBytes3(data1)
ReverseBytes3(data2)
ReverseBytes3(data3)
ReverseBytes3(data4)
ReverseBytes3(data5)
hehe := [][]byte{
data1,
data2,
data3,
data4,
data5,
}
//生成默克尔树
merleroot:= NewMerkleTree(hehe)
//反转
ReverseBytes3(merleroot.RootNode.Data)
fmt.Printf("%x",merleroot.RootNode.Data)
}
