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
        for i := 0; i < len(currentLevel); i += 2 {
40
            left := currentLevel[i]
41
            right := currentLevel[i+1]
42
            combined := left.Hash + right.Hash
43
            hash := sha256.Sum256([]byte(combined))
44
            parent := &Node{
45
                Hash:  hex.EncodeToString(hash[:]),
46
                Left:  left,
47
                Right: right,
48
            }
49
            nextLevel = append(nextLevel, parent)
50
        }
51
        currentLevel = nextLevel
52
    }
53

54
    return &MerkleTree{Root: currentLevel[0], Leaves: leaves}
55
}
56

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

1
function hash(data: string): string {
2
  let h = 0x811c9dc5;
3
  for (let i = 0; i < data.length; i++) {
4
    h ^= data.charCodeAt(i);
5
    h = Math.imul(h, 0x01000193);
6
  }
7
  return (h >>> 0).toString(16).padStart(8, "0");
8
}
9

10
class MerkleTree {
11
  private leaves: string[];
12
  private layers: string[][];
13

14
  constructor(data: string[]) {
15
    // 奇数个叶子时复制最后一个
16
    if (data.length % 2 !== 0) data.push(data[data.length - 1]);
17
    this.leaves = data.map((d) => hash(d));
18
    this.layers = [this.leaves];
19
    this.build();
20
  }
21

22
  private build(): void {
23
    let current = this.leaves;
24
    while (current.length > 1) {
25
      const next: string[] = [];
26
      for (let i = 0; i < current.length; i += 2) {
27
        next.push(hash(current[i] + current[i + 1]));
28
      }
29
      this.layers.push(next);
30
      current = next;
31
    }
32
  }
33

34
  getRoot(): string {
35
    const top = this.layers[this.layers.length - 1];
36
    return top[0];
37
  }
38

39
  // 获取验证某叶子所需的兄弟哈希路径
40
  getProof(index: number): { hash: string; isRight: boolean }[] {
41
    const proof: { hash: string; isRight: boolean }[] = [];
42
    let idx = index;
43
    for (let layer = 0; layer < this.layers.length - 1; layer++) {
44
      const siblingIdx = idx % 2 === 0 ? idx + 1 : idx - 1;
45
      proof.push({
46
        hash: this.layers[layer][siblingIdx],
47
        isRight: siblingIdx > idx,
48
      });
49
      idx = Math.floor(idx / 2);
50
    }
51
    return proof;
52
  }
53

54
  // 验证叶子属于这棵树
55
  static verify(
56
    leafHash: string,
57
    proof: { hash: string; isRight: boolean }[],
58
    rootHash: string
59
  ): boolean {
60
    let current = leafHash;
61
    for (const step of proof) {
62
      current = step.isRight
63
        ? hash(current + step.hash)
64
        : hash(step.hash + current);
65
    }
66
    return current === rootHash;
67
  }
68
}