梅克尔树的结构比较简单,其设计思想比较巧妙,它是SPV实现的关键。
梅克尔树是二叉树,节点存储哈希指针,叶子节点保存数据。
- Merkle Tree节点结构体
type MerkleNode struct {
Left *MerkleNode
Right *MerkleNode
Data []byte
}
- 创建Merkle Tree节点
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
}
- 构建Merkle Tree
func NewMerkleTree(data [][]byte) *MerkleTree {
var nodes []MerkleNode
if len(data) % 2 != 0 {
data = append(data, data[len(data) - 1])
}
for _, dataitem := range data {
node := NewMerkleNode(nil, nil, dataitem)
nodes = append(nodes, *node)
}
for i := 0; i<len(data)/2; i++ {
var newNodes []MerkleNode
for j := 0; j < len(nodes); j += 2 {
node := NewMerkleNode(&nodes[j], &nodes[j+1], nil)
newNodes = append(newNodes , *node)
}
nodes = newNodes
}
mTree := MerkleTree{&nodes[0]}
return &mTree
}