This is the second part of the Blockchain mini-series. Core focus of this post is to define the building “block” of a blockchain and illustrate how to “mine” a block in Scala.

First, let’s make available the key entity classes (Account, Transactions, MerkleTree, etc) and utility/crypto functions we assembled in the previous post.

// -- Utility functions ------

import java.time.{Instant, LocalDateTime, ZoneId}
import java.time.format.DateTimeFormatter

object Util {
  def bytesToBase64(bytes: Array[Byte]): String =
    java.util.Base64.getEncoder.encodeToString(bytes)

  def base64ToBytes(base64: String): Array[Byte] =
    java.util.Base64.getDecoder.decode(base64)

  def longToBytes(num: Long): Array[Byte] =
    java.nio.ByteBuffer.allocate(8).putLong(num).array

  def timestampToDateTime(timestamp: Long, zone: String = "UTC"): String =
    DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss").format(
        LocalDateTime.ofInstant(Instant.ofEpochMilli(timestamp), ZoneId.of(zone))
      )
}

import Util._

// -- Crypto functions ------

import scala.util.{Try, Success, Failure}
import java.io.{OutputStreamWriter, FileOutputStream, IOException}
import java.security.spec.X509EncodedKeySpec
import java.security._
import org.apache.commons.codec.binary.Base64
import org.bouncycastle.jce.provider.BouncyCastleProvider
import org.bouncycastle.util.io.pem.{PemObject, PemWriter}

object Crypto {
  def sha256(byteArr: Array[Byte]): Array[Byte] =
    java.security.MessageDigest.getInstance("SHA-256").digest(byteArr)

  val hashFcn = sha256 _

  def generateKeyPair(keySize: Int = 4096): KeyPair = {
    val generator = java.security.KeyPairGenerator.getInstance("RSA")
    generator.initialize(keySize)
    generator.genKeyPair
  }

  def writePemFile(key: Key, description: String, filename: String): Unit = {
    val pemObject = new PemObject(description, key.getEncoded())
    val pemWriter = new PemWriter(new OutputStreamWriter(new FileOutputStream(filename)))

    try {
      pemWriter.writeObject(pemObject)
    } catch {
      case e: IOException => println("ERROR: IO Exception $e")
    } finally {
      pemWriter.close()
    }
  }

  def generateKeyPairPemFiles(filePrefix: String, keySize: Int = 4096): Unit = {
    Security.addProvider(new BouncyCastleProvider())

    val generator = KeyPairGenerator.getInstance("RSA")
    generator.initialize(keySize)
    val keyPair = generator.generateKeyPair()

    writePemFile(keyPair.getPublic(), "RSA PUBLIC KEY", s"${filePrefix}_public.pem")
    writePemFile(keyPair.getPrivate(), "RSA PRIVATE KEY", s"${filePrefix}_private.pem")
  }

  def publicKeyFromPemFile(keyFile: String): Option[PublicKey] = {
    Try(scala.io.Source.fromFile(keyFile)) match {
      case Success(k) =>
        val keyString = k.mkString.
          replace("-----BEGIN RSA PUBLIC KEY-----\n", "").
          replace("-----END RSA PUBLIC KEY-----\n", "")
        val keyBytes = Base64.decodeBase64(keyString)
        val publicKey = KeyFactory.getInstance("RSA").generatePublic(new X509EncodedKeySpec(keyBytes))
        Some(publicKey)
      case Failure(e) =>
        None
    }
  }

  def publicKeyToBase64(publicKey: PublicKey): String =
    bytesToBase64(publicKey.getEncoded)
}

import Crypto._

// -- Account ------

case class Account(key: String, name: String) {
  override def toString: String =
    s"A(${key.substring(0,2)}*${key.substring(128,132)}*, $name)"
}

object Account {
  def fromKeyFile(keyFile: String, name: String): Account =
    publicKeyFromPemFile(keyFile) match {
      case Some(key) =>
        new Account(publicKeyToBase64(key), name)
      case None =>
        throw new Exception(s"ERROR: Problem loading $keyFile!")
    }
}

// -- Transactions ------

case class TransactionItem(id: String, accountFrom: Account, accountTo: Account, amount: Long, timestamp: Long) {

  override def toString: String = {
    val datetime = timestampToDateTime(timestamp)
    s"TI(${id.substring(0, 4)}, ${accountFrom.name} -> ${accountTo.name}, ${amount}, ${datetime})"
  }
}

object TransactionItem {
  def apply(accountFrom: Account, accountTo: Account, amount: Long, timestamp: Long): TransactionItem = {
    val bytes = accountFrom.key.getBytes ++ accountTo.key.getBytes ++ longToBytes(amount) ++ longToBytes(timestamp)
    new TransactionItem(bytesToBase64(hashFcn(bytes)), accountFrom, accountTo, amount, timestamp)
  }
}

import java.util.UUID.randomUUID

case class Transactions(id: String, items: Array[TransactionItem], timestamp: Long) {
  override def toString: String = {
    val datetime = timestampToDateTime(timestamp)
    s"T(${id.substring(0, 4)}, ${items.map(_.amount).sum}/${items.size}, ${datetime})"
  }
}

object Transactions {
  def apply(transactions: Array[TransactionItem], timestamp: Long): Transactions =
    new Transactions(randomUUID.toString, transactions, timestamp)
}

// -- MerkleTree ----

class MerkleTree(
    val hash: Array[Byte],
    val left: Option[MerkleTree] = None,
    val right: Option[MerkleTree] = None
  ) extends Serializable {

  override def toString: String = s"MT(${bytesToBase64(hash).substring(0, 4)})"
}

object MerkleTree {
  def apply(data: Array[Array[Byte]]): MerkleTree = {
    @scala.annotation.tailrec
    def buildTree(nodes: Array[MerkleTree]): Array[MerkleTree] = nodes match {
      case ns if ns.size <= 1 =>
        ns
      case ns =>
        val pairedNodes = ns.grouped(2).map{
          case Array(a, b) => new MerkleTree(hashFcn(a.hash ++ b.hash), Some(a), Some(b))
          case Array(a)    => new MerkleTree(hashFcn(a.hash), Some(a), None)
        }.toArray
        buildTree(pairedNodes)
    }

    if (data.isEmpty)
      new MerkleTree(hashFcn(Array.empty[Byte]))
    else {
      val nodes = data.map(byteArr => new MerkleTree(hashFcn(byteArr)))
      buildTree(nodes)(0)  // Return root of the tree
    }
  }
}

The building “block” of a Blockchain

We now define the building “block” of a blockchain. In our simple model, it’s a “reversed” linked list with each node consisting of the hash value of its preceding block. Key fields in the Block class include the hash values of the current and preceding blocks, the transaction collection and the corresponding Merkle root, block creation timestamp and a couple of fields for Proof of Work (PoW) – a consensus algorithm we’ll get into shortly.

Let’s define object ProofOfWork, which includes just a couple of values relevant to the PoW process, as follows for now:

object ProofOfWork {
  val defaultDifficulty: Int = 3  // Level of difficulty of the PoW process
  val defaultNonce: Long = 0L     // An integer to be monotonically incremented in the PoW process
  // Other fields and methods ...
}

sealed trait Block {
  def hash: Array[Byte]
  def hashPrev: Array[Byte]
  def merkleRoot: MerkleTree
  def transactions: Transactions
  def timestamp: Long
  def difficulty: Int
  def nonce: Long
  def length: Int

  override def toString: String = {
    val datetime = timestampToDateTime(timestamp)
    val transInfo = s"T(${transactions.id.substring(0, 4)}, ${transactions.items.map(_.amount).sum}/${transactions.items.size})"
    s"BLK(${bytesToBase64(hash).substring(0, 4)}, ${transInfo}, ${datetime}, ${difficulty}, ${nonce})"
  }
}

case object RootBlock extends Block {
  def hash = hashFcn(merkleRoot.hash ++ hashPrev ++ longToBytes(timestamp))
  def hashPrev = Array.empty[Byte]
  def merkleRoot = MerkleTree(Array.empty[Array[Byte]])
  def transactions = new Transactions("----", Array.empty[TransactionItem], 0L)
  def timestamp = 0L
  def difficulty = 0
  def nonce = 0L
  def length = 1
  def hasValidHash: Boolean = (hash sameElements RootBlock.hash) && hashPrev.isEmpty
  def hasValidMerkleRoot: Boolean = merkleRoot.hash sameElements MerkleTree(Array.empty[Array[Byte]]).hash
}

case class LinkedBlock(
    hash: Array[Byte],
    hashPrev: Array[Byte],
    blockPrev: Block,
    merkleRoot: MerkleTree,
    transactions: Transactions,
    timestamp: Long,
    difficulty: Int = ProofOfWork.defaultDifficulty,
    nonce: Long = ProofOfWork.defaultNonce
  ) extends Block {

  def length: Int = {
    @scala.annotation.tailrec
    def loop(blk: Block, len: Int): Int = blk match {
      case RootBlock => len
      case b: LinkedBlock => loop(b.blockPrev, len + 1)
    }
    loop(this, 1)
  }
}

object LinkedBlock {
  def apply(
      blockPrev: Block,
      transactions: Transactions,
      timestamp: Long
    ): LinkedBlock = {
    val mRoot = MerkleTree(transactions.items.map(_.id.getBytes))
    new LinkedBlock(
      hash = hashFcn(mRoot.hash ++ blockPrev.hash ++ longToBytes(timestamp)),
      hashPrev = blockPrev.hash,
      blockPrev = blockPrev,
      merkleRoot = mRoot,
      transactions = transactions,
      timestamp = timestamp
    )
  }
}

RootBlock is the primordial block (a.k.a. genesis block) and any subsequent block chained after it is a LinkedBlock which consists of an additional field blockPrev, a “pointer” to the preceding block. For simplicity in function signatures, the hash function `hashFcn` for the Block subclasses and other previously defined classes is not provided as constructor or class method arguments but rather a predefined function for all.

Proof of Work – a computationally demanding task

Proof of Work (PoW) is a kind of consensus algorithms, arguably popularized by Bitcoin. Due to the lack of a centralized authoritative source like the central bank for a conventional currency, a decentralized cryptocurrency network needs a consensus protocol that every participant agrees to.

The idea of PoW is to incentivize participants to work on a computationally demanding task in order to be qualified for adding a new block of unspent transactions to the existing blockchain – the distributed ledger. The incentive is a reward, typically a specific amount of the cryptocurrency, the network offers to the participants who:

1. completed the task, and,
2. successfully added to the blockchain a new block consisting of the task completion proof.

These participants are referred to as the `miners`. The copy of blockchain maintained by any competing miner with the highest PoW value (generally referred to the length of the blockchain) overrides the rest.

A commonly employed PoW scheme is to require a miner to repeatedly apply a hash function to a given string of text combined with an incrementing integer until the resulting hash value has a certain number of leading zeros. Mathematically this is a task requiring exponentially more trials for every additional zero in the requirement.

We now expand object ProofOfWork to include all the key elements for PoW.

object ProofOfWork {
  val defaultDifficulty: Int = 3
  val defaultNonce: Long = 0L
  val defaultReward: Long = 99L   // Reward that goes to the miner's account

  val networkAccount: Account = new Account(
      key = "MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEApKyCqvNjx+YfVYFippxviV0UgEgpYJbV0luEJTkcbnvIIolqXR5JJACbk8TDW72F9pnwKqQhM0vzpsbat+kubl5FeO0CPk/Gk2/aAcoP11DNqYAgqvCKEyZlJFmwnC/6JecCBdBb+G/+v894LESD8y4upjZIRdrrC4UQowlm4+6mPJTbB0U+2q7rwv8FXmR9KHmRxtGoMh885bKTXwqOO0pqh0/MMSaW5pzS6s5bUiX7ekl0EPwTyiXbuyUZ3nZcpm/v7lCvXWlyRju8g2pg9e0BShyfI7w1qqw1xEeRVwU1qIlN4Q1bz82t1O+7l308VtiXH2lM9Vhn+Sfz68cjtmJ4uSwZKeV91kaOJdr1OafM9ryfPv2MGDVvSGUk+TEMORysFcRS59VsON8styFJ6hGx1/GKyfUilCS2G2dS/9NvTJjV64nPTQ1mufT4Kd8tBa3/DTmjrqsFjfzYsc/kVz0QsGN7PxgKPf5+aSzrG2y9GQy69jAb6wpMoLcux2zlZvobYR+qjoBIsn+5Y5J0Fs9Jvwh0yd0KGdaDkMZnPGYTQo1vpC4gqowt7q4lba0FRV3jt/bm1B8Pu+YWk4MasNk1wfBMLNOr1CGaiSXFIl0NyATViOOyq6FEnHdF8L1MmLM9v7Yj3l4q5ykF0u/JnDXErC7CwtECRVr6gX3LWfcCAwEAAQ==",
      name = "blockchain"
    )

  def generateProof(base64: String, difficulty: Int, nonce: Long): Long = {
    @scala.annotation.tailrec
    def loop(bytes: Array[Byte], n: Long): Long =
      if (validProof(bytes, difficulty, n)) n else loop(bytes, n + 1)

    loop(base64ToBytes(base64), nonce)
  }

  def validProof(bytes: Array[Byte], difficulty: Int, nonce: Long): Boolean =
    hashFcn(bytes ++ longToBytes(nonce)).take(difficulty).forall(_ == 0)

  def validProofIn(block: Block): Boolean = block match {
    case _: LinkedBlock =>
      (block.difficulty >= defaultDifficulty) &&
        validProof(block.hash, block.difficulty, block.nonce)
    case RootBlock =>
      false
  }
}

Borrowing some terms from the Bitcoin model, `defaultDifficulty` is the default difficulty level of the PoW task. The level value represents the number of leading zeros required to be in the resulting hash value after repeatedly applying a hash function against the concatenation of the hash of a block and a monotonically increasing integer. The incremental integer is called `nonce`, and `defaultNonce` is the network-default value. Note that, by design, the output of hashing is so unpredictable and sensitive to input change that any given starting nonce value will not have any advantage over any other values.

Method `validProof` concatenates a dataset of type byte-array and a byte-converted `nonce`, applies `hashFcn` to the combined data and reports whether the resulting hash value has the number of leading zeros specified by `difficulty`. And method `generateProof` is a simple recursive snippet that takes a Base64 string and runs `validProof` repeatedly with an monotonically incrementing `nonce` until it satisfies the difficulty requirement.

Generating Proof

Through repeated trials of hashing with the incrementing nonce value, the “proof” is the first incremented nonce value that satisfies the requirement at the set difficulty level. As it could take significant time to arrive at the required hash value, it’s logical to perform PoW asynchronously.

import scala.concurrent.{ExecutionContext, Future, Promise, TimeoutException, Await}
import scala.concurrent.duration._
import scala.util.Try

import akka.actor.ActorSystem

implicit val system = ActorSystem("blockchain")
implicit val ec = system.dispatcher
implicit val timeout = 20.seconds

def generatePoW(block: Block)(implicit ec: ExecutionContext, timeout: FiniteDuration): Future[Long] = {
  val promise = Promise[Long]()

  system.scheduler.scheduleOnce(timeout){ promise tryFailure new TimeoutException(s"$block: $timeout") }

  Future{
    Try{
      val incrementedNonce =
        ProofOfWork.generateProof(
            bytesToBase64(block.hash),
            ProofOfWork.defaultDifficulty,
            ProofOfWork.defaultNonce
          )
      promise success incrementedNonce
    }.
    recover{
      case e: Exception => promise failure e
    }
  }
  promise.future
}

Using the `scheduleOnce` Akka scheduler to complete a `Promise` with a `TimeoutException` after a certain elapsed time, we’ve created an asynchronous method with a non-blocking timeout mechanism (as opposed to `Await`) that returns a Future of the wanted nonce value.

Test running generatePoW

To test out generating Proof of Work, we borrow the random account/transaction creation snippet from the previous blog:

val numOfAccounts = 5
val maxTransItems = 3
val keyPath = "/tmp/"

def randomFcn = java.util.concurrent.ThreadLocalRandom.current

def distinctRandomIntPair(lower: Int, upper: Int): List[Int] = {
  val rand1 = randomFcn.nextInt(lower, upper)
  val rand2 = randomFcn.nextInt(lower, upper)
  if (rand1 != rand2)
    List(rand1, rand2)
  else
    List(rand1, if (rand2 < upper - 1) rand2 + 1 else lower)
}

def generateTrans(
    numOfAccounts: Int,
    maxTransItems: Int,
    keyPath: String,
    keyFiles: List[String]
  ): Transactions = {

  def genTransItem: TransactionItem = {
    val idx = distinctRandomIntPair(0, numOfAccounts)
    val accountFrom = Account.fromKeyFile(s"${keyPath}${keyFiles(idx(0))}", s"User${idx(0)}")
    val accountTo = Account.fromKeyFile(s"${keyPath}${keyFiles(idx(1))}", s"User${idx(1)}")
    val amount = 1000L + randomFcn.nextInt(0, 5) * 500L

    val transItem = TransactionItem(accountFrom, accountTo, amount, System.currentTimeMillis)

    println(s"accountFrom: $accountFrom  accountTo: $accountTo")
    println(s"TransactionItem: $transItem")

    transItem
  }

  val numOfTransItems = randomFcn.nextInt(1, maxTransItems + 1)
  val transItems = Array.tabulate(numOfTransItems)(_ => genTransItem)

  Transactions(transItems, System.currentTimeMillis)
}

Generating a few Transactions objects with random content, each to be used in building a block:

(0 until numOfAccounts).foreach(i => generateKeyPairPemFiles(s"${keyPath}account${i}"))

val keyFiles = List.tabulate(numOfAccounts)(i => s"account${i}_public.pem")

val trans1 = generateTrans(numOfAccounts, maxTransItems, keyPath, keyFiles)
// accountFrom: A(MI*3SG5*, User3)  accountTo: A(MI*Qpgs*, User4)
// TransactionItem: TI(DnrJ, User3 -> User4, 2500, 2020-03-26 10:17:28)
// accountFrom: A(MI*Qpgs*, User4)  accountTo: A(MI*4REy*, User0)
// TransactionItem: TI(z8JF, User4 -> User0, 2000, 2020-03-26 10:17:28)
// trans1: Transactions = T(b2ce, 4500/2, 2020-03-26 10:17:28)

val trans2 = generateTrans(numOfAccounts, maxTransItems, keyPath, keyFiles)
// accountFrom: A(MI*rlVg*, User2)  accountTo: A(MI*Qpgs*, User4)
// TransactionItem: TI(xoFr, User2 -> User4, 3000, 2020-03-26 10:17:52)
// accountFrom: A(MI*kOJv*, User1)  accountTo: A(MI*Qpgs*, User4)
// TransactionItem: TI(TTdY, User1 -> User4, 2500, 2020-03-26 10:17:52)
// trans2: Transactions = T(30cf, 5500/2, 2020-03-26 10:17:52)

val trans3 = generateTrans(numOfAccounts, maxTransItems, keyPath, keyFiles)
// accountFrom: A(MI*rlVg*, User2)  accountTo: A(MI*4REy*, User0)
// TransactionItem: TI(3Ix3, User2 -> User0, 3000, 2020-03-26 10:18:04)
// trans3: Transactions = T(2e69, 3000/1, 2020-03-26 10:18:04)

The miner will use their own account to receive the blockchain reward upon successful block acceptance. Creating a new block requires a couple of things:

• the reference to the last block in the existing blockchain
• a collection of unspent transactions from a distributed queue

The miner will then save the last block reference as `blockPrev` in the new block, prepend to the transaction collection an additional transaction with their own account reference for the reward, and start the PoW process. Upon finishing the PoW, the incremented nonce that satisfies the requirement at the predefined difficulty level will be kept in the new block as the proof for validation by the blockchain system. Below is the method `mine` that creates the new block.

def mine(minerAccount: Account, blockPrev: Block, trans: Transactions): Future[Block] = {
  val newTransItem = TransactionItem(
      ProofOfWork.networkAccount,
      new Account(minerAccount.key, "miner"),
      ProofOfWork.defaultReward,
      System.currentTimeMillis
    )
  val newTrans = new Transactions(trans.id, newTransItem +: trans.items, System.currentTimeMillis)
  val newBlock = LinkedBlock(blockPrev, newTrans, System.currentTimeMillis)

  generatePoW(newBlock).
    map(newNonce => newBlock.copy(nonce = newNonce)).
    recover{ case e: Exception => throw new Exception(e) }
}

Let’s just say the miner owns the first of the previously created accounts:

val minerAccount = Account.fromKeyFile(s"${keyPath}${keyFiles(0)}", s"User0")
// minerAccount: Account = A(MI*4REy*, User0)

We’ll start mining a new block to be appended to the root block (i.e. the genesis block RootBlock).

val block1Future = mine(minerAccount, RootBlock, trans1)
val block1 = Await.result(block1Future, 20.seconds)
// block1: Block = BLK(o34V, T(b2ce, 4599/3), 2020-03-26 10:20:29, 3, 19793002)

Now that the last block of the blockchain is block1, a subsequent mining attempt will make it the preceding block; and further mining will be performed like so, successively.

val block2Future = mine(minerAccount, block1, trans2)
val block2 = Await.result(block2Future, 20.seconds)
// block2: Block = BLK(rqzE, T(30cf, 5599/3), 2020-03-26 10:20:59, 3, 9526833)

val block3Future = mine(minerAccount, block2, trans3)
val block3 = Await.result(block3Future, 20.seconds)
// block3: Block = BLK(1KAK, T(2e69, 3099/2), 2020-03-26 10:21:20, 3, 15148034)

A couple of notes:

1. At difficulty level 3, the 20-second timeout is generally sufficient on a computer with, say, a 3GHz 4-core CPU, although one may still get a timeout once in a while. If we elevate it to level 4, the required proof-generating time will be about 100-fold (i.e. 30+ minutes) of what its takes for level 3.
2. The incremented nonce saved in the returned block is the exact number of hashing trials to have finally satisfied the PoW requirement at the predefined difficulty level. At difficulty level 3, the number of trials ranges from millions to tens of millions. A level up would require billions of trials.

To look at what the final blockchain (i.e. block3) is like, let’s create a simple function that converts the linked blocks to elements of a List:

def blockchainToList(block: Block): List[Block] = {
  @scala.annotation.tailrec
  def loop(blk: Block, ls: List[Block]): List[Block] = blk match {
    case b: LinkedBlock => loop(b.blockPrev, b :: ls)
    case b: RootBlock.type => b :: ls
  }
  loop(block, List.empty[Block]).reverse
}

blockchainToList(block3)
// res1: List[Block] = List(
//   BLK(1KAK, T(2e69, 3099/2), 2020-03-26 10:21:20, 3, 15148034),
//   BLK(rqzE, T(30cf, 5599/3), 2020-03-26 10:20:59, 3, 9526833),
//   BLK(o34V, T(b2ce, 4599/3), 2020-03-26 10:20:29, 3, 19793002),
//   BLK(XF1C, T(----, 0/0), 1970-01-01 00:00:00, 0, 0)
// )

As a side note, the above detailed steps are for illustration purpose. The list of transactions and blocks could’ve been created in a more concise manner:

val listOfTrans = List.fill(3)(generateTrans(numOfAccounts, maxTransItems, keyPath, keyFiles))

val blockFuture = listOfTrans.foldLeft[Future[Block]](Future.successful(RootBlock)){
  (acc, trans) =>
    acc.flatMap(mine(minerAccount, _, trans))
}

blockchainToList(Await.result(blockFuture, 60.seconds))

// Or, use non-blocking `onComplete` callback to print the resulting blockchain

blockFuture.onComplete{
  case Success(b) => println((blockchainToList(b)))
  case Failure(e) => println(e)
}

Proof validation

Validating a proof (i.e. the incremented nonce) saved in a block is simple. Object ProofOfWork includes method `validProofIn(block: Block)` that takes a block and verifies whether the hash function can reproduce using the block’s hash and nonce a result with the number of leading zeros matching the difficulty level.

For example, the following verification confirms that `block3` has a valid proof.

ProofOfWork.validProofIn(block3)
// res1: Boolean = true

In the next blog post, we’ll port the above proof-of-concept Scala snippets to run on a scalable Akka cluster.