Math behind blockchains. Part 2 - Proof of work and nonces

You've probably come across terms such as

Hash functions

Proof of work and nonce

Public/private keys, signatures, and cryptography

during your blockchain explorations. In this article, we will explain all of these terms. Here is all math you need to know to understand the inner workings of blockchains.

This is part 2 of 3. For other parts see below.

Hash functions →

The math and intuition behind hash functions

How can the private key serve as both, the username and password? →

Crash course on cryptography and digital signatures

How proof of work is implemented using hash functions and a nonce

You've probably heard about proof of work. This mechanism requires us to exert work by our computers. And there is no way to cheat or avoid performing this work. It's the backbone of blockchains such as Bitcoin and it's what prevents the double-spend attack.

If miners want to add a block of transactions to the blockchain, they need to perform work on these blocks in order to add them. Under the hood, proof of work requires computers to solve a difficult math puzzle about the blocks. And this is what makes the work unavoidable. You can't guess the answer to the puzzle.

The only way to solve the puzzle is by calculating math operations on your computer. And only after your computer has solved this puzzle, the network allows you to add a block to the blockchain. The answer to the puzzle serves as the proof that you did the work.

What does the puzzle consist of?

The math puzzle

The puzzle consists of finding a number (called nonce) such that when you append this number to the block of transactions, the hash of the entire thing starts with a certain number of zeros.

We will explain a simplified version of this:

Imagine we have a block of transactions:

We can think of this block of transactions as a big piece of text:

We can now use the hash function from Part 1, to map this piece of text to a short hash (the summary). Thus, the hash function allows us to convert a block of transactions into a short hash. (Hash is just short text).

ContentHash value

idaeacchi

A requirement

Now, let's add a requirement. The hash needs to begin with 5 d's (ddddd).

Not all inputs will satisfy this requirement. Some will map to a hash leading with ddddd, others will not.

Remember the hash function acts like a random function. It's impossible to guess which inputs will map to a particular output. It's irreversible.

What if we want to make any block of transactions satisfy this requirement? It might seem impossible but what if we are allowed to add some text to the end of the block of transactions and take the hash of the combination?

ContentHash value

geffdafih

Nonce

This text that's added to the end is called nonce.

Can we pick the right nonce so that our requirement is satisfied? Yes, we can. If we keep trying different values of nonce, one of them will eventually satisfy this requirement.

Here is the nonce that satisfies the requirement for this particular block:

ContentHash value

dddddcegb

How did we find this nonce: 1152203? By trying out a lot of random nonces until we satisfy the requirement. Try out the search in real-time below by clicking the "Start nonce search" button.

ContentHash value

idaeacchi

Hash pattern

Proof of work

The work that we did - picking a random nonce and taking the hash until the hash satisfies our requirement.

Nonce - serves as the proof that we did the work. It's the proof because there was no other way to find the nonce other than exert the work. You couldn't guess the nonce. If you found the nonce, that means you performed the necessary work to find it.

Intuition

Since hash functions are quickly verifiable but impossible to reverse engineer, it's fast to verify whether a nonce satisfies our requirement (hash value starting with ddddd), but it's hard to find the nonce itself.

The only option is the random search. And thus, the time it takes to find the nonce is also random.

You can think of the nonce as a jigsaw puzzle. Hard to find (hard to solve), but once it’s found, very easy to verify. Jigsaw is much easier to verify (check that the solution is correct) than to solve.

This might seem like a contradiction to the statement that hash functions are irreversible. Because we are in fact reversing the hash function: given desired output (hash value starting with ddddd) we are able to find the necessary input to produce the desired output. However, we will need a lot of trial and errors to find the suitable input. That's a lot of time. In Part 1, we learned that it will take unpractical amount of time to reverse a hash function. But, how can we make picking the nonce practical? How can we do it in a relatively fast way? The answer is, instead of requiring an input to produce a certain output, we require it to produce a range of outputs which is a much easier task. It's much easier to find the one-of rather than the exact one. (The one-of being one of hash values starting with ddddd, which there are a lot of) For the illustration above, we accelerated the search by making the task easier. In practice, it takes around ~10 min to find the nonce in the Bitcoin blockchain. We can make this task harder by requiring the hash to start with 10 d's instead, which is a much harder task and will take longer

Blockchain Course

Summary

When you want to add a block of transactions to the blockchain, you need to provide proof of work.

The work=find a nonce such that when the nonce is appended to the block, the hash value starts with a certain number of zeros.

Proof=the nonce is the proof because the only way to find it is by doing the necessary work.

Each block will require a different nonce, because the output of the hash function changes very unpredictably even if the input (the block of transactions + nonce) changes slightly.

In the illustration above the nonce was found pretty quickly. But I made it fast on purpose just for educational purposes, so that you don't wait for it. In the Bitcoin blockchain, blocks are mined on average every 10 mins. Which means it takes around 10 mins to find the nonce for each block. But what happens if computers get faster? Does it mean the blocks will be mined faster? Not really, Bitcoin blockchain has a built-in mechanism that adjusts the difficulty of the requirement frequently (more on this in the "Genius of Satoshi" section). So if the Bitcoin blockchain detects that miners are mining blocks quicker than 10 mins, it will increase the difficulty so that it takes longer to find the nonce. Remember, we can make the difficulty arbitrarily hard by requiring the hash to start with 5 d's instead of 3. This is a more difficult task so it will take longer to find the nonce satisfying this new requirement.

Hash functions →

The math and intuition behind hash functions

How can the private key serve as both, the username and password? →

Crash course on cryptography and digital signatures

Also, you can learn everything about blockchains in my course:

Blockchain Course

Contact me