What is a Merkle Tree?

Merkle Tree (also called a Merkle Tree or Hash Tree) is a fundamental component and foundation for the functionality of blockchain. It enables efficient and secure verification of large data structures, particularly in blockchain and datasets that can grow without limit.

The implementation of Merkle Tree in blockchain has many effects. It allows blockchain to scale while providing a hash-based architecture to maintain data integrity and a standard way to verify data integrity. Cryptographic hash functions are the fundamental technology that allows Merkle Trees to work, so it is first important to understand what cryptographic hashing is.

Cryptographic Hash Function

A hash function is any function used to map data of arbitrary size (input) to output of fixed size. A hash algorithm is applied to input data and the resulting output of fixed length is called a hash function. Many hash algorithms are publicly available and can be selected based on your needs.

The hash result from arbitrary input is not only fixed in length, it is also completely unique. That is, no matter how many times you run the function on the same input, the output will always be the same. For example, if you have the following datasets as input, the output result is unique for each input. Note that in the second and third examples, although the difference in inputs is only one word, the output results are completely different. This is very important because it allows “fingerprinting” of data.

Merkle Tree & Merkle Root

The story of Merkle Tree begins in 1979 with a young man named Ralph Merkle. While studying at Stanford University, Merkle wrote an academic paper titled “A Certified Digital Signature”. In other words, he designed a data verification process that allowed computers to perform their work much faster than before.

Merkle’s idea, now known as the Merkle Tree, has revolutionized the world of cryptography by changing how cryptographic computer protocols operate. In fact, Merkle Trees are mentioned multiple times in Satoshi Nakamoto’s 2008 essay introducing Bitcoin to the world. They are also widely used in Bitcoin code.

So, what is a Merkle Tree? Simply put, a Merkle Tree is a data structure method that allows a large amount of information to be verified for accuracy extremely quickly and efficiently.

Now let’s consider it on blockchain. First, it’s important to note that each transaction on a blockchain has a unique transaction ID. With most blockchains, each transaction ID is a 64-character code occupying 256 bits (32 bytes) of memory.

Blockchains typically consist of hundreds of thousands of blocks, each containing up to thousands of transactions, so you can imagine how memory space becomes a problem. Therefore, it optimizes to use as little data as possible when processing and verifying transactions. This minimizes CPU processing time while ensuring the highest level of security.

That’s exactly what Merkle Tree does. Simply put, Merkle Tree takes a large number of transaction IDs and runs them through a mathematical process that results in a 64-character code.

This code is extremely important because it allows any computer to quickly verify that a specific transaction occurred on a specific block in the most efficient way possible. This code is called the Merkle Root.

The unique code that Merkle Tree creates is called the Merkle Root. Each block in a blockchain has only one Merkle Root. The Merkle Root is important data because it allows computers to verify information with remarkable speed and efficiency.

To understand a bit more deeply how Merkle Root is created, the first step is to organize all input data.

Merkle Tree, by design, always groups all inputs into pairs. If there are an odd number of inputs, the last input is copied and then paired with itself. This applies to all transaction IDs written on a block of the blockchain.

For example, suppose a single block contains a total of 512 transactions. Merkle Tree would start by grouping those 512 transaction IDs into 256 pairs. Then those 256 pairs of transaction IDs would undergo a mathematical process called hashing or hash algorithm, which would produce 256 new 64-character alphanumeric codes.

The exact same process will occur again. Those 256 new codes will be paired and turned into 128 codes. The process will be repeated, cutting the number of codes in half each time, until only one code remains. That single code is the Merkle Root.

An Example of Merkle Tree

To visualize this concept clearly, let’s look at a very simple example of a Merkle Tree. Imagine there are 8 transactions made on a specific block with 8 different IDs. In reality, transaction IDs are 64 characters long (including numbers and letters), but for simplicity, let’s assume they are only 8 characters long. To make the explanation simpler, we’ll just use numbers (and ignore letters).

So in this example, our eight transaction IDs would be:

• 11111111
• 22222222
• 33333333
• 44444444
• 55555555
• 66666666
• 77777777
• 88888888

Our Merkle Tree would look like this:

Now, suppose the method to hash transaction IDs is to take the first, third, fifth, and seventh digits from each combined pair, then simply concatenate those numbers to form a new 8-digit code.

Of course, in reality, the mathematics behind hash algorithms is much more complex than this. But for this simple explanation, this basic system is sufficient.

Efficiency and Speed: Benefits of Merkle Tree

Suppose we want to verify transaction ID in the current example. Bob says he paid Alice a certain amount of Bitcoin and tells us the transaction ID is 88888888. He also sends us 3 hashes: 77777777, 55556666, and 11223344. That’s all the information needed to be sent or received to verify Bob’s payment to Alice.

These three hash values, along with the mentioned transaction ID (the Merkle Root of this specific block) are exactly the data needed to verify Bob’s payment to Alice. This is much less data than what would be required to verify the entire Merkle Tree. Therefore, the verification process is much faster and more efficient for everyone.

Let’s see how it works. We already have the block Merkle Root, so Bob doesn’t need to send it to us. He sends us his transaction ID and the 3 additional hashes that we listed above. He also sends us some information about the order and position to use the hash. Now, all we have to do is run the hash algorithm on the dataset that Bob provided.

We start by hashing the first code 77777777 with transaction ID 88888888, giving us the result 77778888. Bob didn’t send us this code (77778888) but it’s not necessary because we use the same hash algorithm as he does. Therefore, we get the same correct result as he did.

Then we take the second code that Bob sent us, 55556666, and hash it with the new code 77778888 that we just got. This, of course, produces 55667788.

Finally, we hash the third code Bob provided us, 11223344, with the other new code we got, 55667788, and we end up with the correct Merkle Root: 12345678.

Notice that we only needed 3 codes from Bob and only had to run the hash algorithm three times to see that Bob’s transaction is valid. That means our computer performed less than half the work required to verify the entire Merkle Tree. The initial Merkle Tree diagram has 15 numbers and the hash algorithm needs to be run 7 times. But more than half of that tree is not necessary to verify Bob’s transaction!

This process is sufficient to verify that Bob actually paid Alice a certain amount of Bitcoin because we were able to derive the numbers that when hashed together with the other codes Bob sent us, produced the same Merkle Root that we knew was correct for this specific block.

Bob could forge a transaction because that would require finding a fraudulent transaction ID and an additional set of fraudulent codes that, when input into the hash function, would produce the actual Merkle Root. The chance of this happening is so small that we can confidently say it is impossible.

In this simple example, the computational power savings seem minimal. However, when you consider that blocks in a blockchain can contain thousands of transactions, it’s easy to see how dramatically Merkle Trees increase efficiency.

In summary, that’s the main benefit of Merkle Tree. It allows computers to verify information extremely efficiently with much less data than would be required without Merkle Tree.

According to:

• komodoplatform.com | backup

• blockonomi.com | backup