Merkle tree in functional style

Merkle trees are typically implemented as binary trees where each non-leaf node is a hash of the two nodes below it.
The leaves can either be the data itself or a hash/signature of the data.

API

The whole picture:

  import com.github.merkle.conversion.Conversion._
  
  // Anything convertible to a sequence of bytes, e.g. protobuf/avro/parquet 
  val leaf1 = leaf("1", "MD5")
  val leaf2 = "c81e728d9d4c2f636f067f89cc14862c"
  val leaf3 = "3" getBytes
  val leaf4 = Array[Byte](59, 66, 1, 55) 
    
  val leafs: Seq[BlockView] = Seq(leaf1, leaf2, leaf3, leaf4)
  
  val tree = MerkleTree(leafs, "MD5")
  TreeTraverse.inorderRecursive(tree)
  val root = tree.rootHash

Convenient API for leafs:

• Hashes:

    val hashLeaf = "c81e728d9d4c2f636f067f89cc14862c"

• String with digest:

    val stringWithDigest = leaf("1", "MD5")

• Bytes + postfix notation:

    val bytes1 = "3".getBytes()
    val bytes2 = "3" getBytes
    val bytes3 = Array[Byte](59, 66, 1, 55)

• Anything which can be converted to bytes with twitter bijection, for example:

• thrift/protobuf/avro

• GZippedBytes / GZippedBase64String

• Base64String

• java.nio.ByteBuffer

Overview

Merkle trees are typically implemented as binary trees where each non-leaf node is a hash of the two nodes below it. The leaves can either be the data itself or a hash/signature of the data.

Merkle trees is often used in distributed systems for file integrity/verification purposes:

• Databases: Apache Cassandra, Amazon Dynamo DB, Riak

• Cryptocurrencis: Bitcoin, Ethereum (modified Merkle tree)

• VCS: Git, Mercurial

• File systems: IPFS, Btrfs, ZFS

• And other: Apache Wave (previously Google Wave)