Hash Pointer and Merkle Tree Notes

November 2024
M	T	W	T	F	S	S
	1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

Mar 23, 2021 by admin in Uncategorized

In this article, we are discissing the topic about Hash Pointer and Merkle Tree. Hash pointer: its main job is to retrieve information and verify the information has not changed. Merkle trees are in a binary tree, so it requires an even number of leaf nodes. If there is an odd number of transactions.

Hash Pointer and Merkle Tree Notes discuss in details

What is Hash Pointer?

As you know that information hash, which serves as a pointer to location of information.
Before a hash pointer, we must first understand the Regular pointer so its main job is to get information.
Regular pointers: Regular pointers can be used to build data structures: linked lists, binary trees.
But in case of Hash pointer: its main job is to retrieve information and verify the information has not changed.
Hash pointers can also be used to construct related data structures. It is a Significantly useful for blockchain. In fact, the blockchain itself is a hash pointer based data structure that is a specialized way of storing data.
It is a additional property of cryptographic hashing.

A hash pointer consists of two things:

pointer to where some info is stored
(cryptographic) hash of the info

Data Structures (linked list) Built with Hash Pointers

A linked list is one of the most important parts in data structures. linked list looks like as in figuer:

Each element of the list is known as a Block.
Block: Header + Data
Header: Pointer to previous block = hash of the previous block
Data: information specific to the block
The last block in the list refers to null.
The first node in the list is referred to by a reference head.
The last node in the list is optionally referred to by a reference tail.

Hash pointers can be used to build a linked list, which is also called a blockchain. The head of the block chain is known genesis block.

Terminology

H( ): It is a hash pointer that containing the address of the first blockand the cryptographic hash of the whole block(data+hash pointer) stored there.
H1, H2, H3: hash pointers stored in blocks moving from right to left.
Block0, Block1, Block2: data blocks, moving from right to left.

Now suppose we change some data in block2.

Since H1 stores the cryptographic hash of block 2. The value of h1also changes and later the value of other hash pointers.

It is a tamper-evident log because head of the chain being known is enough to find tamper evidence in any internal block.

All head pointer has a hash pointer value to verify. if the value does not match, it means the data has been tampered.

Binary Tree with hash pointer (Merkle Tree)

A Merkle tree is a binary tree that uses hash pointers.
The Merkle tree was developed by Ralph Merkle in 1979.
The leaves are data blocks, nodes further up in the tree are the hashes of their respective children.

What is a Merkle Tree?

According to Wikipedia: In cryptography and computer science, a hash tree or Merkle tree is a tree in which every leaf node is labelled with the hash of a data block and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes.

Non-leaf node: Each non-leaf node is the hash of the values of their child nodes.
Leaf Node: The leaf nodes are the nodes in the lowest tier of the tree.

How do Merkle trees work?

A Merkle tree works like this: we need to learn three important terms. They are as below:

Merkle Root: Multiple branches are hashed together finally getting one single hash.
Leaf Nodes: Every leaf node is a hash of transactional data
Non-Leaf Nodes: It is a hash of its previous hashes.

Merkle trees are in a binary tree, so it requires an even number of leaf nodes. If there is an odd number of transactions, the last hash will be duplicated once to create an even number of leaf nodes.

For Example:

There are four transactions in a block: TX1, TX2, TX3, and TX4. The transactions are then hashed and then stored in leaf nodes which we name as Hash 2, Hash 3, Hash 4, and Hash 5.

the leaf nodes of Hash 2, 3, 4, and 5 are again hashed and created into a combined hash of 01 and 01. Finally, these two hashes are used to create the Merkle Root or Root Hash.

The whole process of hashing can be done on a very large data set which makes the Merkle Trees data structure useful in the case of decentralized networks.

Merkle Trees benefits

It serves as evidence of the integrity and validity of the data.
Its proof and control require the simplest a small quantity of facts to be dispatched throughout a community.
It helps in saving the memory or disk space as the proofs, computationally easy and fast.
Their proofs and management require tiny amounts of information to be transmitted across networks.

Conclusion

TheHash pointer and Merkle tree is one of the important concepts in computer science. A Merkle tree is useful because it allows computers to verify on leaves, under trees, without storing the entire set of information.

Browse By

Calendar