Merkle Tree，通常也被稱作Hash Tree，顧名思義，就是存儲(chǔ)hash值的一棵樹。Merkle樹是一種數(shù)據(jù)結(jié)構(gòu)，Merkle樹的葉子是數(shù)據(jù)塊(例如，文件或者文件的集合)的hash值。非葉節(jié)點(diǎn)是其對(duì)應(yīng)子節(jié)點(diǎn)串聯(lián)字符串的hash。
image
對(duì)于網(wǎng)站中的交易： https://www.blockchain.com/btc/block/000000000001741120135274584b2a0da45b39c8cc78322a14f9004ae766a8e0
第一筆hash：
16f0eb42cb4d9c2374b2cb1de4008162c06fdd8f1c18357f0c849eb423672f5f
大小端轉(zhuǎn)換為：
5f2f6723b49e840c7f35181c8fdd6fc0628100e41dcbb274239c4dcb42ebf016
第二筆hash：
cce2f95fc282b3f2bc956f61d6924f73d658a1fdbc71027dd40b06c15822e061
大小端轉(zhuǎn)換為：
61e02258c1060bd47d0271bcfda158d6734f92d6616f95bcf2b382c25ff9e2cc
將兩個(gè)拼接在一起：
5f2f6723b49e840c7f35181c8fdd6fc0628100e41dcbb274239c4dcb42ebf01661e02258c1060bd47d0271bcfda158d6734f92d6616f95bcf2b382c25ff9e2cc
將上面拼接的字符串進(jìn)行兩次hash如下：
第一次hash結(jié)果：
9b2ec096d49fee8b310752082d63d8fe198386ae2172d90533d9186bb28df63d
將上面計(jì)算出的hash值再次進(jìn)行hash：
525894ddd0891b36c5ff8658e2a978d615b35ce6dedb5cb83f2420dbcd40a0c7
大小端轉(zhuǎn)換即為結(jié)果：
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轉(zhuǎn)換為字節(jié)
hash1,_:= hex.DecodeString("16f0eb42cb4d9c2374b2cb1de4008162c06fdd8f1c18357f0c849eb423672f5f")
hash2,_:= hex.DecodeString("cce2f95fc282b3f2bc956f61d6924f73d658a1fdbc71027dd40b06c15822e061")
//大小端的轉(zhuǎn)換
ReverseBytes2(hash1)
ReverseBytes2(hash2)
//拼接在一起
rawdata:=append(hash1,hash2...)
//double hash256
firsthash:=sha256.Sum256(rawdata)
secondhash:= sha256.Sum256(firsthash[:])
merkroot := secondhash[:]
//反轉(zhuǎn)，與瀏覽器當(dāng)中的數(shù)據(jù)對(duì)比
ReverseBytes2(merkroot)
fmt.Printf("%x",merkroot)
}
merkle樹實(shí)戰(zhàn)
func min(a int,b int) int{
if(a>b){
return b
}
return a
}
//默克爾樹節(jié)點(diǎn)
type MerkleTree struct{
RootNode *MerkleNode
}
//默克爾根節(jié)點(diǎn)
type MerkleNode struct{
Left *MerkleNode
Right *MerkleNode
Data []byte
}
//生成默克爾樹中的節(jié)點(diǎn)，如果是葉子節(jié)點(diǎn)，則Left，right為nil ，如果為非葉子節(jié)點(diǎn)，根據(jù)Left，right生成當(dāng)前節(jié)點(diǎn)的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
}
//構(gòu)建默克爾樹
func NewMerkleTree(data [][]byte) *MerkleTree{
var nodes []MerkleNode
//構(gòu)建葉子節(jié)點(diǎn)。
for _,datum := range data{
node:= NewMerkleNode(nil,nil,datum)
nodes = append(nodes,*node)
}
//j代表的是某一層的第一個(gè)元素
j:=0
//第一層循環(huán)代表 nSize代表某一層的個(gè)數(shù)，每循環(huán)一次減半
for nSize :=len(data);nSize >1;nSize = (nSize+1)/2{
//第二條循環(huán)i+=2代表兩兩拼接。 i2是為了當(dāng)個(gè)數(shù)是基數(shù)的時(shí)候，拷貝最后的元素。
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代表的是某一層的第一個(gè)元素
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
}
//默克爾樹節(jié)點(diǎn)
type MerkleTree struct{
RootNode *MerkleNode
}
//默克爾根節(jié)點(diǎn)
type MerkleNode struct{
Left *MerkleNode
Right *MerkleNode
Data []byte
}
//生成默克爾樹中的節(jié)點(diǎn)，如果是葉子節(jié)點(diǎn)，則Left，right為nil ，如果為非葉子節(jié)點(diǎn)，根據(jù)Left，right生成當(dāng)前節(jié)點(diǎn)的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
}
//構(gòu)建默克爾樹
func NewMerkleTree(data [][]byte) *MerkleTree{
var nodes []MerkleNode
//構(gòu)建葉子節(jié)點(diǎn)。
for _,datum := range data{
node:= NewMerkleNode(nil,nil,datum)
nodes = append(nodes,*node)
}
//j代表的是某一層的第一個(gè)元素
j:=0
//第一層循環(huán)代表 nSize代表某一層的個(gè)數(shù)，每循環(huán)一次減半
for nSize :=len(data);nSize >1;nSize = (nSize+1)/2{
//第二條循環(huán)i+=2代表兩兩拼接。 i2是為了當(dāng)個(gè)數(shù)是基數(shù)的時(shí)候，拷貝最后的元素。
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代表的是某一層的第一個(gè)元素
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(){
//測(cè)試網(wǎng)站下的5個(gè)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")
//大小段轉(zhuǎn)換
ReverseBytes3(data1)
ReverseBytes3(data2)
ReverseBytes3(data3)
ReverseBytes3(data4)
ReverseBytes3(data5)
hehe := [][]byte{
data1,
data2,
data3,
data4,
data5,
}
//生成默克爾樹
merleroot:= NewMerkleTree(hehe)
//反轉(zhuǎn)
ReverseBytes3(merleroot.RootNode.Data)
fmt.Printf("%x",merleroot.RootNode.Data)
}
