What are Hash and Merkle Tree?
Hashing is the transformation of a string of characters or a piece of information into a usually shorter fixed-length value or key that represents the original string. The fixed length value or key is called as the Hash.
Example of a Hashing function is the SHA-256, SHA1, MD5.
Reference Link for computing SHA256 Encryption: LINK
Few data values and corresponding hash values:
- Hash length is the same (64 units) irrespective of the data fed into it.
- Even a slight change in the input string would completely change the Hash.
- A unique piece of data will always produce the same hash. Hashes are encountered on a daily basis in the context of passwords, private data.
Hashing in Blockchain:
In the modern day Blockchain application hashing is used to write new transactions. After a new hash is created it is linked to the hash of the previous block. When a block of verified transactions are added, it is nearly impossible to reverse a transaction due to the enormous computing power required to tamper the blockchain, and the one-way nature of hashing. Hereby, hashing is crucial to maintain the cryptographic integrity of the blockchain. The stronger the hashing function, the more secure the blockchain.
Consider a set of data to be hashed. In Naive Hashing each element is sent into a hashing function, then each hash is appended and again it is hashed using a hashing function. Verifying membership of a data element, requires the entire hash data.
Disadvantages of Naive Hashing:
- Requires high computational power and disk space.
- Less secure than Merkle Tree.
Merkle tree structure allows for efficient and secure verification of data on a large scale. Helps in verifying the consistency and content of the data. Merkle trees are used by bothe Bitcoin and Ethereum.
How do Merkle trees work?
Merkle trees are created by repeatedly hashing pairs of nodes (which contain the hashes) until there is only one hash left. The final hash left is called as the Merkle Root or the Root Hash. In the Merkle tree each leaf node is the hash of the individual data (In blockchain the data is the transaction ID). Merkle trees requires even number of nodes and therefore are binary. If the leaf nodes are odd, the last hash will be duplicated once to create an even number of leaf nodes.
Uses of Merkle Trees:
- Provide means to prove integrity and validity of data
- Proofs and management only require tiny amounts of information to be transmitted across networks.
- They require little memory as the proofs are computationally easy and fast.