Repository files navigation

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.

The whole picture:

importcom.github.merkle.conversion.Conversion._// Anything convertible to a sequence of bytes, e.g. protobuf/avro/parquetvalleaf1= leaf("1","MD5")valleaf2="c81e728d9d4c2f636f067f89cc14862c"valleaf3="3" getBytesvalleaf4=Array[Byte](59,66,1,55)valleafs:Seq[BlockView]=Seq(leaf1, leaf2, leaf3, leaf4)valtree=MerkleTree(leafs,"MD5")TreeTraverse.inorderRecursive(tree)valroot= tree.rootHash

Convenient API for leafs:

• Hashes:

valhashLeaf="c81e728d9d4c2f636f067f89cc14862c"

• String with digest:

valstringWithDigest= leaf("1","MD5")

• Bytes + postfix notation:

valbytes1="3".getBytes()valbytes2="3" getBytesvalbytes3=Array[Byte](59,66,1,55)

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

• thrift/protobuf/avro

• GZippedBytes /GZippedBase64String

• Base64String

• java.nio.ByteBuffer

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)