# Discussion

I just started learning about Merkle Trees and wanted to get some practice by attempting to implement a very simple Merkle Tree.

The constructor for the tree takes some type of hash function, and an array of byte[] values that represent the "leaf" node values.

I construct a tree by first hashing the leaf node values, combining the hashed node values 2 at a time (if possible), and constructing new node values from the combined hashed node values. I continue this process, until I have a single root node.

# Implementation

public class SimpleMerkleTree {
public static class Node {
private final Node left;
private final Node right;
private final byte[] value;

public Node(final Node left, final Node right, final byte[] value) {
this.left = left;
this.right = right;
this.value = value;
}

public Node getLeft() {
return left;
}

public Node getRight() {
return right;
}

public byte[] getValue() {
return Arrays.copyOf(value, value.length);
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return Objects.equals(left, node.left) && Objects.equals(right, node.right) && Arrays.equals(value, node.value);
}

@Override
public int hashCode() {
int result = Objects.hash(left, right);
result = 31 * result + Arrays.hashCode(value);
return result;
}
}

private final Node root;

public SimpleMerkleTree(final Function<byte[], byte[]> hashFunction, final byte[][] values) {
if (0 == values.length) {
throw new IllegalArgumentException("Must specify at least one value");
}

List<Node> currentLevel = Stream.of(values)
.map(hashFunction)
.map(hash -> new Node(null, null, hash))
.collect(Collectors.toList());

while (1 < currentLevel.size()) {
final List<Node> nextLevel = new ArrayList<>();

for (int nodeIndex = 0; nodeIndex < currentLevel.size(); nodeIndex += 2) {
final Node firstNode = currentLevel.get(nodeIndex);

if (currentLevel.size() - 1 == nodeIndex) {
} else {
final Node secondNode = currentLevel.get(1 + nodeIndex);

new Node(
firstNode,
secondNode,
hashFunction.apply(concatenate(firstNode.value, secondNode.value))
)
);
}
}

currentLevel = nextLevel;
}

this.root = currentLevel.get(0);
}

public Node getRoot() {
return root;
}

private static byte[] concatenate(final byte[] first, final byte[] second) {
final int firstLength = first.length;
final int secondLength = second.length;
final byte[] concatenated = new byte[firstLength + secondLength];
System.arraycopy(first, 0, concatenated, 0, firstLength);
System.arraycopy(second, 0, concatenated, firstLength, secondLength);

return concatenated;
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
SimpleMerkleTree that = (SimpleMerkleTree) o;
return Objects.equals(root, that.root);
}

@Override
public int hashCode() {
return Objects.hash(root);
}
}