Skip to content

Instantly share code, notes, and snippets.

@eribeiro
Last active September 15, 2019 22:41
Show Gist options
  • Save eribeiro/39ff8b73c43d453edd041bf1305425e0 to your computer and use it in GitHub Desktop.
Save eribeiro/39ff8b73c43d453edd041bf1305425e0 to your computer and use it in GitHub Desktop.
package com.company;
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;
public final class MerkleTreeBuilder {
private static MessageDigest md;
static {
try {
md = MessageDigest.getInstance("sha1");
} catch (NoSuchAlgorithmException e) {
e.printStackTrace();
}
}
private MerkleTreeBuilder() {}
public static MerkleNode build(String... nodes) {
List<MerkleNode> leafs = getMerkleLeafNodes(nodes);
return buildTree(leafs).get(0);
}
private static List<MerkleNode> getMerkleLeafNodes(String[] nodes) {
var init = System.currentTimeMillis();
// List<MerkleNode> leafs = new ArrayList<>(nodes.length);
// for (String node : nodes) {
// leafs.add(of(node.getBytes()));
// }
List<MerkleNode> leafs = Arrays.asList(nodes)
.stream().map(x -> {
var data = x.getBytes();
return of(data);
})
.collect(Collectors.toList());
System.out.println("leaf nodes time: " + (System.currentTimeMillis() - init));
return leafs;
}
private static List<MerkleNode> buildTree(List<MerkleNode> leafs) {
if (leafs == null || leafs.isEmpty()) {
throw new IllegalArgumentException("Leafs cannot be null or empty");
}
if (leafs.size() == 1)
return leafs;
List<MerkleNode> nextLevel = new ArrayList<>();
for (int i = 0; i < leafs.size(); i += 2) {
if (i+1 < leafs.size()) {
MerkleNode node1 = leafs.get(i);
MerkleNode node2 = leafs.get(i + 1);
var newHash = node1.getHash() + node2.getHash();
MerkleNode newNode = of(newHash.getBytes());
newNode.setLeftNode(node1);
newNode.setRightNode(node2);
nextLevel.add(newNode);
} else {
nextLevel.add(leafs.get(i));
break;
}
}
return buildTree(nextLevel);
}
public static MerkleNode of(byte[] data) {
md.update(data);
var hexString = new BigInteger(1, md.digest()).toString(16);
md.reset();
return new MerkleNode(hexString, new String(data));
}
public static class MerkleNode {
private final String hash;
private final String value;
private MerkleNode leftNode;
private MerkleNode rightNode;
public MerkleNode(String hash) {
this.hash = hash;
this.value = null;
}
public MerkleNode(String hash, String value) {
this.hash = hash;
this.value = value;
}
public MerkleNode getLeftNode() {
return leftNode;
}
public void setLeftNode(MerkleNode leftNode) {
this.leftNode = leftNode;
}
public MerkleNode getRightNode() {
return rightNode;
}
public void setRightNode(MerkleNode rightNode) {
this.rightNode = rightNode;
}
public String getHash() {
return hash;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
MerkleNode that = (MerkleNode) o;
return hash.equals(that.hash);
}
@Override
public int hashCode() {
return Objects.hash(hash);
}
@Override
public String toString() {
return "{\"hash\": \"" + hash + "\",\n" +
"\"data\": \"" + value + "\",\n " +
"\"left\": " + leftNode + ",\n" +
"\"right\": " + rightNode + "}";
}
}
public static void main(String[] args) {
var length = 10;
String[] files = new String[length];
for (int i = 0; i < length; i++) {
files[i] = "file_" + i;
}
// var files = new File("/Users/eribeiro").list();
System.out.println(Arrays.toString(files));
long init = System.currentTimeMillis();
var root = MerkleTreeBuilder.build(files);
long lapse = System.currentTimeMillis() - init;
System.out.println(root);
System.out.println("whole tree time:" + lapse);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment