A Clojure Merkle tree utilizing SHA-256.

merkle.tree.clj

(ns merkle.tree
  (:import [java.security MessageDigest]))

(defn sha-256-digest [bs]
  (.digest
    (doto (MessageDigest/getInstance "SHA-256")
      (.update bs))))

(def double-sha-256 (comp sha-256-digest sha-256-digest))

(defn node
  "Given a label and optionally a left and right node, returns a list
  representing a node in a binary tree."
  ([label]
   (node label nil nil))
  ([label left right]
   (cons label (list left right))))

(defn tree-levels
  "Given a previous level, constructs the next level until it reaches a root."
  [previous]
  (let [level
        (->> previous
             (partition 2)
             (map (fn [[left right]]
                    (let [combined-hash
                          (->> (map first [left right])
                               (mapcat seq)
                               byte-array
                               double-sha-256)]
                      (node combined-hash left right)))))]
    (if (= (count level) 1)
      level
      (lazy-cat (tree-levels level) level))))

(defn tree
  "Given a collection, constructs a Merkle tree using doubled SHA-256. The tree
  is represented as a list of nodes. See `node`."
  ([coll]
   (tree coll (fn [c] (.getBytes (str c)))))
  ([coll get-bytes]
   ;; Construct the leaf nodes and pass them into the `tree-levels` function.
   (->>
     (if (even? (count coll))
       coll
       (conj coll (last coll)))
     (map get-bytes)
     (map double-sha-256)
     (map node)
     tree-levels)))

(comment
  (tree (into [] "foo")))