Golang实现默克尔树（merkle tree）

nianxian1年前 (2023-07-03)阅读数 238#国际

什么是默克尔树？？

默克尔树是一种哈希二叉树，1979年由RalphMerkle发明。哈希树可以用来验证任何一种在计算机中和计算机之间存储、处理和传输的数据。它们可以确保在点对点网络中数据传输的速度不受影响，数据跨越自由的通过任意媒介，且没有损坏，也没有改变。

简单来说，哈希树（默克尔树）中，每个节点都标有一个数据块的加密哈希值。

Merkle树结构

一个根节点（root）
一组中间节点
一组叶节点（leaf）组成

叶节点（leaf）包含存储数据或其哈希值，中间节点是它的两个子节点内容的哈希值，根节点也是由它的两个子节点内容的哈希值组成。所以Merkle树也称哈希树。

Golang实现默克尔树（merkle tree）

默克尔树哈希树的特点

任意底层数据的任何变动，都会传递到其父节点，一直到树根。因此只需要判断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

原文地址：https://cloud.tencent.com/developer/article/2137259