Java手写简单Merkle树

 Java手写Merkle树代码

package com.blockchain.qgy.component;import com.blockchain.qgy.model.MerkleTreeNode;
import com.blockchain.qgy.util.SHAUtil;import java.util.*;public class MerkleTree<T> {//merkle树private List<MerkleTreeNode<T>> list;//根节点private MerkleTreeNode<T> root;public MerkleTree(List<T> nodes){createMerkleTree(nodes);}/*** function 初始化merkle树* @param nodes: 数据集合*/private void createMerkleTree(List<T> nodes) {//判断入参if (Objects.isNull(nodes) || nodes.size() == 0) return;list = new ArrayList<>();//创建叶子节点List<MerkleTreeNode<T>> leafList = createLeafList(nodes);list.addAll(leafList);//创建父级节点List<MerkleTreeNode<T>> parents = new ArrayList<>(leafList);//循环创建直到找到根节点do {List<MerkleTreeNode<T>> temp = new ArrayList<>(parents);temp = createParentList(temp);parents = temp;list.addAll(parents);}while (parents.size() > 1);root = parents.get(0);}/*** function 初始化父亲节点* @param leafList：叶子节点* @return 父节点*/private List<MerkleTreeNode<T>> createParentList(List<MerkleTreeNode<T>> leafList) {//判断入参if (Objects.isNull(leafList) || leafList.size() == 0) return new ArrayList<>();List<MerkleTreeNode<T>> parents = new ArrayList<>();int length = leafList.size();for(int i = 0;i < length - 1; i += 2){MerkleTreeNode<T> parent = createParentNode(leafList.get(i),leafList.get(i+1));parents.add(parent);}//当节点数为奇数时，单独进行处理if ((length & 1) == 1) {MerkleTreeNode<T> parent = createParentNode(leafList.get(length - 1),null);parents.add(parent);}return parents;}/*** function 生成一个父节点* @param left：左节点* @param right：右节点* @return 父节点*/private MerkleTreeNode<T> createParentNode(MerkleTreeNode<T> left, MerkleTreeNode<T> right) {MerkleTreeNode<T> parent = new MerkleTreeNode<>();parent.setLeft(left);parent.setRight(right);String hash = left.getHash();if(!Objects.isNull(parent.getRight())) {hash = SHAUtil.sha256BasedHutool(hash.concat(parent.getRight().getHash()));}parent.setHash(hash);parent.setName("无人签名");parent.setData((T) new Object());return parent;}/*** function 初始化叶子节点* @param nodes：数据集合* @return merkle的叶子节点*/private List<MerkleTreeNode<T>> createLeafList(List<T> nodes) {//判断入参if (Objects.isNull(nodes) || nodes.size() == 0) return new ArrayList<>();List<MerkleTreeNode<T>> leafList = new ArrayList<>();for(T curr : nodes) {MerkleTreeNode<T> node = new MerkleTreeNode<>(curr);leafList.add(node);}return leafList;}public void printfTree() {Collections.reverse(list);MerkleTreeNode<T> root = list.get(0);Queue<MerkleTreeNode<T>> queue = new LinkedList<MerkleTreeNode<T>>(){{offer(root);}};printfTree(queue,1);}public void printfTree(Queue<MerkleTreeNode<T>> queue,Integer floor) {Queue<MerkleTreeNode<T>> currQueue = new LinkedList<>();System.out.println("第"+floor+"层--------------------------------------------------------------------------------------------------------------------------");while (!queue.isEmpty()) {MerkleTreeNode<T> poll = queue.poll();System.out.println(poll.toString());if(!Objects.isNull(poll.getLeft())) currQueue.offer(poll.getLeft());if(!Objects.isNull(poll.getRight())) currQueue.offer(poll.getRight());}if (!currQueue.isEmpty()) printfTree(currQueue,floor+1);}public List<MerkleTreeNode<T>> getList() {return list;}public MerkleTreeNode<T> getRoot() {return root;}public void setList(List<MerkleTreeNode<T>> list) {this.list = list;}public void setRoot(MerkleTreeNode<T> root) {this.root = root;}}

package com.blockchain.qgy.model;import com.blockchain.qgy.util.SHAUtil;public class MerkleTreeNode<T> {//左节点private MerkleTreeNode<T> left;//右节点private MerkleTreeNode<T> right;//区块数据private T data;//节点hash值private String hash;//数字签名private String name;public MerkleTreeNode() {}public MerkleTreeNode(T data) {this.data = data;this.hash = SHAUtil.sha256BasedHutool(data.toString());this.name = "无人签名";}public MerkleTreeNode(T data, String name){this.data = data;this.hash = SHAUtil.sha256BasedHutool(data.toString());this.name = name;}public MerkleTreeNode<T> getLeft() {return left;}public void setLeft(MerkleTreeNode<T> left) {this.left = left;}public MerkleTreeNode<T> getRight() {return right;}public void setRight(MerkleTreeNode<T> right) {this.right = right;}public T getData() {return data;}public void setData(T data) {this.data = data;}public String getHash() {return hash;}public void setHash(String hash) {this.hash = hash;}public String getName() {return name;}public void setName(String name) {this.name = name;}@Overridepublic String toString() {return  "MerkleTreeNode:\n" +"name:" + name + ";\n" +"data:" + data + ";\n" +"------------\n";}
}

 

注意：这里用了SHAUtil工具类，该部分代码链接如下：

SHAUtil代码

测试代码

package com.blockchain.qgy.test;import com.blockchain.qgy.component.MerkleTree;
import com.blockchain.qgy.model.MerkleTreeNode;
import org.testng.annotations.Test;import java.util.Arrays;
import java.util.List;public class MerkleTreeTest {@Testpublic void Test(){List<String> contents = Arrays.asList("星","极","天","下","第","一");MerkleTree<String> stringMerkleTree = new MerkleTree<>(contents);stringMerkleTree.printfTree();MerkleTreeNode<String> root = stringMerkleTree.getRoot();System.out.println("root:"+root);System.out.println("hash:"+root.getHash());}
}

结果：

"C:\Program Files\Java\jdk1.8.0_261\bin\java.exe" -ea -Didea.test.cyclic.buffer.size=1048576 "-javaagent:D:\idea\IntelliJ IDEA 2020.2.1\lib\idea_rt.jar=55223:D:\idea\IntelliJ IDEA 2020.2.1\bin" -Dfile.encoding=UTF-8 -classpath "D:\idea\IntelliJ IDEA 2020.2.1\lib\idea_rt.jar;D:\idea\IntelliJ IDEA 2020.2.1\plugins\testng\lib\testng-rt.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_261\jre\lib\rt.jar;D:\项目\区块链\target\classes;C:\Users\86153\Desktop\java架包\org\testng\testng\6.8.7\testng-6.8.7.jar;C:\Users\86153\Desktop\java架包\junit\junit\4.10\junit-4.10.jar;C:\Users\86153\Desktop\java架包\org\hamcrest\hamcrest-core\1.1\hamcrest-core-1.1.jar;C:\Users\86153\Desktop\java架包\org\beanshell\bsh\2.0b4\bsh-2.0b4.jar;C:\Users\86153\Desktop\java架包\com\beust\jcommander\1.27\jcommander-1.27.jar;C:\Users\86153\Desktop\java架包\org\yaml\snakeyaml\1.12\snakeyaml-1.12.jar;C:\Users\86153\Desktop\java架包\org\mockito\mockito-all\1.9.5\mockito-all-1.9.5.jar;C:\Users\86153\Desktop\java架包\com\xiaoleilu\hutool-all\3.0.9\hutool-all-3.0.9.jar;C:\Users\86153\Desktop\java架包\com\google\crypto\tink\tink\1.2.0\tink-1.2.0.jar;C:\Users\86153\Desktop\java架包\com\amazonaws\aws-java-sdk-core\1.11.166\aws-java-sdk-core-1.11.166.jar;C:\Users\86153\Desktop\java架包\software\amazon\ion\ion-java\1.0.2\ion-java-1.0.2.jar;C:\Users\86153\Desktop\java架包\com\fasterxml\jackson\dataformat\jackson-dataformat-cbor\2.6.7\jackson-dataformat-cbor-2.6.7.jar;C:\Users\86153\Desktop\java架包\joda-time\joda-time\2.8.1\joda-time-2.8.1.jar;C:\Users\86153\Desktop\java架包\com\amazonaws\aws-java-sdk-kms\1.11.166\aws-java-sdk-kms-1.11.166.jar;C:\Users\86153\Desktop\java架包\com\amazonaws\jmespath-java\1.11.166\jmespath-java-1.11.166.jar;C:\Users\86153\Desktop\java架包\com\fasterxml\jackson\core\jackson-databind\2.6.7.1\jackson-databind-2.6.7.1.jar;C:\Users\86153\Desktop\java架包\com\fasterxml\jackson\core\jackson-annotations\2.6.0\jackson-annotations-2.6.0.jar;C:\Users\86153\Desktop\java架包\com\google\api-client\google-api-client\1.22.0\google-api-client-1.22.0.jar;C:\Users\86153\Desktop\java架包\com\google\oauth-client\google-oauth-client\1.22.0\google-oauth-client-1.22.0.jar;C:\Users\86153\Desktop\java架包\com\google\http-client\google-http-client\1.22.0\google-http-client-1.22.0.jar;C:\Users\86153\Desktop\java架包\org\apache\httpcomponents\httpclient\4.0.1\httpclient-4.0.1.jar;C:\Users\86153\Desktop\java架包\org\apache\httpcomponents\httpcore\4.0.1\httpcore-4.0.1.jar;C:\Users\86153\Desktop\java架包\commons-logging\commons-logging\1.1.1\commons-logging-1.1.1.jar;C:\Users\86153\Desktop\java架包\commons-codec\commons-codec\1.3\commons-codec-1.3.jar;C:\Users\86153\Desktop\java架包\com\google\http-client\google-http-client-jackson2\1.22.0\google-http-client-jackson2-1.22.0.jar;C:\Users\86153\Desktop\java架包\com\fasterxml\jackson\core\jackson-core\2.1.3\jackson-core-2.1.3.jar;C:\Users\86153\Desktop\java架包\com\google\apis\google-api-services-cloudkms\v1-rev9-1.22.0\google-api-services-cloudkms-v1-rev9-1.22.0.jar;C:\Users\86153\Desktop\java架包\com\google\guava\guava\25.0-jre\guava-25.0-jre.jar;C:\Users\86153\Desktop\java架包\com\google\code\findbugs\jsr305\1.3.9\jsr305-1.3.9.jar;C:\Users\86153\Desktop\java架包\org\checkerframework\checker-compat-qual\2.0.0\checker-compat-qual-2.0.0.jar;C:\Users\86153\Desktop\java架包\com\google\errorprone\error_prone_annotations\2.1.3\error_prone_annotations-2.1.3.jar;C:\Users\86153\Desktop\java架包\com\google\j2objc\j2objc-annotations\1.1\j2objc-annotations-1.1.jar;C:\Users\86153\Desktop\java架包\org\codehaus\mojo\animal-sniffer-annotations\1.14\animal-sniffer-annotations-1.14.jar;C:\Users\86153\Desktop\java架包\com\google\auto\service\auto-service\1.0-rc4\auto-service-1.0-rc4.jar;C:\Users\86153\Desktop\java架包\com\google\auto\auto-common\0.8\auto-common-0.8.jar;C:\Users\86153\Desktop\java架包\com\google\protobuf\protobuf-java\3.3.0\protobuf-java-3.3.0.jar;C:\Users\86153\Desktop\java架包\org\json\json\20170516\json-20170516.jar;D:\idea\IntelliJ IDEA 2020.2.1\plugins\testng\lib\jcommander-1.27.jar" com.intellij.rt.testng.RemoteTestNGStarter -usedefaultlisteners false -socket55222 @w@C:\Users\86153\AppData\Local\Temp\idea_working_dirs_testng.tmp -temp C:\Users\86153\AppData\Local\Temp\idea_testng.tmp
[TestNG] Running:
  C:\Users\86153\AppData\Local\JetBrains\IntelliJIdea2020.2\temp-testng-customsuite.xml

第1层------------------------------------------------------------------------------------------------------------------
MerkleTreeNode:
name:无人签名;
data:java.lang.Object@b684286;
------------

第2层------------------------------------------------------------------------------------------------------------------
MerkleTreeNode:
name:无人签名;
data:java.lang.Object@880ec60;
------------

MerkleTreeNode:
name:无人签名;
data:java.lang.Object@3f3afe78;
------------

第3层------------------------------------------------------------------------------------------------------------------
MerkleTreeNode:
name:无人签名;
data:java.lang.Object@7f63425a;
------------

MerkleTreeNode:
name:无人签名;
data:java.lang.Object@36d64342;
------------

MerkleTreeNode:
name:无人签名;
data:java.lang.Object@39ba5a14;
------------

第4层------------------------------------------------------------------------------------------------------------------
MerkleTreeNode:
name:无人签名;
data:星;
------------

MerkleTreeNode:
name:无人签名;
data:极;
------------

MerkleTreeNode:
name:无人签名;
data:天;
------------

MerkleTreeNode:
name:无人签名;
data:下;
------------

MerkleTreeNode:
name:无人签名;
data:第;
------------

MerkleTreeNode:
name:无人签名;
data:一;
------------

root:MerkleTreeNode:
name:无人签名;
data:java.lang.Object@b684286;
------------

hash:4e8da83f3ee3cb2ddb2d5dec5724a0c01bb4f6f48d2f7c3dd46f51158b26b5f4

===============================================
Default Suite
Total tests run: 1, Failures: 0, Skips: 0
===============================================

Process finished with exit code 0