1
package merkle
2

3
import (
4
    "crypto/sha256"
5
    "encoding/hex"
6
)
7

8
// MerkleTree 表示一棵 Merkle 树
9
type MerkleTree struct {
10
    Root   *Node
11
    Leaves []*Node
12
}
13

14
// Node 表示树中的一个节点
15
type Node struct {
16
    Hash  string
17
    Left  *Node
18
    Right *Node
19
}
20

21
// NewMerkleTree 从数据块列表构建 Merkle 树
22
func NewMerkleTree(data [][]byte) *MerkleTree {
23
    // 构建叶子节点
24
    var leaves []*Node
25
    for _, d := range data {
26
        hash := sha256.Sum256(d)
27
        leaves = append(leaves, &Node{Hash: hex.EncodeToString(hash[:])})
28
    }
29

30
    // 奇数个叶子时复制最后一个
31
    if len(leaves)%2 != 0 {
32
        leaves = append(leaves, leaves[len(leaves)-1])
33
    }
34

35
    // 自底向上构建树
36
    currentLevel := leaves
37
    for len(currentLevel) > 1 {
38
        var nextLevel []*Node
39
        // 奇数个节点时复制最后一个，避免访问越界
40
        if len(currentLevel)%2 != 0 {
41
            currentLevel = append(currentLevel, currentLevel[len(currentLevel)-1])
42
        }
43
        for i := 0; i < len(currentLevel); i += 2 {
44
            left := currentLevel[i]
45
            right := currentLevel[i+1]
46
            combined := left.Hash + right.Hash
47
            hash := sha256.Sum256([]byte(combined))
48
            parent := &Node{
49
                Hash:  hex.EncodeToString(hash[:]),
50
                Left:  left,
51
                Right: right,
52
            }
53
            nextLevel = append(nextLevel, parent)
54
        }
55
        currentLevel = nextLevel
56
    }
57

58
    return &MerkleTree{Root: currentLevel[0], Leaves: leaves}
59
}
60

61
// VerifyProof 验证某个叶子属于这棵树
62
func VerifyProof(leafHash string, proof []string, indices []bool, rootHash string) bool {
63
    current := leafHash
64
    for i, sibling := range proof {
65
        combined := sibling + current
66
        if indices[i] {
67
            combined = current + sibling
68
        }
69
        hash := sha256.Sum256([]byte(combined))
70
        current = hex.EncodeToString(hash[:])
71
    }
72
    return current == rootHash
73
}