Before learning blockchain technology, it is inevitable to learn about hash function. A cryptographic hash function is a mathematical function.
A hash function can take any string as input, absolutely any string of any size. It produces a fixed-size output. In the content of crypto currencies like Bitcoin, the transactions are taken as input and run rough a hashing algorithm (bitcoin uses SHA-256) which gives an output of a fixed length.
Example
There are certain properties that a cryptographic hash function needs to have in order to be considered secure.
1. Deterministic
This means that no matter how many times you parse through a particular input you will get the same result. This is critical because if you get different hashes every single time it will be impossible to keep track of the input.
2. Quick computation
The hash function should be capable of returning the hash of an input quickly. If the process isn't fast enough then the system simply won't be efficient.
3. Pre-image Resistance
What pre-image resistance states is that given H (A) it is infeasible to determine A, where A is the input and H(A) is the output hash.
Suppose you are rolling a dice and the output is the hash of the number that comes up from the dice. How will you be able to determine what the original number was? It’s simple all that you have to do is to find out the hashes of all numbers from 1-6 and compare. Since hash functions are deterministic, the hash of a particular input will always be the same, so you can simply compare the hashes and find out the original input.But this only works when the given amount of data is very less. What happens when you have a huge amount of data? Suppose you are dealing with a 128-bit hash. The only method that you have to find the original input is by using the “brute-force method”. Brute-force method basically means that you have to pick up a random input, hash it and then compare the output with the target hash and repeat until you find a match.
So, what will happen if you use this method?
• Best case scenario: You get your answer on the first try itself. You will seriously have to be the luckiest person in the world for this to happen. The odds of this happening are astronomical.
• Worst case scenario: You get your answer after 2^128 – 1 times. Basically, it means that you will find your answer at the end of all the data.
• Average scenario: You will find it somewhere in the middle so basically after 2^128/2 = 2^127 times. To put that into perspective, 2^127 = 1.7 X 10^38. In other words, it is a huge number.
So, while it is possible to break pre-image resistance via brute force method, it takes so long that it doesn’t matter.
Property 4: Small Changes In The Input Changes the Hash.
Even if you make a small change in your input, the changes that will be reflected in the hash will be huge. Let’s test it out using SHA-256:
You see that? Even though you just changed the case of the first alphabet of the input, look at how much that has affected the output hash. This is a critical function because this property of hashing leads to one of the greatest qualities of the blockchain, its immutability (more on that later.)
Property 5: Collision Resistant
Given two different inputs A and B where H(A) and H(B) are their respective hashes, it is infeasible for H(A) to be equal to H(B). What that means is that for the most part, each input will have its own unique hash. Why did we say “for the most part”? Let’s talk about an interesting concept called “The Birthday Paradox”.
What is the Birthday Paradox?
If you meet any random stranger out on the streets the chances are very low for both of you to have the same birthday. In fact, assuming that all days of the year have the same likelihood of having a birthday, the chances of another person sharing your birthday is 1/365 which is a 0.27%. In other words, it is really low.
However, having said that, if you gather up 20-30 people in one room, the odds of two people sharing the exact same birthday rises up astronomically. In fact, there is a 50-50 chance for 2 people of sharing the same birthday in this scenario!
What is the application of this in hashing?
Suppose you have a 128-bit hash which has 2^128 different possibilities. By using the birthday paradox, you have a 50% chance to break the collision resistance at the sqrt(2^128) = 2^64th instance.
As you can see, it is much easier to break collision resistance than it is to break preimage resistance. No hash function is collision free, but it usually takes so long to find a collision. So, if you are using a function like SHA-256, it is safe to assume that if H(A) = H(B) then A = B.
Property 6: Puzzle Friendly
Now, this is a fascinating property, and the application and impact that this one property has had on cryptocurrency are huge (more on that later when we cover mining and crypto puzzles). First let’s define the property, after that we will go over each term in detail.
For every output “Y”, if k is chosen from a distribution with high min-entropy it is infeasible to find an input x such that H(k|x) = Y.
That probably went all over your head! But it’s ok, let’s now understand what that definition means.
What does “k|x” mean?
The “|” denotes concatenation. Concatenation means adding two strings together. Eg. If I were to concatenate “BLUE” and “SKY” together, then the result will be “BLUESKY”.
So now let’s revisit the definition.
Suppose you have an output value “Y”. If you choose a random value “k” from a wide distribution, it is infeasible to find a value X such that the hash of the concatenation of k and x will give the output Y.
Examples of cryptographic hash functions
• MD 5: It produces a 128-bit hash. Collision resistance was broken after ~2^21 hashes.
• SHA 1: Produces a 160-bit hash. Collision resistance broke after ~2^61 hashes.
• SHA 256: Produces a 256-bit hash. This is currently being used by Bitcoin.
• Keccak-256: Produces a 256-bit hash and is currently used by Ethereum.
That’s it with the properties of hash function, will learn about more in the next post…!