今天在写程序的时候需要生成默克尔树进行校验，但是在网上一搜，全部都是讲的原理，没看到什么代码，很是奇怪，就自己动手写了一个。

定义

实际上我是不想再写这个的，了解区块链的几乎都听说过这个词了，知道是文件完整性与合法性的很有力的验证工具。 我只要有了一个可信的默克尔根，那么初始文件我就一定能够检验是不是对的。

生成树流程

网上的树通常都是这么画的 merkletree 但是在我们生成的过程中，按照这个想法肯定很难想到解决办法，因为是分层结构的。 但是，反过来一想，我就是从最底层，两个节点连在一块算哈希，生成父节点。父节点再连一块生成它的父节点。 就像这样 merkletreereverse

一些问题

不知道大家看到没有，我们上面的图很巧，恰好都是两两连在一块的，如果是奇数个叶子节点呢？ merkletreemiss 问题不大，我们就把单独的节点再复制一份，凑成双数就好啦 merkletreecp

算法流程

看到了上面的图片，大家对于答题的流程应该有了一点印象，我们可以考虑怎么写到代码上了。 1. 定义变量list，存储每一层的节点数据level 2. 取出当前层的数据内容levelValue，每两个计算一个新的hash 3. 如果存在单独节点，复制一份计算hash 4. 定义变量nodeHash，存储计算出来的hash 5. 将level从list中移除，把nodeHash添加到list中 6. 循环往复，直到levelValue的长度只有一个

代码

废话不多说，我们看下代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

node := list.New()
node.PushBack(txHashes)
for node.Len() != 0 {
	//generate root step
	levelNode := node.Front()
	levelNodeValue := levelNode.Value.([]string)
	if len(levelNodeValue) == 1 {
		merkleRoot = util.GenStrHash(levelNodeValue[0])
		break
	}
	nodeHash := make([]string, 0)
	for i := 0; i < len(levelNodeValue); i += 2 {
		first := levelNodeValue[i]
		second := first
		if i+1 < len(levelNodeValue) {
			second = levelNodeValue[i+1]
		}
		hash := util.GenStrHash(first + second)
		nodeHash = append(nodeHash, hash)
	}
	node.Remove(levelNode)
	node.PushBack(nodeHash)
}

结果

算了，结果不截图了。大家有兴趣的可以参考下，应该有很大的优化空间