Named after Ralph Merkle, a Merkle Tree is a method of structuring data that allows a large body of information to be verified for accuracy extremely quickly and efficiently.
In his academic paper titled, A Certified Digital Signature, he wrote about a new digital signature based only on a conventional encryption function which is as secure as the underlying encryption function — the security does not depend on the difficulty of factoring and the high computational costs of modular arithmetic are avoided.
The signature system can sign an unlimited number of messages, and the signature size increases logarithmically as a function of the number of messages signed. Signature size in a ‘typical’ system might range from a few hundred bytes to a few kilobytes, and generation of a signature might require a few hundred to a few thousand computations of the underlying conventional encryption function.
The Merkle Tree revolutionised the world of cryptography and, by extension, the way that encrypted computer protocols function
Under The Hood Of Blockchain
Source: Investopedia
In the figure above, “TA” represents a normal transaction, like the one described above. These transactions are hashed individually to give their corresponding hash value. For example, “TD” is put through a hash function to give its corresponding hash value of “HD“.
Blockchains are typically made up of hundreds of thousands of blocks, with each block containing as many as several thousand transactions. So, memory allocation is a problem when it comes to handling these transactions.
Each transaction on a blockchain has its own unique transaction ID. With most blockchains, each transaction ID is a 64-character code that takes up 256 bits (32 bytes) of memory.
Merkle Trees take a huge number of transaction IDs and put them through a mathematical process that results in a single, 64-character code.
The single code that a Merkle Tree produces is called the Merkle Root.
For instance, let’s suppose that a single block contains a total of 512 transactions. The Merkle Tree would begin by grouping those 512 transactions IDs into 256 pairs. Then, those 256 pairs of transaction IDs would go through a mathematical process, called a hashing function or hashing algorithm, that would result in 256 new, 64-character alphanumeric codes.
The same exact process would occur again. Those 256 new codes would be paired up and turned into 128 codes. The process would be repeated, cutting the number of codes in half each time until only a single code remained. That single code is our Merkle Root.
Why Use A Hash Tree Like Merkle Tree:
1. They provide a means to prove the integrity and validity of data
2. They require little memory or disk space as the proofs are computationally easy and fast
3. Their proofs and management only require tiny amounts of information to be transmitted across networks
Merkle trees help verify that later versions of a log include everything from an earlier version and that all data is recorded and presented in chronological order. Proving that a log is consistent requires showing that no previous records have been added, altered or tampered with and that the log has never been branched or forked.
Applications Of Merkle Trees
Merkle trees and variations of it are used by Bitcoin, Ethereum, Apache Cassandra. So wherever these cryptocurrencies are in use, it can be safely assumed that Merkle trees play a large part. Single Merkle trees enable simple light clients. It does not tell anything about the current state i.e. how many bitcoins one holds or account balance on Ethereum.
- Merkle trees are used extensively by SPV nodes.
- Google’s subsidiary DeepMind Health has plans to maintain patient data using the same technology.
- Git and Mercurial use Merkle trees to manage their versions.
- Whereas, Ethereum uses three different Merkle Roots in each block:
- The first root is of the transactions in the block
- The second root represents the state
- The third root is for transaction receipts
Digital signatures are an indispensable element for secured communication applications. They are needed, to ensure the authentication of a communication partner, i.e. in web services like Email or chats. They are also needed, to ensure the authentication of a web server for web services like online banking.
The big advantage of the Merkle Signature Scheme is, that the security does not rely on the difficulty of any mathematical problem. The security of the Merkle Signature Scheme depends on the availability of a secure hash function and a secure one-time digital signature. Even if a one-time signature or a hash function becomes insecure, it can be easily exchanged. This makes it very likely that the Merkle Signature Scheme stays secure even if the conventional signature schemes become insecure.
Know More About Merkle Trees here.
