Merkle Trees — Ensuring Integrity On Blockchains
Welcome to a new post here at blockwhat?, where we explore the mesmerizing technological fabric that powers blockchains.
In this post we will take a look at a fascinating concept known as Merkle Trees and find out how they ensure integrity on blockchains. After getting to know the history behind it, we will examine how it works and why it matters, especially in a blockchain context.
An exciting journey into one of the fundamental parts that make blockchains so powerful — let’s go!
This article is part five of our journey into the technological foundations of blockchain technology.
If you’re new here and want to understand what’s going on, just click here.
- The Tech Behind Blockchains
- A Journey Into Decentralization
- Hash(ing) Everywhere — A Primer On Hash Functions
- Public Key Encryption — A Comprehensive Guide
- Merkle Trees — Ensuring Integrity On Blockchains (This article)
- Finding Consensus 1/4: Byzantine Fault Tolerance
- Finding Consensus 2/4: Proof of Work
- Finding Consensus 3/4: Proof Of Stake
- Finding Consensus 4/4: Alternative Consensus Mechanisms
- Network — Who’s Doing All This Stuff?
Introduction
This man in the picture above is Ralph Merkle — a highly influential computer scientist who is also known as the father of modern public key cryptography. Not bad, eh?
Merkle turned out be an exceptionally smart man already early on — while still being an undergrad, he coming up with an ingenious concept known as Merkle Puzzle in 1974. His idea was groundbreaking and revolved around the question, how two parties can safely exchange secrets even if they have never exchanged secrets before, without anybody else being able to listen in on their exchange.
His solution to this problem was astonishing and works the following way. Let’s assume that the super secret spy Alice wants to communicate with the heroic insider Bob from Evil Corporation, who has an important piece of information that could save the world from eternal evil.
In order for Alice to securely communicate with Bob, she decides to use Merkle’s Puzzle. By doing so, she sends Bob thousands of encrypted messages who all contain a different key. The interesting thing about all of those messages is, that while they are encrypted, this encryption is not super duper difficult to break — it takes a couple of minutes for each message though.
Now, Bob chooses a random message out of the thousands that he received from Alice and starts to decrypt it. After 15 minutes his computer has decrypted the message and now he can see the key that was hidden inside. He now writes a message, uses the key to encrypt it and sends it back to Alice.
Since Alice knows which keys she has sent and which keys belong together, she can now easily find out which key, out of the thousands she sent to Bob, has been chosen by him. From now on they both can easily communicate with each other — and any possible hacker or malicious party would have a very hard time of figuring out what’s happening. Why?
Well, in order to understand their encrypted messages, the hacker would need to decrypt all of the thousands of messages sent (which would require enormous amounts of processing power) and check every possible key with the messages.
So far, so good — Merkle’s Puzzle was an early idea for a public key environment. If you want to read more about Public Key Cryptography, check out this post:
Like this groundbreaking idea hasn’t been enough, five years later he and his college Ivan Damgård came up with another innovative concept known as the Merkle–Damgård construction, which he published as his PhD thesis in 1979. This idea is also known as a cryptographic hash function and plays a big role in Merkle Trees. But more on this later.
In the same year, he published his paper “A certified digital signature” — this idea became known as Merkle Trees.
Let’s see what it describes:
“The invention comprises a method of providing a digital signature for purposes of authentication of a message, which utilizes an authentication tree function of a one-way function of a secret number.”
Say what?
No worries, in this post we will dissect the different aspects of this and by the end you’ll have no problem understanding what Merkle Trees are and why they are incredibly important!
His idea revolved around a new and highly efficient way to create digital signatures or proofs. By using his idea, we now have a very practical way of efficiently summarizing large sets of data and verifying their integrity.
Before we get into the nitty gritty details of this, we need to recap one important building block of his idea — hash functions.
Hash Functions
Hash functions, if broken down, are very straightforward and easy to understand.
A hashing algorithm takes an input (this can be literally anything), runs it through some magic mathematical processes and then creates a unique output (called a hash).
What makes hashing algorithms so incredibly useful, is the property that the slightest change in the input completely alters the output. This property is what makes hashing algorithms so powerful — because they can be used to validate data and detect even the slightest change to them.
Ralph Merkle came up with a fundamental idea in this area as well — remember the ominous Merkle–Damgård construction that we talked about earlier?
Cryptographic hash functions are a special class of hash functions that at the first impression sound quite intimidating, but they are actually quite easy to understand. These special hash functions serve a very important purpose in the field of cryptography and are widely used in online payments, the HTTPS protocol and , you guessed it, blockchain technology.
These hash functions have a couple of very important characteristics, listed below:
Deterministic: for the same input you will always get the same output.
Quick computation: they can be quickly computed (no brainer).
Pre-Image Resistance: it is infeasible to to determine the input through the output.
Every change in the input changes resulting hash: indispensable for immutability of records.
Collision Resistant: it is infeasible for two inputs to have the same hash.
Puzzle Friendly: its infeasible but not impossible to deduce a certain input
If you want to deep dive into this topic, I highly recommend you to read this complementary post:
One of the most widely used cryptographic hash functions is the SHA256. The SHA is an acronym for Secure Hash Algorithm and the 256 relates the number of bytes that are produced as a result. These 256 bites will be always represented as a 64 character number, no matter how big (all of wikipedia) or how small (just one letter) the input is.
Now that we know what hash functions are, especially cryptographic hash functions, we are ready to look at these mysterious Merkle trees.
Merkle Trees
Don’t be intimidated by the looks of this beauty above! What you can see there is a lovely Merkle tree. The hashes at the very bottom are called leafs, the hashes above them branches and last but not least, we have the root at the very top.
As already stated above, this idea lets us very efficiently summarize large sets of data and verify that a specific data block is part of the larger data set.
How so?
Well, we take all the bits of data (e.g.transactions) and pair them — if its an odd number, we simply take the last remaining one and pair it with itself . Then, all of the individual transactions are run through a hashing algorithm and added together. This process continues until we’re left with one final hash — which is also known as the Merkle root.
The unique nature of hashes, that even the slightest change in the original input completely changes the output, is what makes this idea so incredibly powerful.
Changing one of the original leafs (e.g. individual transactions) would lead to that particular hash being altered — this in turn would alter all the other hashes up to the Merkle root. This allows for an easy verification of the validity of the complete database.
In the picture above we only had a very small Merkle tree, the real power lies in the magic this concept can work in bigger databases, like the one below.
Let’s assume that you want to check if a certain piece of data is valid and has not been altered — for example K.
It would be a real hassle and computational effort to check every single piece of data in the database above. Merkle trees enable us to do a nice short cut now — we only need 4 pieces of information, instead of checking the whole tree (L, IJ, MNOP and ABCDEFGH).
We start by seeing if the hash of K and L give us the right hash KL. Then, cascading our way up, we continuously check the corresponding hashes all the way up to the Root. If the original piece of information was indeed valid and has not been altered, we should end up with exactly the same root hash.
And voila, instead of checking every single piece of data, we could get the job done way faster.
This ingenious concept gives us three very useful applications:
- We can easily prove the integrity and validity of data contained in a database.
- It requires only little memory or disk space — since we have only the hashes of all the data, it is computationally easy and fast.
- In order to verify the integrity and validity of data, only tiny amounts of information is required to be transmitted.
Now let’s see what role Merkle trees play in the context of blockchain technology.
Application in Blockchains
Before we explore why Merkle trees are an essential part of blockchains, it’s important to understand how blockchains are actually composed.
Blockchains are basically recording changes in the state of a network — changes that happen when transactions take place, smart contracts are triggered, etc.
All these state changes are bundled into blocks — in the case of Bitcoin roughly every 10 min and in Ethereum every 12 seconds. These blocks are structured roughly like in the graphic below.
All these blocks have a so-called block header. There are six different values that are stored here, for now the only one we care about is the Merkle root though, which is called Tx_Root in the graphic above (Tx = Transaction).
The are hundreds of thousands of blocks each possibly containing thousands of transactions. In order to verify all transactions happening, a huge amount of processing power would be needed if computers would need to query and search the whole database each time they want to validate that a certain transaction has happened. Why do we even need to know if certain transactions happened?
Well, if you own one Bitcoin (Ethereum employs a different model), you actually don’t really “own” that specific token as one whole unit. Rather, you have a right to so-called unspent transaction outputs (UTXO). We won’t go in-depth here, for now it’s simply important to understand that the tokens you want to spend might have been transferred to you n-number of blocks ago, so in order to verify that you really have the tokens you say you have, the computer needs to be able to go back and search for a block in the past.
Every transaction has an ID, which is a 64 character code that takes up 32 bytes of memory. If we now think of the thousands and thousands of transactions that a computer would have to search through in order to validate one transaction, it would be extremely processing intense and inefficient.
While blockchains would be technically possible without Merkle trees, they nevertheless play an essential role when it comes to ensuring integrity and efficiency. By applying the Merkle magic, all the transactions that are included in one block are now easily verifiable.
Let’s take the visual below as an example (if you click on it, it becomes bigger).
In it, you see all the transactions that are repeatedly hashed and together make up this magnificent Merkle tree.
If we need to verify if a certain transaction happened (and you thus have the Bitcoins you claim you can spend), we simply need a couple of infos. Apart from the block number, we simply need the corresponding hashes and can easily verify that the transaction 8 is indeed included in that block.
Merkle trees enable another really cool feature of blockchains. Nowadays, a copy of the whole blockchain in the case of Bitcoin amounts up to ~ 184 gb. This size makes it impossible to carry around on a mobile phone or many computers.
In order to still be able to interact with the blockchain and to engage in transactions, so-called Simplified Payment Verification clients make use of Merkle trees. Since we don’t need that many informations in order to ensure integrity and verify certain transactions, by using Merkle trees we can also use Wallet applications from our phones! (We’ll cover this topic in a future article)
While most Merkle trees are of a binary nature, Ethereum uses a special type of Merkle tree with three inputs, called Patricia trees (or also tries). If you feel like, you can read more about it in this intriguing article by Vitalik Buterin.
Wow, you’ve made it all the way to the end — I hope that you’ve enjoy the read and in case you have any questions or feedback, please let me know, I’d love to hear from you.
All the best
Till
PS: If you’re looking for helpful and great resources to learn more about blockchain’s paradigm shifting technological potential, check out these awesome resources.
