We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies.

We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies. Less

We use cookies and other tracking technologies... More

Login or register
to apply for this job!

Login or register
to publish this job!

Login or register
to save this job!

Login or register
to save interesting jobs!

Login or register
to get access to all your job applications!

Login or register to start contributing with an article!

Login or register
to see more jobs from this company!

Login or register
to boost this post!

Show some love to the author of this blog by giving their post some rocket fuel 🚀.

Login or register to search for your ideal job!

Login or register to start working on this issue!

Login or register
to save articles!

Engineers who find a new job through Blockchain Works average a 15% increase in salary 🚀

Blog hero image

Grokking Merkle Tree

John Ferrolino 3 March, 2021 | 4 min read

Grokking Merkle Trees in Scala

There are quite a few literatures that talk about this data structure by people who, the same as I, came from their early introduction to the blockchain technology and bitcoin.

This article is not trying to replicate the effort as some posts were in-depth in their walkthrough on the usage and importance of Merkle Tree in the blockchain space and other use cases. This is the reference I used that inspired me to write this article.

In this post, we will write an implementation of this data structure using the Scala language. The approach I will take is first to first a)define the data types then (b)implement the algorithm for Merkle tree. The simplest representative of this data structure is a binary tree where the input data are used to generate our leaf nodes that contain the cryptographic hash of a dataset which will continue iterating to create branches until it reaches the last node that we will call the root.

Abstract Data Types

We will define the Node as a trait where other types will refer from. It will contain a type parameter that represents the data type of the hash value which is typically be represented as an Array[Byte].

trait Node[T] {
 val hash: T
}

The structure of the tree is composed of:

  • a Leaf which is a node that does not have any children nodes and stores the hashed value of the input data.
    case class Leaf[T](datum: T) extends Node[T]{
    	override val hash: T = ???
    }
    
  • a Branch which is the node that is produced as a product of the hash value of its children nodes.
    case class Branch[T](left: Node[T], right: Option[Node[T]]) 	extends Node[T] {
    		override val hash: T = ???
    }
    

As seen above, we are missing the computation for producing the hash value. We needed to provide the mechanism to generate this hash value through defining the hash function. We will then add another parameter in the case class definition written above with this:

(implicit hashFn: (T, Option[T]) => T)

This will be used both on the Leaf and Branch nodes whilst the second value parameter in the function literal is left optional.

To complete the definition, let us rewrite them and add the logic for the computation as follows:

case class Leaf[T](datum: T)(implicit hashFn: (T, Option[T]) => T extends Node[T] {
	override val hash: T = hashFn(datum, None)
}

case class Branch[T](left: T, right: Option[Node[T]])(implicit hashFn: (T, Option[T]) => T) extends Node[T]{
	override val hash: T = hashFn(left.hash, right.flatMap(r => Some(r.hash))
}

We now have completed the abstract data types for this data structure. The other remaining thing to do is to work on writing the algorithm for our Merkle Tree.

Join our newsletter
Join over 111,000 others and get access to exclusive content, job opportunities and more!

Implementing the Merkle Tree

The merkle tree will be defined as a class with a companion object to hold the construction of the tree.

class MerkleTree[T](val root: Node[T])

The gist of the algorithm will be written in its companion object. It will be composed of two parts:

  • the constructor that accepts the input data of some type T and generates the leaf nodes that will store the hash value of the input data.
    object MerkleTree {
    	def apply[T](data: Seq[T])(implicit hashFn: (T,Option[T]) => T): MerkleTree[T] = ???
    ...
    }
    
  • - the recursive method that will keep on creating branches until a single node is left. This node will represent the root of the Merkle tree.
    object MerkleTree {
    ...
    	def build[T](nodes: Seq[Node[T]])(implicit hashFn: (T, Option[T]) => T): MerkleTree[T] = ???
    }
    

We also need an outlet to plug in our function for generating the hash for our inputs which will then be used in the data types.

Define our constructor, apply

When creating an instance of the Merkle tree, the apply method will be called. It requires data as input which is typically an array of bytes.

The apply method will use those input data to generate our leaf nodes which will store the hash content. It will look something like below:

	def apply[T](data: Seq[T])(implicit hashFn: (T, Option[T]) => T): MerkleTree = {
	val withLeaves = data.map(Leaf(_))
	build(withLeaves)
}

After generating the leaves, it will then pass this to build which will complete the construction of the Merkle tree.

Create our tree with the build method

The build method completes the creation of our Merkle Tree where it will recursively call itself until a single node is left, the root.

Whilst in the process, the sequence of nodes are paired from leaves and internal nodes (i.e. branch) to instantiate our Branch case class. The pair serves as an input to our branch to represent either the left or an optional right node.

	def build[T](nodes: Seq[Node[T]])(implicit hashFn: (T, Optional[T]) => T): MerkleTree = {
	if(nodes.length == 1) new MerkleTree[T](nodes.head)
	else {
		val withBranches = nodes.grouped(2).map {
			case Seq(l,r) => Branch(l, Some(r))
			case Seq(a) => Branch(a, None)
		}.toSeq
		build(withBranches)
	}
}

How to use it?

The first thing to do is to define our cryptographic hash function implementation. For this, we will use the built-in MessageDigest utility available in the jdk with SHA-256 encoding.

This function literal will be used and injected to the classes and methods that require it. One way of writing it will look like as follows:

	implicit val hashFn: (Array[Byte], Option[Array[Byte]])=> Array[Byte] = (byteArr, opt) => {
		val cc = opt match {
			case None => byteArr
			case _ => byteArr ++ opt.get
		}
java.security.MessageDigest.getInstance("SHA-256").digest(cc)
		}

To prepare, we can define a sequence of string as inputs. Since our hashFn expects an input of Array[Byte], we need to convert each items to its bytes equivalent.

It will be written as shown below.

val inputs = Seq("trans01", "trans02", "trans03").map(_.getBytes)

val tree = MerkleTree(inputs)

For more details on how to use this, visit the test spec.

You can also find the source code for this article at this github link

What's next?

So far, we only built a data structure in the most simplest way we could. This will help us understand the components being used as well as the algorithm to complete it. This is a good introduction to understanding the Merkle tree but far enough for practical use.

A follow up article(s) will ensue on topics for applying Merkle proofs and further improvements.

Author's avatar
John Ferrolino
Functional programmer
    Scala
    event sourcing
    Functional Programming
    Solidity
    DAML
    Haskell

Related Issues

cosmos / gaia
  • Started
  • 0
  • 4
  • Intermediate
  • Go
cosmos / gaia
  • Started
  • 0
  • 3
  • Intermediate
  • Go
cosmos / ibc
  • Open
  • 0
  • 0
  • Intermediate
  • TeX
cosmos / ibc
cosmos / ibc
  • Started
  • 0
  • 1
  • Intermediate
  • TeX
viebel / klipse-clj
viebel / klipse-clj
  • Started
  • 0
  • 4
  • Intermediate
  • Clojure
viebel / klipse
  • Started
  • 0
  • 1
  • Intermediate
  • Clojure
viebel / klipse
  • 1
  • 2
  • Intermediate
  • Clojure
viebel / klipse
  • Started
  • 0
  • 4
  • Intermediate
  • Clojure
  • $80

Get hired!

Sign up now and apply for roles at companies that interest you.

Engineers who find a new job through Blockchain Works average a 15% increase in salary.

Start with GitHubStart with Stack OverflowStart with Email