Introduction to Merkle Tree
Merkle tree also known as hash tree is a data structure used for data verification and synchronization.
It is a tree data structure where each non-leaf node is a hash of it’s child nodes. All the leaf nodes are at the same depth and are as far left as possible.
It maintains data integrity and uses hash functions for this purpose.
Hash Functions:
So before understanding how Merkle trees work, we need to understand how hash functions work.
A hash function maps an input to a fixed output and this output is called hash. The output is unique for every input and this enables fingerprinting of data. So, huge amounts of data can be easily identified through their hash.
This is a binary merkel tree, the top hash is a hash of the entire tree.
- This structure of the tree allows efficient mapping of huge data and small changes made to the data can be easily identified.
- If we want to know where data change has occurred then we can check if data is consistent with root hash and we will not have to traverse the whole structure but only a small part of the structure.
- The root hash is used as the fingerprint for the entire data.
For a Binary Merkel tree
Operation | Complexity |
---|---|
Space | O(n) |
Searching | O(logn) |
Traversal | O(n) |
Insertion | O(logn) |
Deletion | O(logn) |
Synchronization | O(logn) |
Applications:
- Merkle trees are useful in distributed systems where same data should exist in multiple places.
- Merkle trees can be used to check inconsistencies.
- Apache Cassandra uses Merkle trees to detect inconsistencies between replicas of entire databases.
- It is used in bitcoin and blockchain.
Implementation:
// CPP code for the above data structure
#include <bits/stdc++.h>
using namespace std;
/* determines the maximum capacity of
Hash Tree */
int maxim = 10;
/* determines the number of elements
present in Hash Tree */
int size = 0;
/* node for storing an item in a Binary Tree */
struct node {
int key;
int value;
struct node* left;
struct node* right;
};
/* for storing a Binary Tree at each index
of Hash Tree */
struct bst {
/* head pointing to the root of Binary Tree */
struct node* head;
};
struct bst* arr;
void insert_element(struct node* tree, struct node* item);
struct node* find(struct node* tree, int key);
struct node* remove_element(struct node* tree, int key);
void display_tree(struct node* tree);
/* this function creates an index corresponding
to the every given key */
int hashcode(int key) { return (key % maxim); }
void add(int key, int value)
{
int index = hashcode(key);
/* extracting Binary Tree at the given index */
struct node* tree = (struct node*)arr[index].head;
/* creating an item to insert in the hashTree */
struct node* new_item
= (struct node*)malloc(sizeof(struct node));
new_item->key = key;
new_item->value = value;
new_item->left = NULL;
new_item->right = NULL;
if (tree == NULL) {
/* absence of Binary Tree at a given
index of Hash Tree */
cout << "Inserting " << key << " and " << value
<< endl;
arr[index].head = new_item;
size++;
}
else {
/* a Binary Tree is present at given index
of Hash Tree */
struct node* temp = find(tree, key);
if (temp == NULL) {
/*
* Key not found in existing Binary Tree
* Adding the key in existing Binary Tree
*/
cout << "Inserting " << key << "and" << value
<< endl;
insert_element(tree, new_item);
size++;
}
else {
/*
* Key already present in existing Binary Tree
* Updating the value of already existing key
*/
temp->value = value;
}
}
}
/*
* this function finds the given key in the Binary Tree
* returns the node containing the key
* returns NULL in case key is not present
*/
struct node* find(struct node* tree, int key)
{
if (tree == NULL) {
return NULL;
}
if (tree->key == key) {
return tree;
}
else if (key < tree->key) {
return find(tree->left, key);
}
else {
return find(tree->right, key);
}
}
/* this function inserts the newly created node
in the existing Binary Tree */
void insert_element(struct node* tree, struct node* item)
{
if (item->key < tree->key) {
if (tree->left == NULL) {
tree->left = item;
return;
}
else {
insert_element(tree->left, item);
return;
}
}
else if (item->key > tree->key) {
if (tree->right == NULL) {
tree->right = item;
return;
}
else {
insert_element(tree->right, item);
return;
}
}
}
/* displays the content of hash Tree */
void display()
{
int i = 0;
for (i = 0; i < maxim; i++) {
struct node* tree = arr[i].head;
if (tree == NULL) {
cout << "arr[" << i
<< "] has no
elements " << endl;
}
else {
cout << "arr[" << i
<< "] has
elements " << endl;
display_tree(tree);
}
}
}
/* displays content of binary tree of
particular index */
void display_tree(struct node* tree)
{
if (tree == NULL) {
return;
}
cout << tree->key << " and " << tree->value << " ";
if (tree->left != NULL) {
display_tree(tree->left);
}
if (tree->right != NULL) {
display_tree(tree->right);
}
}
/* for initializing the hash Tree */
void init()
{
int i = 0;
for (i = 0; i < maxim; i++) {
arr[i].head = NULL;
}
}
/* returns the size of hash Tree */
int size_of_hashTree() { return size; }
/* to del a key from hash Tree */
void del(int key)
{
int index = hashcode(key);
struct node* tree = (struct node*)arr[index].head;
if (tree == NULL) {
cout << key << " Key not present" << endl;
}
else {
struct node* temp = find(tree, key);
if (temp == NULL) {
cout << key << " is not present";
}
else {
tree = remove_element(tree, key);
cout << key
<< " has been removed
form the hash tree " << endl;
}
}
}
struct node* remove_element(struct node* tree, int key)
{
if (tree == NULL) {
return NULL;
}
if (key < tree->key) {
tree->left = remove_element(tree->left, key);
return tree;
}
else if (key > tree->key) {
tree->right = remove_element(tree->right, key);
return tree;
}
else {
/* reached the node */
if (tree->left == NULL && tree->right == NULL) {
size--;
return tree->left;
}
else if (tree->left != NULL
&& tree->right == NULL) {
size--;
return tree->left;
}
else if (tree->left == NULL
&& tree->right != NULL) {
size--;
return tree->right;
}
else {
struct node* left_one = tree->left;
while (left_one->right != NULL) {
left_one = left_one->right;
}
tree->key = left_one->key;
tree->value = left_one->value;
tree->left
= remove_element(tree->left, tree->key);
return tree;
}
}
}
// Driver Code
int main()
{
int choice, key, value, n, c;
arr = (struct bst*)malloc(maxim * sizeof(struct bst*));
init();
do {
cout << "Implementation of Hash Tree" << endl;
cout << "MENU-: \n1.Insert an item in the Hash Tree"
"\n2.Remove an item from the Hash Tree"
"\n3.Check the size of Hash Tree"
"\n4.Display Hash Tree"
"\n\n Please enter your choice-:";
cin >> choice;
switch (choice) {
case 1:
cout << "Inserting element in
Hash Tree " << endl;
cout
<< "Enter key and value-: ";
cin >> key >> value;
add(key, value);
break;
case 2:
cout << "Deleting item from Hash Tree
\n Enter the key to delete -
: ";
cin
>> key;
del(key);
break;
case 3:
n = size_of_hashTree();
cout << "Size of Hash Tree is-:" << n << endl;
break;
case 4:
display();
break;
default:
cout << "Wrong Input" << endl;
}
cout << "\n Do you want to continue-:
(press 1 for yes) ";
cin >> c;
} while (c == 1);
return 0;
}
// This code is contributed by Amit Das(amit_das)
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;
// Node class represents a node in the Merkle Tree
class Node {
Node left, right;
String value, content;
boolean isCopied;
// Node constructor
Node(Node left, Node right, String value,
String content, boolean isCopied)
{
this.left = left;
this.right = right;
this.value = value;
this.content = content;
this.isCopied = isCopied;
}
// Method to hash a string value using SHA-256
static String hash(String val)
throws NoSuchAlgorithmException
{
MessageDigest digest
= MessageDigest.getInstance("SHA-256");
byte[] hash = digest.digest(
val.getBytes(StandardCharsets.UTF_8));
StringBuilder hexString = new StringBuilder();
for (byte b : hash) {
String hex = Integer.toHexString(0xff & b);
if (hex.length() == 1)
hexString.append('0');
hexString.append(hex);
}
return hexString.toString();
}
// Method to create a copy of a node
Node copy()
{
return new Node(this.left, this.right, this.value,
this.content, true);
}
}
// MerkleTree class represents the Merkle Tree
class MerkleTree {
Node root;
// MerkleTree constructor
MerkleTree(List<String> values)
throws NoSuchAlgorithmException
{
this.root = buildTree(values);
}
// Method to build the Merkle Tree from a list of string
// values
Node buildTree(List<String> values)
throws NoSuchAlgorithmException
{
List<Node> leaves = new ArrayList<>();
for (String e : values) {
leaves.add(new Node(null, null, Node.hash(e), e,
false));
}
if (leaves.size() % 2 == 1) {
leaves.add(
leaves.get(leaves.size() - 1).copy());
}
return buildTreeRec(leaves);
}
// Recursive method to build the Merkle Tree
Node buildTreeRec(List<Node> nodes)
throws NoSuchAlgorithmException
{
if (nodes.size() % 2 == 1) {
nodes.add(nodes.get(nodes.size() - 1).copy());
}
int half = nodes.size() / 2;
if (nodes.size() == 2) {
return new Node(nodes.get(0), nodes.get(1),
Node.hash(nodes.get(0).value
+ nodes.get(1).value),
nodes.get(0).content + "+"
+ nodes.get(1).content,
false);
}
Node left = buildTreeRec(nodes.subList(0, half));
Node right = buildTreeRec(
nodes.subList(half, nodes.size()));
String value = Node.hash(left.value + right.value);
String content = left.content + "+" + right.content;
return new Node(left, right, value, content, false);
}
// Method to print the Merkle Tree
void printTree() { printTreeRec(this.root); }
// Recursive method to print the Merkle Tree
void printTreeRec(Node node)
{
if (node != null) {
if (node.left != null) {
System.out.println("Left: "
+ node.left.value);
System.out.println("Right: "
+ node.right.value);
}
else {
System.out.println("Input");
}
if (node.isCopied) {
System.out.println("(Padding)");
}
System.out.println("Value: " + node.value);
System.out.println("Content: " + node.content);
System.out.println("");
printTreeRec(node.left);
printTreeRec(node.right);
}
}
// Method to get the root hash of the Merkle Tree
String getRootHash() { return this.root.value; }
}
public class Main {
public static void main(String[] args)
throws NoSuchAlgorithmException
{
List<String> elems = Arrays.asList(
"w3wiki", "A", "Computer", "Science",
"Portal", "For", "Beginner");
System.out.println("Inputs: ");
for (String elem : elems) {
System.out.print(elem + " | ");
}
System.out.println("\n");
MerkleTree mtree = new MerkleTree(elems);
System.out.println(
"Root Hash: " + mtree.getRootHash() + "\n");
mtree.printTree();
}
}
# Python code for implemementing Merkle Tree
from typing import List
import hashlib
class Node:
def __init__(self, left, right, value: str, content, is_copied=False) -> None:
self.left: Node = left
self.right: Node = right
self.value = value
self.content = content
self.is_copied = is_copied
@staticmethod
def hash(val: str) -> str:
return hashlib.sha256(val.encode('utf-8')).hexdigest()
def __str__(self):
return (str(self.value))
def copy(self):
"""
class copy function
"""
return Node(self.left, self.right, self.value, self.content, True)
class MerkleTree:
def __init__(self, values: List[str]) -> None:
self.__buildTree(values)
def __buildTree(self, values: List[str]) -> None:
leaves: List[Node] = [Node(None, None, Node.hash(e), e)
for e in values]
if len(leaves) % 2 == 1:
# duplicate last elem if odd number of elements
leaves.append(leaves[-1].copy())
self.root: Node = self.__buildTreeRec(leaves)
def __buildTreeRec(self, nodes: List[Node]) -> Node:
if len(nodes) % 2 == 1:
# duplicate last elem if odd number of elements
nodes.append(nodes[-1].copy())
half: int = len(nodes) // 2
if len(nodes) == 2:
return Node(nodes[0], nodes[1], Node.hash(nodes[0].value + nodes[1].value), nodes[0].content+"+"+nodes[1].content)
left: Node = self.__buildTreeRec(nodes[:half])
right: Node = self.__buildTreeRec(nodes[half:])
value: str = Node.hash(left.value + right.value)
content: str = f'{left.content}+{right.content}'
return Node(left, right, value, content)
def printTree(self) -> None:
self.__printTreeRec(self.root)
def __printTreeRec(self, node: Node) -> None:
if node != None:
if node.left != None:
print("Left: "+str(node.left))
print("Right: "+str(node.right))
else:
print("Input")
if node.is_copied:
print('(Padding)')
print("Value: "+str(node.value))
print("Content: "+str(node.content))
print("")
self.__printTreeRec(node.left)
self.__printTreeRec(node.right)
def getRootHash(self) -> str:
return self.root.value
def mixmerkletree() -> None:
elems = ["w3wiki", "A", "Computer",
"Science", "Portal", "For", "Beginner"]
# as there are odd number of inputs, the last input is repeated
print("Inputs: ")
print(*elems, sep=" | ")
print("")
mtree = MerkleTree(elems)
print("Root Hash: "+mtree.getRootHash()+"\n")
mtree.printTree()
mixmerkletree()
# This code was contributed by Pranay Arora (TSEC-2023).
const crypto = require('crypto');
// Node class represents a node in the Merkle Tree
class Node {
constructor(left, right, value, content, isCopied) {
this.left = left;
this.right = right;
this.value = value;
this.content = content;
this.isCopied = isCopied;
}
// Method to hash a string value using SHA-256
static hash(val) {
return crypto.createHash('sha256').update(val).digest('hex');
}
// Method to create a copy of a node
copy() {
return new Node(this.left, this.right, this.value, this.content, true);
}
}
// MerkleTree class represents the Merkle Tree
class MerkleTree {
constructor(values) {
this.root = this.buildTree(values);
}
// Method to build the Merkle Tree from a list of string values
buildTree(values) {
let leaves = values.map(e => new Node(null, null, Node.hash(e), e, false));
if (leaves.length % 2 === 1) {
leaves.push(leaves[leaves.length - 1].copy());
}
return this.buildTreeRec(leaves);
}
// Recursive method to build the Merkle Tree
buildTreeRec(nodes) {
if (nodes.length % 2 === 1) {
nodes.push(nodes[nodes.length - 1].copy());
}
let half = nodes.length / 2;
if (nodes.length === 2) {
return new Node(nodes[0], nodes[1], Node.hash(nodes[0].value + nodes[1].value),
nodes[0].content + "+" + nodes[1].content, false);
}
let left = this.buildTreeRec(nodes.slice(0, half));
let right = this.buildTreeRec(nodes.slice(half));
let value = Node.hash(left.value + right.value);
let content = left.content + "+" + right.content;
return new Node(left, right, value, content, false);
}
// Method to print the Merkle Tree
printTree() {
this.printTreeRec(this.root);
}
// Recursive method to print the Merkle Tree
printTreeRec(node) {
if (node !== null) {
if (node.left !== null) {
console.log("Left: " + node.left.value);
console.log("Right: " + node.right.value);
} else {
console.log("Input");
}
if (node.isCopied) {
console.log("(Padding)");
}
console.log("Value: " + node.value);
console.log("Content: " + node.content);
console.log("");
this.printTreeRec(node.left);
this.printTreeRec(node.right);
}
}
// Method to get the root hash of the Merkle Tree
getRootHash() {
return this.root.value;
}
}
// Main program
const elems = ["w3wiki", "A", "Computer", "Science", "Portal", "For", "Beginner"];
console.log("Inputs: ");
elems.forEach(elem => {
process.stdout.write(elem + " | ");
});
console.log("\n");
const mtree = new MerkleTree(elems);
console.log("Root Hash: " + mtree.getRootHash() + "\n");
mtree.printTree();
Output
...a628f9ed881e2d784cb9cd85f3d5d04a6489 Value: 4fcfb77eaf9a279c4ff2d20171c1626c2823a82a2cec1ddc0c23dbcb48822e80 Content: Portal+For+Beginner+Beginner Left: b65ffe0cec61786d5d090268b99a14a807101d847fe4f5fbb4daa2764b73cd84 Right: ca15ebc05a3c5c1348753b209c4452c54022dbe565d9943b11c795e3af9eb0b0 Value: 67da93d6580ec1ef25cd9589147fcf93c7612f1063c37e92b0c441627afdd8bb Content: Portal+For Input Value: b65ffe0cec61786d5d090268b99a14a807101d847fe4f5fbb4daa2764b73cd84 Content: Portal Input Value: ca15ebc05a3c5c1348753b209c4452c54022dbe565d9943b11c795e3af9eb0b0 Content: For Left: 0c0dcd8c8d8c6c0dfba6677e1e11076ff864f3351e3cbd1a6c9571269b4d655d Right: 0c0dcd8c8d8c6c0dfba6677e1e11076ff864f3351e3cbd1a6c9571269b4d655d Value: 9855c9f31157005f7f2ff1c7ca91a628f9ed881e2d784cb9cd85f3d5d04a6489 Content: Beginner+Beginner Input Value: 0c0dcd8c8d8c6c0dfba6677e1e11076ff864f3351e3cbd1a6c9571269b4d655d Content: Beginner Input (Padding) Value: 0c0dcd8c8d8c6c0dfba6677e1e11076ff864f3351e3cbd1a6c9571269b4d655d Content: Beginner
Contact Us