ABAP meets #BlockChain – Transaction Merkle Tree

So continuing from our previous blog where we have implemented a basic blockchain using ABAP, let us dig into the transactions structure of the block.  A block is collection of transactions, how many transactions that varies from case to case. For example in case of Bitcoin,it has around 500 transactions in a block.

What is a transaction?

A Transaction is nothing but it contains details such as sender, receiver, value of the transaction etc.. It can have N number of fields depending on what needs to be achieved using blockchain. Below mentioned figure highlights a basic transaction structure.

How transactions are arranged in a block -> Merkle Tree

The arrangement of the transactions inside a block is basically in the form of a binary tree.  So what is a Merkle Tree than? A Merkle tree is created by recursively Hashing (encrypted) a pair of nodes data at a time. This continues till we get one single node, known as root node or Merkle Root which contains the hashed data. If the total number of leaf nodes is odd, then the last node will be duplicated so as to make a pair.

The below mentioned figure depicts basic structure of a Merkle Tree and how it merges towards Root node. As can be seen, First all leaf nodes shown with prefix T are hashed and renamed with prefix as H. Then recursively we are pairing two nodes to get the next hash node. This goes on till we get one root node shown as HABCD below.

ABAP implementation of Merkle Tree

• Number of leaf nodes is kept as input selection screen parameter.

PARAMETERS: leafnode TYPE i.

• Firstly we determine if number of nodes is odd or even if odd add one to full fill the pairing requirement. In this example data of all leaf nodes is  concatenation leaf with index.The height of the tree is determined by dividing the total number of leaf nodes by 2.

  " if number of leaf nodes is odd add one to make it even,
  IF leafnode MOD 2 <> 0.
    leafnode = leafnode + 1.
  ENDIF.
  " Calculate tree height
  treeheight = leafnode / 2.
  count = 0.
  DATA lv_tabix TYPE string.
  DO leafnode TIMES.
    lv_tabix = sy-index.
    CONCATENATE 'Leaf' lv_tabix INTO merkelline-leafvalue  .
    PERFORM dohash USING merkelline-leafvalue CHANGING merkelline-leafhash.
    merkelline-level = treeheight.
    merkelline-leftleafhash = ''.
    merkelline-rightleafhash = ''.
    APPEND merkelline TO merkeldata.
  ENDDO.
  merkeldata1 = merkeldata.

• Recursively in a subroutine named recursivehashing, we keep hashing the pair of nodes and keep moving towards the root. At each iteration we are checking,if number nodes is odd then add last node as duplicate one in order to keep the principle or Merkle Tree intact.

FORM recursivehashing.
 ""Check number of nodes to be hashed if odd add the last node again.
  DESCRIBE TABLE merkeldata1 LINES DATA(leafcount).
  IF leafcount MOD 2 <> 0.
    READ TABLE merkeldata1 INTO merkelline1 INDEX leafcount.
    APPEND merkelline1 TO merkeldata1.
  ENDIF.

  DESCRIBE TABLE merkeldata1 LINES leafcount.
  DATA(iteration) = leafcount / 2.
  " Combine the number of nodes based on iteration count.
  DO iteration TIMES.
    DATA(count) = sy-index * 2.
    DATA(count2) = count - 1.
    READ TABLE merkeldata INTO merkelline1 INDEX count.
    READ TABLE merkeldata INTO merkelline2 INDEX count2.

    CONCATENATE merkelline1-leafvalue merkelline2-leafvalue INTO merkelline-leafvalue.
    CONCATENATE merkelline1-leafhash merkelline2-leafhash   INTO merkelline-leafhash.
    PERFORM dohash USING  merkelline-leafhash CHANGING merkelline-leafhash.
    merkelline-leftleafhash = merkelline1-leafhash.
    CONCATENATE merkelline1-leafhash merkelline2-leafhash INTO merkelline-leafhash  .
    merkelline-rightleafhash = merkelline2-leafhash.

    merkelline-level = treeheight - count.
    APPEND merkelline TO merkeldata2.
  ENDDO.
  " Add the processed nodes to master table and call the subroutine again with processed node data
  CLEAR adddummy.
  INSERT LINES OF merkeldata2 INTO merkeldata INDEX 1.
  CLEAR merkeldata1.
  merkeldata1 = merkeldata2.
  CLEAR merkeldata2.
  DESCRIBE TABLE merkeldata1 LINES leafcount.
  IF leafcount <> 1.
    PERFORM recursivehashing.
  ENDIF.
ENDFORM.
FORM dohash USING inputvalue TYPE string CHANGING hashvalue TYPE string.
  CALL METHOD cl_abap_message_digest=>calculate_hash_for_char
    EXPORTING
      if_algorithm  = 'SHA1'
      if_data       = merkelline-leafvalue
    IMPORTING
      ef_hashstring = merkelline-leafhash.
ENDFORM.

Final Output of Hashed Merkle Root

• The output structure contains the readable combined value as well as hashed value. Additionally left and right child details of the current node is also stored.

What is next?

As we were able to construct a basic Merkle tree, the root hash can be now passed onto the block for further processing in the blockchain. I hope this blog helps in enhancing your understanding about Blockchain concepts further:)

Finally wrapping up with next set of challenges on the list.

• Validate whether a node belongs to Merkle tree or not basically Merkle Path
• Wish list is to make an app based on concept of blockchain if possible, still researching.

Feel free to provide your feedback, open to all ears. Lets share and learn:)