Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
MerkleTree Implementation with very simple testing, implements proofPath creation and proofPath validation. Is heavily influenced by https://github.com/SimoneStefani/merkle-tree-java.
package tech.blockchainers.crypyapi.http.common;
import org.web3j.utils.Numeric;
import java.io.PrintStream;
// taken from https://github.com/eugenp/tutorials/blob/master/data-structures/src/main/java/com/baeldung/printbinarytree/BinaryTreePrinter.java
public class BinaryTreePrinter {
private MerkleTree tree;
public BinaryTreePrinter(MerkleTree tree) {
this.tree = tree;
}
private String traversePreOrder(MerkleTree root) {
if (root == null) {
return "";
}
StringBuilder sb = new StringBuilder();
sb.append(Numeric.toHexString(root.root.value));
String pointerRight = "└──";
String pointerLeft = (root.root.right != null) ? "├──" : "└──";
traverseNodes(sb, "", pointerLeft, root.root.left, root.root.right != null);
traverseNodes(sb, "", pointerRight, root.root.right, false);
return sb.toString();
}
private void traverseNodes(StringBuilder sb, String padding, String pointer, MerkleTree.MerkleNode node,
boolean hasRightSibling) {
if (node != null) {
sb.append("\n");
sb.append(padding);
sb.append(pointer);
sb.append(Numeric.toHexString(node.value));
StringBuilder paddingBuilder = new StringBuilder(padding);
if (hasRightSibling) {
paddingBuilder.append("");
} else {
paddingBuilder.append(" ");
}
String paddingForBoth = paddingBuilder.toString();
String pointerRight = "└──";
String pointerLeft = (node.right != null) ? "├──" : "└──";
traverseNodes(sb, paddingForBoth, pointerLeft, node.left, node.right != null);
traverseNodes(sb, paddingForBoth, pointerRight, node.right, false);
}
}
public void print(PrintStream os) {
os.print(traversePreOrder(tree));
}
}
package tech.blockchainers.crypyapi.http.common;
import com.google.common.primitives.Bytes;
import org.web3j.crypto.Hash;
import org.web3j.utils.Numeric;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class MerkleTree {
static class ProofPathElement {
Location location;
byte[] value;
public ProofPathElement(byte[] value, Location location) {
this.location = location;
this.value = value;
}
public Location getLocation() {
return location;
}
public byte[] getValue() {
return value;
}
@Override
public String toString() {
return "ProofPathElement{" +
"location=" + location +
", value=" + Numeric.toHexString(value) +
'}';
}
}
enum Location {
SMALLER, BIGGER;
}
MerkleNode root;
public MerkleTree(MerkleNode root) {
this.root = root;
}
static class MerkleNode {
byte[] value;
MerkleNode left;
MerkleNode right;
MerkleNode parent;
public MerkleNode(byte[] value) {
this.value = value;
}
public MerkleNode(MerkleNode left, MerkleNode right) {
this.value = Hash.sha256(Bytes.concat(left.value, right.value));
left.parent = this;
this.left = left;
right.parent = this;
this.right = right;
}
public List<ProofPathElement> proofPath() {
List<ProofPathElement> proofPath = new ArrayList<>();
return proofPath(proofPath, this);
}
private List<ProofPathElement> proofPath(List<ProofPathElement> proofPath, MerkleNode node) {
List<ProofPathElement> proofPathAppend = new ArrayList<>(proofPath);
if (node.parent == null) {
return proofPathAppend;
}
if (node.parent.left == node) {
proofPathAppend.add(new ProofPathElement(node.parent.right.value, Location.BIGGER));
return proofPath(proofPathAppend, node.parent);
} else if (node.parent.right == node) {
proofPathAppend.add(new ProofPathElement(node.parent.left.value, Location.SMALLER));
return proofPath(proofPathAppend, node.parent);
} else {
throw new IllegalStateException("But HOW?");
}
}
public static boolean validateProofPath(MerkleNode leaf, MerkleNode root, List<ProofPathElement> elements) {
byte[] hashedValue = leaf.value;
for (ProofPathElement element : elements) {
if (element.location == Location.SMALLER) {
hashedValue = Hash.sha256(Bytes.concat(element.value, hashedValue));
} else {
hashedValue = Hash.sha256(Bytes.concat(hashedValue, element.value));
}
}
return Arrays.equals(hashedValue, root.value);
}
@Override
public String toString() {
return "MerkleNode {" +
"value=" + Numeric.toHexString(this.value) + '}';
}
}
public static MerkleNode findNode(MerkleNode current, byte[] value) {
if (Arrays.equals(current.value, value)) {
return current;
} else {
if (current.left != null) {
MerkleNode left = findNode(current.left, value);
if (left != null) {
return left;
}
}
if (current.right != null) {
MerkleNode right = findNode(current.right, value);
if (right != null) {
return right;
}
}
return null;
}
}
public static MerkleTree createTreeFromList(List<byte[]> leaves) {
List<MerkleNode> leavesAsNodes = leaves.stream().map(MerkleNode::new).collect(Collectors.toList());
MerkleNode root = createRootFromNodeList(leavesAsNodes);
return new MerkleTree(root);
}
private static MerkleNode createRootFromNodeList(List<MerkleNode> leaves) {
List<MerkleNode> parents = new ArrayList<>();
for (int i=0; i<leaves.size(); i+=2) {
if (leaves.size() < (i+2)) {
parents.add(new MerkleNode(leaves.get(i), new MerkleNode(new byte[]{})));
} else {
parents.add(new MerkleNode(leaves.get(i), leaves.get(i+1)));
}
}
if (parents.size() <= 1) {
return (parents.size() == 0) ? null : parents.get(0);
} else {
return createRootFromNodeList(parents);
}
}
}
package tech.blockchainers.crypyapi.http.common;
import org.junit.Assert;
import org.junit.jupiter.api.Test;
import org.web3j.crypto.Hash;
import org.web3j.utils.Numeric;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
public class MerkleTreeTest {
@Test
public void printSampleMarkleTree() {
MerkleTree tree = getSampleMerkleTree();
new BinaryTreePrinter(tree).print(System.out);
}
@Test
public void getMerkleTreeProofPath() {
MerkleTree tree = getSampleMerkleTree();
new BinaryTreePrinter(tree).print(System.out);
MerkleTree.MerkleNode nodeNo7 = MerkleTree.findNode(tree.root, Hash.sha256(BigInteger.valueOf((long) 7).toByteArray()));
//System.out.println("\n" + nodeNo7);
System.out.println(nodeNo7.proofPath());
}
@Test
public void validateMerkleTreeProofPath() {
MerkleTree tree = getSampleMerkleTree();
new BinaryTreePrinter(tree).print(System.out);
MerkleTree.MerkleNode nodeNo7 = MerkleTree.findNode(tree.root, Hash.sha256(BigInteger.valueOf((long) 100).toByteArray()));
//System.out.println("\n" + nodeNo7);
List<MerkleTree.ProofPathElement> proofPath = nodeNo7.proofPath();
Assert.true(MerkleTree.MerkleNode.validateProofPath(nodeNo7, tree.root, proofPath));
}
private MerkleTree getSampleMerkleTree() {
List<byte[]> nums = new ArrayList<>();
for (int i=0; i<100000; i++) {
nums.add(Hash.sha256(BigInteger.valueOf((long)i).toByteArray()));
}
MerkleTree merkleTree = MerkleTree.createTreeFromList(nums);
return merkleTree;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment