Simple Merkle Tree

Question

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) {
                    nextLevel.add(new Node(firstNode, null, firstNode.value));
                } else {
                    final Node secondNode = currentLevel.get(1 + nodeIndex);

                    nextLevel.add(
                            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);
    }
}