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

845 字

4 分钟

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

2023-08-23

Guides

go

Merkle trees#

Merkle树是区块链技术的基本组成部分。它是由不同数据块的散列组成的数学数据结构，用作块中所有交易的摘要。

它还允许对大量数据中的内容进行有效和安全的验证。此结构有助于验证数据的一致性和内容。比特币和以太坊都使用Merkle树结构。Merkle树也被称为哈希树。

从根本上说，Merkle树是数据结构树，其中每个叶节点都用数据块的哈希标记，非叶节点用加密标记其子节点标签的哈希值。叶节点是树中的最低节点。

图片.png

原理#

区块链中每个区块都会有一个 Merkle 树，它从叶子节点（树的底部）开始，一个叶子节点就是一个交易哈希。叶子节点的数量必须是双数，但是并非每个块都包含了双数的交易。如果一个块里面的交易数为单数，那么就将最后一个叶子节点（也就是 Merkle 树的最后一个交易，不是区块的最后一笔交易）复制一份凑成双数。

从下往上，两两成对，连接两个节点哈希，将组合哈希作为新的哈希。新的哈希就成为新的树节点。重复该过程，直到仅有一个节点，也就是树根。根哈希然后就会当作是整个块交易的唯一标示，将它保存到区块头，然后用于工作量证明。

代码实现#

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
}