默克尔树

默克尔树（Merkle tree）是一种哈希树的结构

常用于数据完整性验证和快速数据检索。在比特币中，每个区块的交易记录就是通过默克尔树组织起来的。在本文中，我们将使用Go语言实现一个简单的默克尔树。

首先，我们需要定义一个数据结构来表示默克尔树节点：

type MerkleNode struct {
    Left  *MerkleNode
    Right *MerkleNode
    Data  []byte
}

MerkleNode包含三个字段：Left和Right表示左右子节点，Data表示节点的数据。对于叶子节点，Data为交易记录的哈希值；对于非叶子节点，Data为左右子节点的哈希值的拼接。

接下来，我们实现一个函数来创建默克尔树节点：

func NewMerkleNode(left, right *MerkleNode, data []byte) *MerkleNode {
    node := MerkleNode{}

    if left == nil && right == nil {
        node.Data = data
    } else {
        prevHashes := append(left.Data, right.Data...)
        hash := sha256.Sum256(prevHashes)
        node.Data = hash[:]
    }

    node.Left = left
    node.Right = right

    return &node
}

NewMerkleNode函数接受左右子节点和数据作为参数，返回一个新的默克尔树节点。如果左右子节点都为空，则该节点为叶子节点，Data为数据的哈希值；否则，该节点为非叶子节点，Data为左右子节点的哈希值的拼接。左右子节点和Data字段将分别设置为函数参数的值。

最后，我们可以编写一个函数来生成默克尔树：

func NewMerkleTree(data [][]byte) *MerkleNode {
    var nodes []*MerkleNode

    for _, d := range data {
        node := NewMerkleNode(nil, nil, d)
        nodes = append(nodes, node)
    }

    for len(nodes) > 1 {
        var level []*MerkleNode

        for len(nodes) > 0 {
            left := nodes[0]
            nodes = nodes[1:]

            var right *MerkleNode

            if len(nodes) > 0 {
                right = nodes[0]
                nodes = nodes[1:]
            }

            node := NewMerkleNode(left, right, nil)
            level = append(level, node)
        }

        nodes = level
    }

    return nodes[0]
}

NewMerkleTree函数接受一个二维字节数组作为参数，其中每个字节数组表示一个交易记录的哈希值。该函数首先将每个哈希值转换为一个默克尔树节点，并将这些节点添加到一个节点列表中。然后，函数使用节点列表生成默克尔树，直到树的根节点生成为止。最后，函数返回树的根节点

下面我写完整代码：

在MerkleTree结构体中，我们定义了树的节点类型Node，它包含一个哈希值Hash和指向父节点和子节点的指针。另外，我们还定义了一个MerklePath结构体，它用于存储从叶子节点到根节点的路径。路径上的每个节点包含了它的兄弟节点的哈希值和它在父节点中的位置。

接下来，我们实现树的构建和哈希计算方法。在buildTree方法中，我们首先将所有数据块转换为节点，并将它们添加到叶子节点列表中。然后，我们在循环中计算每个节点的哈希值，将它们添加到父节点的子节点列表中，并将父节点添加到父节点列表中。直到只剩下根节点为止。

在calculateHash方法中，我们使用sha256哈希算法计算节点的哈希值。

最后，我们实现了generateMerklePath方法，它用于生成指定叶子节点到根节点的路径。在循环中，我们依次获取节点的兄弟节点的哈希值，并将它们添加到路径上。直到到达根节点为止。

package main

import (
	"crypto/sha256"
	"fmt"
)

// MerkleTree 表示默克尔树结构
type MerkleTree struct {
	LeafNodes []Node // 叶子节点列表
	RootNode  *Node  // 根节点
}

// Node 表示默克尔树的一个节点
type Node struct {
	Hash       []byte // 节点的哈希值
	LeftChild  *Node  // 左子节点指针
	RightChild *Node  // 右子节点指针
	Parent     *Node  // 父节点指针
}

// MerklePath 表示默克尔树中某个叶子节点的路径
type MerklePath struct {
	Hashes [][]byte // 路径中涉及到的节点的哈希值列表
	Lefts  []bool   // 路径中每个节点是其父节点的左子节点还是右子节点的标记
}

// NewMerkleTree 根据数据构建一个默克尔树
func NewMerkleTree(data [][]byte) *MerkleTree {
	leafNodes := make([]Node, len(data))
	for i, d := range data {
		leafNodes[i] = Node{
			Hash: calculateHash(d), // 计算数据的哈希值并赋值给叶子节点
		}
	}
	return &MerkleTree{
		LeafNodes: leafNodes,
	}
}

// buildTree 构建默克尔树
func (mt *MerkleTree) buildTree() {
	nodes := mt.LeafNodes
	for len(nodes) > 1 {
		var parentNodes []Node
		for i := 0; i < len(nodes); i += 2 {
			var left, right *Node
			if i < len(nodes)-1 {
				left = &nodes[i]
				right = &nodes[i+1]
			} else {
				left = &nodes[i]
				right = left
			}
			parent := Node{
				LeftChild:  left,
				RightChild: right,
				Hash:       calculateHash(append(left.Hash, right.Hash...)), // 计算左右子节点的哈希值并拼接为父节点的哈希值
			}
			left.Parent = &parent
			right.Parent = &parent
			parentNodes = append(parentNodes, parent)
		}
		nodes = parentNodes
	}
	mt.RootNode = &nodes[0] // 最后剩下的节点就是根节点
}

// calculateHash 计算哈希值
func calculateHash(data []byte) []byte {
	h := sha256.New()
	h.Write(data)
	return h.Sum(nil)
}
func (mt *MerkleTree) generateMerklePath(index int) *MerklePath {
	node := &mt.LeafNodes[index]
	path := &MerklePath{
		Hashes: [][]byte{},
		Lefts:  []bool{},
	}
	for node.Parent != nil {
		parent := node.Parent
		isLeftChild := parent.LeftChild == node
		if isLeftChild {
			path.Lefts = append(path.Lefts, true)
			path.Hashes = append(path.Hashes, parent.RightChild.Hash)
		} else {
			path.Lefts = append(path.Lefts, false)
			path.Hashes = append(path.Hashes, parent.LeftChild.Hash)
		}
		node = parent
	}
	return path
}

func main() {
	data := [][]byte{
		[]byte("a"),
		[]byte("b"),
		[]byte("c"),
		[]byte("d"),
	}
	tree := NewMerkleTree(data)
	tree.buildTree()
	fmt.Printf("Merkle Root Hash: %x\n", tree.RootNode.Hash)

	path := tree.generateMerklePath(1)
	fmt.Printf("Merkle Path for index %d:\n", 1)
	for i := 0; i < len(path.Hashes); i++ {
		fmt.Printf("Hash: %x, is left child: %t\n", path.Hashes[i], path.Lefts[i])
	}
}