MerkleTreeBuilder.java

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);

    }
}