默克尔树(Merkle tree)的Go实现

1
package main
2

3
import (
4
  "bufio"
5
  "crypto/sha256"
6
  "fmt"
7
  "os"
8
  "strconv"
9
)
10

11
//默克尔树节点结构体
12
type Node struct {
13
  Index    int
14
  Value    string
15
  RootTree *MHTree
16
}
17

18
//默克尔树结构体
19
type MHTree struct {
20
  Length   int
21
  Nodes    []Node
22
  rootHash string
23
}
24

25
//获得默克尔树根节点哈希值
26
func (t *MHTree) GetRootHash() string {
27
  //不管是否存储，都重新计算哈希值
28
  t.rootHash =   t.Nodes[1].getNodeHash()
29
  return t.rootHash
30
}
31

32
//计算默克尔树中某个节点的哈希值
33
func (n *Node) getNodeHash() string {
34
  //叶子节点，则直接计算该节点Value的哈希值
35
  if n.Value != "" {
36
    return calDataHash(n.Value)
37
  }
38
  //非叶子节点，则递归计算哈希值,其为2个子节点哈希值的哈希值123123123123
39
    return calDataHash(n.RootTree.Nodes[n.Index*2].getNodeHash() + n.RootTree.Nodes[n.Index*2+1].getNodeHash()
40
        )
41

42
//计算数据的哈希值
43
func calDataHash(data string) string {
44
  hash := sha256.New()
45
  hash.Write([]byte(data))
46
  return string(hash.Sum(nil))
47
}
48

49
//从结构化文件创建默克尔树
50
func CreateMHTree(fileName string) MHTree {
51
  var tree MHTree
52
  //打开文件
53
  file, err := os.Open(fileName)
54
  if err != nil {
55
    panic(err)
56
  }
57
  defer file.Close()
58
  //获取读取器
59
  buf := bufio.NewReader(file)
60
  //读取首行，获得叶子节点数目（要求叶子节点数目为2的整数次幂
61
  dataCountStr, _, _ := buf.ReadLine()
62
  dataCount, _ := strconv.Atoi(string(dataCountStr))
63

64
  //判断幂次
65
  level := 0
66
  for i := 1; ; i++ {
67
    if 2<<i == dataCount {
68
      level = i
69
      break
70
    }
71
  }
72
  //创建默克尔树
73

74
  //给非叶子节点赋值
75
  for i := 1; i <= 2<<level-1; i++ {
76
    tree.Nodes[i].Index = i
77
    tree.Nodes[i].RootTree = &tree
78
  }
79
  //读取文件数据，给叶子节点赋值
80
  for i := 2 << level; i < tree.Length; i++ {
81
    str, _, _ := buf.ReadLine()
82
    tree.Nodes[i].Index = i
83
    tree.Nodes[i].RootTree = &tree
84
    tree.Nodes[i].Value = string(str)
85
  }
86
  return tree
87
}
88

89
func main() {
90
  var fileName string
91

92
  fmt.Println("请输入原始数据文件名称")
93
  fmt.Scanln(&fileName)
94
  mhTree1 := CreateMHTree(fileName)
95
  fmt.Println("请输入比对数据文件名称")
96
  fmt.Scanln(&fileName)
97
  mhTree2 := CreateMHTree(fileName)
98

99
  hash1 := mhTree1.GetRootHash()
100
  hash2 := mhTree2.GetRootHash()
101

102
  if hash1 == hash2 {
103
    fmt.Println("用户没有改变数据")
104
  } else {
105
    fmt.Println("用户改变了数据")
106
  }
107

108
}