Hash functions

Part 1 of Math and Cryptography behind Blockchains

In this article, I will explain what hash functions are, the math behind them, and the intuition about them. The article will be divided into the following sections:

  • What they taught us in school
  • Example hash function
  • Intuition
  • Summary

An implementation of a simple hash function can be found on my blog here.

What they taught us in school

Before we learn about hash functions, let’s remember some stuff about regular functions from school. Here are various properties of functions.

Hash function is also just a function like the functions above. It also has its input, output. But its properties are a little more interesting:

  • Very non-smooth output. Even the smallest change in input can result in a completely different output. This function’s output jumps around a lot.
  • One way function (non-invertible).
  • The input and output are text.
  • The output always has the same length. Meaning the output text always has the same number of letters.

Example hash function

Here is an example of a hash function. On top, you have the input to the function (the content), and the output (the hash value) is below it.

For the interactive version, go here. (Try changing the content and check how the hash value changes)

Notice that the hash value always has the same length. And the smallest changes in the content can lead to completely random changes in the hash value. Here are some examples of content and how the hash value for the content changes:

  • Hash functions are used in Bitcoin → hafifcehi
  • Hash functions are used in Litcoin → bihbidbci
  • Ethereum → ijfjbchhc

Why is it called a “hash” function? The origin of the term “hash” seems to come from its non-technical meaning which is “to chop” or “to make a mess out of something”.

The hash function was named that way because it also scrambles its input to produce the output. The output looks nothing like its input.

The output of a hash function is usually called the “hash value” of the input. It’s also called the “digest” of the input.

Intuition

Hash functions summarize text

  • You can think of hash functions as functions that summarize text.
  • Given text of arbitrary length, they always produce text of short and fixed length — the summary of the input text.
  • Just like the other functions, given the same input, you will always get the same output from hash functions. This means, given the same input text, you will always get the same summary.
  • In addition, this summary is just one-way. Given the summary, you can’t reverse-engineer the input text.
  • Every input text results in a different summary.
  • Another way to think about it is that hash functions produce the fingerprint of the input text. The same input text will always map to the same fingerprint but it’s impossible to deduce the input text given just its fingerprint.

The summary is quickly verifiable but impossible to reverse-engineer

  • The summary is quickly verifiable meaning that if you have an input text t and someone claims that f(t) is the summary of that text, you can verify that claim by just passing your text through this function, i.e. by computing the output of the hash function.
  • But the summary is impossible to reverse engineer since hash functions are one-way.

Hash functions lock the content

  • Imagine you have some text. Like “Bitcoin will be top”. And you want to send it to your friend.
  • But you’re worried that someone might intercept it and send a slightly modified version of your text to your friend. Imagine if someone changed “top” to “flop” (Bitcoin will be flop). That would be a disaster!
  • How can you send this text to your friend knowing that it might be intercepted?
  • Well, you can compute the hash value of your text and store it somewhere. The hash value of “Bitcoin will be top” is bjcbicghc.
  • Now, you can send your text. When your friend receives your text, he will also compute the hash value of the received text. If it matches bjcbicghc, then that means that your text has not been tampered with. Otherwise, someone changed the text during transit.
  • This is because the hash function output is very non-smooth. Even the smallest change in the input can result in a completely different output.
  • So, hash functions lock the content in place. It’s impossible to change the content without affecting the hash value as well. The hash value is the lock.
  • This property of hash functions is used in checksums — when you download a file from a website, the website can provide the “checksum” (which is just another way of calling the hash value) of the file. After you download the file, you can pass it through the hash function and check that your computed checksum matches the checksum provided by the website. If they do, you downloaded the file safely. Otherwise, your downloaded file is corrupt.
  • In some scenarios, it’s also used in cloud storage to save space. Instead of storing the actual content (like a movie) which takes up a lot of space, you just store the hash value of the content, which is just a short piece of text. Later, when you need the content, you can pull it from auxiliary storage (like local storage), compute the hash value, and compare it to the hash value stored in the cloud. This way you can check for the authenticity of your movie, without actually storing the entire movie in the cloud.

Irrevertability (one-way property) of hash functions is not a strict statement. Hash functions can be inverted by brute force. If we are given desired output, we can find the suitable input to produce the desired output (thus invert the hash function) by trying out a lot of different inputs and hoping to find the input that produces the desired output.

But this will take a lot of time. How big is ‘a lot’? More than the life of the entire universe using modern computers. So irrevertability of hash functions is just strict in practice (you can’t practically invert a hash function) but in theory, it is possible: just try out a whole lot of inputs until you find the one that produces the desired output.

Implementation

It sounds too good to be true, doesn’t it? How can such a function exist?

There is an example of how can such a function be implemented in practice on my blog here. But it’s not necessary to understand the implementation details in order to understand blockchains. You can get away by just understanding the high-level properties of hash functions explained above.

The actual hash function used in the Bitcoin blockchain is called SHA256. (SHA are the initials of the inventors and 256 is the variant of the function).

It’s a much more involved algorithm but it’s straightforward to understand for those who have a Computer Science background. See the article linked at the end of this section for an excellent overview of SHA256.

Summary

And that’s it! To summarize, hash functions are just regular functions that have the following properties:

  • They summarize any input text to a fixed-length summary, called the hash of the input.
  • The summary is non-smooth. Meaning, the slightest change in input will result in a completely different summary.
  • The function is one-way. Meaning it’s impossible to compute the input text given just the summary.
  • The summary is quickly verifiable but impossible to reverse engineer.
  • Hash functions lock the content and make it unmodifiable.

That’s all a hash function is, just a regular function that has all these properties. Nothing else, nothing fancy. Very straightforward.

Hash functions are used in a lot of different places. Some of the are:

  • Hash tables
  • Checksums
  • Cryptography ciphers
  • They are also used in blockchains extensively.

References

  • The hash function algorithm explained above is from this article.
  • SHA-256 Cryptographic Hash Algorithm
  • How SHA-256 Works Step-By-Step

If you’re interested in learning more about blockchains, check out my blog.


Hash functions was originally published in DataDrivenInvestor on Medium, where people are continuing the conversation by highlighting and responding to this story.