Merkle Tree

Asha Rani
Jan 4, 2020 2 min read

Introduction

Merkle Tree [1] is an authenticated data structure, also known as Merkle hash Tree. It is an authenticated binary search tree.It is a fundamental part of the blockchain.
It uses hash functions like MD5, SHA, etc. In the Fig1. Shows a hash binary tree, so the leaf nodes contain the hash value of the block of transaction. The internal node contains the hash value of the concatenated value of leaf nodes. This process of creating a node continues until we reach the root of the tree. The root node is also known as the Merkle Root. This Merkle root is the data content of the blocks of the blockchain.
This data structure is very useful for checking inconsistencies and greatly minimizes the data content.

Method to create Merkle Tree

  1. To build up a Merkle tree ,firstly leaf nodes is required which is an ordered set containing hash value i.e a node with element xi contains hash value h(xi).
  2. h( ) is a one-way hash function, which is an algorithm that converts messages or text in a fixed string value.
  3. The internal node contains the hash value of the concatenation of their children in the order. eg h(v1 || v2),if value of leaf nodes are v1 and v2 respectively.
  4. Step 3 continues until the root level, and finally, the root node is digitally signed.
  5. In fig 1, the case of the odd number of internal nodes is shown, then for the last internal node, a duplicate node is created for creations of the further internal node.This result in the internal node containing value h(vm || vm)

Properties

  1. The traversal of the Merkle Hash Tree in a bottom-up approach. But a top, bottom approach is also possible.
  2. Merkle Hash Tree (MHT) have the ability to give empty proofs, i.e., to prove that value is non-existent in the tree.
  3. Merkle Hash Tree(MHT) can be implemented using both binary trees and improved B-tree.

Application

  1. Initially, it was used for the purpose of a one-time signature and authentication public key. It is also used in the outsource database model.
  2. It is an important part of the blockchain technology as it plays an important role in mapping huge data.

Reference

[1]: Mykletun, E., Narasimha, M., & Tsudik, G. (2004). Authentication and Integrity in Outsourced Databases.