文章目录
前言一、Merkle树简介二、java实现1.代码如下：2.测试
总结
前言
学习区块链技术，那么Merkle树不得不去深入了解。本文将用java手写Merkle树
一、Merkle树简介
Merkle树是1979 年Ralph Merkle提出并用自己名字命名的一种数据结构。什么是 Merkle 树呢？维基百科中对 Merkle 树的定义如下：
在密码学和计算机科学中，哈希树或 Merkle 树是一种树，其中每个叶子节点 都标记有数据块的哈希，而每个非叶子节 ，点都标记有其子节，或标签的加 密哈希 Merkle 树允许对大型数据结构的内容进行有效、安全的验证，是散列列表和散列链的泛化！
Merkle树的结构如图如下图所示：
收集一个或多个新记录块，对这些记录进行散列，再将散列配对，散列，再次配对并再次散列，直到单个散列保留这个单独的哈希被称为merkle树的Merkle根。在比特币浏览器中如下图所示： 图中的1 2 3 4二二合一，最终得到了Merkle Root：f3e94742aca4b5ef85488dc37c06c3282295ffec960994b2c0d5ac2a25a95766 有兴趣的可以看看bitcoin代码之MerkleTree这篇文章。
二、java实现
1.代码如下：
package org
.xiangbiao
;
import cn
.hutool
.crypto
.SecureUtil
;
import java
.util
.ArrayList
;
import java
.util
.Collections
;
import java
.util
.List
;
public class MerkleTrees {
String merkleRoot
;
List
<String> txLst
;
public MerkleTrees(List
<String> txList
) {
this.txLst
= txList
;
merkleRoot
= "";
}
private List
<String> getNodeHashList(List
<String> tempTxList
) {
List
<String> newTxList
= new ArrayList<String>();
int index
= 0;
while (index
< tempTxList
.size()) {
String left
= tempTxList
.get(index
);
index
++;
String right
= "";
if (index
!= tempTxList
.size()) {
right
= tempTxList
.get(index
);
}
String sha2HexValue
= SecureUtil
.sha256(left
+ right
);
sha2HexValue
= SecureUtil
.sha256(sha2HexValue
);
newTxList
.add(sha2HexValue
);
index
++;
}
return newTxList
;
}
public void merkle_tree() {
List
<String> tempTxList
= new ArrayList<String>();
for (int i
= 0; i
< this.txLst
.size(); i
++) {
tempTxList
.add(this.txLst
.get(i
));
}
List
<String> newTxList
= getNodeHashList(tempTxList
);
while (newTxList
.size() != 1) {
newTxList
= getNodeHashList(newTxList
);
}
this.merkleRoot
= newTxList
.get(0);
}
public String
getMerkleRoot() {
return this.merkleRoot
;
}
2.测试
代码如下（示例）：
public static void main(String
[] args
) {
List
<String> tempTxList
= new ArrayList<String>();
tempTxList
.add("80c6f121c3e9fe0a59177e49874d8c703cbadee0700a782e4002e87d862373c6");
tempTxList
.add("b86f5ef1da8ddbdb29ec269b535810ee61289eeac7bf2b2523b494551f03897c");
MerkleTrees merkleTrees
= new MerkleTrees(tempTxList
);
merkleTrees
.merkle_tree();
System
.out
.println("root : " + merkleTrees
.getMerkleRoot());
}
}
总结
由于哈希算法结果较长，我们用简化版的结果来举例，假设目前某区块包含两笔交易，双重哈希之后：
在执行【两两一组拼接】时，简单将111和222拼一起：111222，就完成拼接了。(实际的拼接，是需要将哈希结果解码为计算机语言、位移、拼接、编码、位移，最终才能得到结果。)
拼接前，所有交易假设有n个，拼接后，剩下的个数就为n/2个了。
多次【双重哈希算法+两两一组拼接】，就是多次执行上述操作，最开始总交易个数有n个，执行一次，还有n/2个，再执行一次，还有n/4个，最终执行到结果只有1个的时候停止，再对结果做两次哈希运算，得到的结果就是merkle根值了。
