Demonstrate Merkle trees by "Merklizing" the words of a sentence supplied as command line arguments

merkle.groovy

#!/usr/local/bin/groovy

/*
 * Demonstrate Merkle trees by "Merklizing" the words of a sentence supplied as command line arguments
 * Example: merkle The dog jumped over the moon
 */

HASHPREFIXLEN = 8

static byte[] hash(List<byte[]> input) {
    java.security.MessageDigest.getInstance("SHA-256").with {
        input.each{update(it)}
        digest()
    }
}

// Recursively hash pairs of elements to produce Merkle tree levels
// Returns the full tree, one array for each descending level
List<List<byte[]>> reduce(List<byte[]> hashes) {
    def nullHash = new byte[32]
    (hashes.size < 2) ? [hashes] : {
        def even = (hashes.size % 2) ? hashes + nullHash : hashes
        def reduced = even.collate(2).collect { hash(it) }

        [even] + reduce(reduced)
    }()
}

// Create Merkle tree structure for a set of input strings (sentence)
List<List<byte[]>> merklize(String... strings) {
    def hashes = strings.collect { hash([it.bytes]) }
    reduce(hashes)
}

void printMerkle(List<List<String>> levels) {
    def maxColWidth = levels.flatten().collect{ it.length() }.max() + 2
    def firstWidth = maxColWidth * levels.first().size()
    def treeWidth = maxColWidth * levels.tail().collect{ it.size() }.max()

    def printRow = { row, rowWidth ->
        def colWidth = rowWidth / row.size()
        row.eachWithIndex { n, i ->
            def fieldWidth = Math.round((i + 1) * colWidth) - Math.round(i * colWidth)
            print n.center(fieldWidth)
        }
        println()
    }

    println()
    printRow(levels.first(), firstWidth)
    printRow(levels.first().collect{ "|"}, firstWidth)
    printRow(levels.tail().first(), treeWidth)
    levels.tail().tail().each{
        printRow(it.collect{ "\\    /"}, treeWidth)
        printRow(it, treeWidth)
    }
}

merklized = merklize(args).collectNested { it.encodeHex().toString().take(HASHPREFIXLEN) }

printMerkle([args.toList()] + merklized)