Hash Function and Its Intuition
Hello Everyone, I am super motivated to contribute through the Medium with the philosophy, “ Knowledge Increases by Sharing”.
I recently completed my ConsenSys Developer Program in India. This was my first official touch point to the Decentralized World. The program brought beautiful people together and was amazing 6 weeks of intense work and learning from peers and assignments :).
In this post we will try to understand the Hash Function and its Intuition.
Cryptocurrencies, like any other currencies, needs some way to control supply and enforce various security properties using technology without any central authority. Cryptography provides a mechanism to avoid tempering of currencies, from equivocating and enable creation of new supplies via encoding the rules into a mathematical protocol.
The field of cryptography is deep research topic and the present article gives an overview of Cryptographic Hash function , which are very useful in block-chain field.
A hash function[1] is a mathematical formulation with following three properties
- Input can be any string of any size
- It produces a fixed size output , which user can be defined
- It is efficiently computable : given any size string it gives fixed output in reasonable time
Following are three additional properties which are critical for Hash Function to be useful in cryptographic secure function
- Collision Free:
It is infeasible to find X and Y which are distinct to produce the same hash.
Formal definition [1]:
A hash function H is said to be collision resistant if it is infeasible to find two values, X and Y, such that X != Y, yet H(X) = H(Y)
Note that : it is not impossible to find the collision, if we choose randomly just 2¹³⁰ + 1 inputs, it turns out there’s a 99.8% chance that at least two of them are going to collide. [1]
Let’s quickly check the hypothesis : it is not feasible to find collision, suppose we have a function which is capable of calculating 2³⁰ Hash/Sec.
Let’s us take cryptocurrency which has 256 bits as private key.
Total combinations to be tested is 2²⁵⁶ [2]
Assume we have a machine which is capable of doing 2³⁰ hash operation per second hence total time required is 2²²⁶ second
Suppose we have processing farm made of 2³⁰ computers and total time required by computers in each farm 2¹⁹⁶ second
Suppose we have 2³⁰ such farms all over world and total time requires by these farms 2¹⁶⁶ second
Assuming we are lucky to get the collisions at 50% of combinations and total time is 2¹⁶⁵ second
1 year = 2³⁵ seconds
Overall we would require 2¹⁶⁵/2³⁵ = 2¹³⁰ years
To our best knowledge the age of universe is 2³⁴ years and am not sure how many atoms are there in the universe. Thus we validate the hypothesis that it is in fact infeasible to find collision.
This is kind of general but impractical algorithm to find a collision for any hash function.
We safely assume that the hash function; H(X) = x mod 2²⁵⁶
is a collision resistant or there is infinitesimal chance to detect it.
One of the use case for this property is message digest.
Get AMIT BORUNDIYA’s stories in your inbox
Join Medium for free to get updates from this writer.
Hash can be used as the message digest: if H(x) = H(y) then it is safe to assume x==y; this can be used to validate the data sanctity of the files or files were tempered or not.
2. Hiding:
The property states given H(X), there is no feasible way to find X.
One of the challenge is if X is chosen from small spread set, there is a possibility to find X in few steps. Example the flipping of coin. To avoid finding the X in few steps , choose X from a very spread out set, this will make it difficult to find X.
Normally, the wider spread X is not always guaranteed and one solution is to concatenate X with another input, say r, which we chose from a wide spread set i.e. wider distribution, thus guaranteeing the input to hash function is wider distribution set.
Formally[1]:
A Hash function is hiding when a secret value r is chosen from a probability distribution that has high min-entropy , then given H(r||X) it is infeasible to find X .
min-entropy is measure of predictability and hence high min-entropy is very low predictability i.e. choosing from wider distribution.
Example : if we choose r uniformly from all strings that are 256 bits long, then any particular string was chosen with probability 1/2²⁵⁶ , which is an infinitesimally small value, making it candidate for set of wide spread.
The application for the hiding property is Commitment scheme
1) Com := commit(msg,nonce) : where nonce -> secret random value
2) Verify (com, msg, nonce): true if ( com==commit (msg, nonce) ) or false otherwise.
To use this, we need to create a random nonce and create commitment com and publish it.
To reveal the value that was committed earlier, we can release the nonce value used to create the commitment, this way anyone can verify the msg was indeed committed earlier.
3. Puzzle Friendliness:
Suppose we need to find y — the output of hash function- and there is input which is randomly chosen from set of wide spread, it should be difficult to find another value that is exactly like y.
This might sound bit complicated let us try and see the application of it called the search puzzle.
The search puzzle consists of
· A hash function
· A value, say r chosen from set of wide spread
· Target Y
i.e . H (r || X) ε Y
Solving this puzzle is to find X such that Y falls within a limited set.
The size of Y determines the how hard the puzzle is i.e. Y = Universal set this is trivial to solve and if Y =1 element set this is maximal hard.
One thing to remember since r is chosen from wide spread this will ensure there are not many alternatives to solve except the brute force mechanism. This means we can keep trying with all randomly chosen value X.
This is the idea the miners used when they mined.
In the next article I will deep dive into the Hash Pointers .
Credits :
“Bitcoin and Cryptocurrency Technologies”[1] ,
ConsenSys course material [2]
Endless discussions in the class with peers (which I can recollect) and with danielnovy our instructor at Developer Program.
