什么是默克尔树？？
默克尔树是一种哈希二叉树，1979年由RalphMerkle发明。哈希树可以用来验证任何一种在计算机中和计算机之间存储、处理和传输的数据。它们可以确保在点对点网络中数据传输的速度不受影响，数据跨越自由的通过任意媒介，且没有损坏，也没有改变。
简单来说，哈希树（默克尔树）中，每个节点都标有一个数据块的加密哈希值。
Merkle树结构
- 一个根节点（root）
- 一组中间节点
- 一组叶节点（leaf）组成
叶节点（leaf）包含存储数据或其哈希值，中间节点是它的两个子节点内容的哈希值，根节点也是由它的两个子节点内容的哈希值组成。所以Merkle树也称哈希树。
哈希树的特点
任意底层数据的任何变动，都会传递到其父节点，一直到树根。因此只需要判断Hash Root是否一致，就可以判断整个数据书否一致。
因此，在区块链系统中，区块头只需要封装默克尔根（也就是Hash Root），通过对默克尔根的比对，从而验证区块交易数据是否一致。 极大的提升了数据校验的效率。
Golang实现默克尔树
完整代码已发布至 https://github.com/wk331100/MerkleTree，可使用go get github.com/wk331100/MerkleTree 获取代码库。
package merkleTree
import (
"bytes"
"crypto/md5"
"crypto/sha1"
"crypto/sha256"
"crypto/sha512"
"errors"
"hash"
"math"
)
const (
errEmptyData = "empty data"
)
// MerkleTree 默克尔树
type MerkleTree struct {
Root *Node
Leaves []*Node
hashHandler func() hash.Hash
}
// Node 节点
type Node struct {
Parent *Node
Left *Node
Right *Node
leaf bool
single bool
Hash []byte
Data []byte
}
// GetRootHash 获取默克尔树根Hash
func (m *MerkleTree) GetRootHash() []byte {
return m.Root.Hash
}
// NewMerkleTree 创建一个新的 默克尔树
func NewMerkleTree(hashType string, data [][]byte) (*MerkleTree, error) {
mk := &MerkleTree{}
mk.hashHandler = mk.buildHash(hashType)
root, leaves, err := mk.buildMerkleTreeRoot(data)
if err != nil {
return nil, err
}
mk.Root = root
mk.Leaves = leaves
return mk, nil
}
// VerifyData 验证数据是否在默克尔树中
func (m *MerkleTree) VerifyData(data []byte) (bool, error) {
dataHash := m.calHash(data)
for _, leaf := range m.Leaves {
if bytes.Compare(dataHash, leaf.Hash) == 0 {
return true, nil
}
}
return false, nil
}
// VerifyTree 验证默克尔树Hash
func (m *MerkleTree) VerifyTree() (bool, error) {
calRoot, err := m.Root.verifyNode(m)
if err != nil {
return false, err
}
if bytes.Compare(calRoot, m.Root.Hash) == 0 {
return true, nil
}
return false, err
}
// verifyNode 重新计算节点Hash
func (n *Node) verifyNode(mk *MerkleTree) ([]byte, error) {
if n.leaf {
return mk.calHash(n.Data), nil
}
leftNodeHash, err := n.Left.verifyNode(mk)
if err != nil {
return nil, err
}
rightNodeHash, err := n.Right.verifyNode(mk)
if err != nil {
return nil, err
}
return mk.calHash(append(leftNodeHash, rightNodeHash...)), nil
}
// buildMerkleTree 构建 默克尔树 节点
func (m *MerkleTree) buildMerkleTreeRoot(data [][]byte) (*Node, []*Node, error) {
if len(data) <= 0 {
return nil, nil, errors.New(errEmptyData)
}
leaf := m.buildMerkleTreeLeaf(data)
root, err := m.buildMerkleTreeNode(leaf)
return root, leaf, err
}
// buildMerkleTreeNode 构建 默克尔树 中间节点
func (m *MerkleTree) buildMerkleTreeNode(nodes []*Node) (*Node, error) {
length := int(math.Ceil(float64(len(nodes)) / 2))
var nodeSlice []*Node
var single bool
for i := 0; i < length; i++ {
leftNode := nodes[i*2]
var rightNode = new(Node)
if i*2+1 < len(nodes) {
rightNode = nodes[i*2+1]
} else {
single = true
}
node := &Node{
Parent: nil,
Left: leftNode,
Right: rightNode,
leaf: false,
single: single,
Hash: nil,
Data: nil,
}
// 将两个子节点Hash拼接后，计算自身Hash
if !single {
leftNode.Hash = append(leftNode.Hash, rightNode.Hash...)
}
node.Hash = m.calHash(leftNode.Hash)
// 将当前节点设置为 两个子节点的父节点
nodes[i*2].Parent = node
nodes[i*2+1].Parent = node
nodeSlice = append(nodeSlice, node)
}
if len(nodeSlice) > 1 {
return m.buildMerkleTreeNode(nodeSlice)
}
return nodeSlice[0], nil
}
// buildMerkleTreeLeaf 构建 默克尔树 叶节点
func (m *MerkleTree) buildMerkleTreeLeaf(data [][]byte) []*Node {
var leaf []*Node
for _, item := range data {
node := &Node{
Parent: nil,
Left: nil,
Right: nil,
leaf: true,
single: false,
Hash: m.calHash(item),
Data: item,
}
leaf = append(leaf, node)
}
return leaf
}
// buildHash 根据Hash类型，构建Hash
func (m *MerkleTree) buildHash(hashType string) func() hash.Hash {
switch hashType {
case "md5":
return md5.New
case "sha1":
return sha1.New
case "sha256":
return sha256.New
case "sha512":
return sha512.New
default:
return sha1.New
}
}
func (m *MerkleTree) calHash(data []byte) []byte {
hashHandler := m.hashHandler()
hashHandler.Write(data)
return hashHandler.Sum(nil)
}
单测及结果
package merkleTree
import (
"encoding/json"
"fmt"
"testing"
"github.com/stretchr/testify/require"
)
var (
testData []byte
testHash []byte
)
func TestMerkleTree(t *testing.T) {
data := initData()
mk, err := NewMerkleTree("md5", data)
require.Nil(t, err)
fmt.Sprintf("%x", mk.GetRootHash())
printHash(mk)
res, _ := mk.VerifyData(testData)
require.True(t, res)
res2, _ := mk.VerifyTree()
require.True(t, res2)
}
func printHash(mk *MerkleTree) {
if mk.Root.leaf {
return
}
cyclePrint(mk.Root)
}
func cyclePrint(node *Node) {
if node.leaf {
fmt.Println(fmt.Sprintf("Leaf: hash[%x], data[%s], leaf[%v]\n", node.Hash, node.Data, node.leaf))
} else {
fmt.Println(fmt.Sprintf("Node: hash[%x], data[%s], leaf[%v]\n", node.Hash, node.Data, node.leaf))
}
if node.Left != nil {
cyclePrint(node.Left)
}
if node.Right != nil {
cyclePrint(node.Right)
}
}
func TestBuildMerkleTreeLeaf(t *testing.T) {
m := &MerkleTree{}
data := initData()
m.hashHandler = m.buildHash("sha256")
leaf := m.buildMerkleTreeLeaf(data)
fmt.Println(leaf)
}
func initData() [][]byte {
var data [][]byte
for i := 0; i < 4; i++ {
str := fmt.Sprintf("test data %d", i)
bz, _ := json.Marshal(str)
if i == 3 {
testData = bz
}
data = append(data, bz)
}
return data
}
结果
=== RUN TestMerkleTree
Node: hash[3c95e6ec5965e5c1b797709a8e649c14], data[], leaf[false]
Node: hash[e1c340b19bee346c95fe9ef64ad992e09820b47149a1893754e7557b0d7fdb13], data[], leaf[false]
Leaf: hash[56f0aade6664b4bf7ef30ab6de77ecd1481cf84fb2f19c94e04293027b39ad90], data["test data 0"], leaf[true]
Leaf: hash[481cf84fb2f19c94e04293027b39ad90], data["test data 1"], leaf[true]
Node: hash[9820b47149a1893754e7557b0d7fdb13], data[], leaf[false]
Leaf: hash[3381b0b53c7f1e8bb44d469dec35051565997690d1ade051def10b273ae49fe5], data["test data 2"], leaf[true]
Leaf: hash[65997690d1ade051def10b273ae49fe5], data["test data 3"], leaf[true]
--- PASS: TestMerkleTree (0.00s)
PASS
评论区