What is Proof of Work? Crypto 101

What you need to know:

  • Proof of Work is a solution to the so-called Byzantine General’s Problem.
  • The Byzantine General’s Problems describes the difficulty that distributed computing systems have in reaching a consensus when communications channels are unreliable.
  • Proof of works solves the problem by requiring a significant amount of computing power to find a valid hash for each message through a process called mining.
  • An attacker would have to have more computing power than the rest of the mining network to produce a succesful attack.

Have you ever wondered what makes Bitcoin so special?

Or perhaps you have heard the term Proof of Work and wondered what it means?

Proof of Work Meme

Proof of work is one of the key measures underpinning Bitcoin and most other cryptocurrencies. This post will explain what it all means.

Byzantine Solutions

Bitcoin was designed by the mysterious Satoshi Nakamoto as a proof-of-concept for a solution to a previously unsolved problem in distributed computing called the “Byzantine General’s” problem.

The problem describes a group of Byzantine Generals who have encircled an enemy city, each commanding a portion of the Byzantine army, and each trying to decide whether to attack or retreat. Only a coordinated, simultaneous action (either Attacking or Retreating) would be successful, an uncoordinated action would be disastrous as anything less than the army’s full strength would be insufficient to storm the city and a retreating army at less than full strength could also be effectively routed.

Each general must cast a vote on the correct course of action and send it to each of the other generals. As the armies are spread out, communication is difficult, and the decision must be relayed via messengers. However, the messengers could get captured by the enemy city, which may replace them with new messengers with different messages to disrupt the coordinated attack.

The Generals must send some messengers across enemy territory, where the chances of getting caught are very high.

Can’t we just hash this out?

How can this problem be solved? Imagine that the Byzantine Generals own modern computer which allows them to use hash functions. A hash function is simply a function that receives a string of words and generates a seemingly random 64 alphanumeric number (called a “hash”).

For example, if I input a string such as “LET’S ATTACK ON WEDNESDAY” the function will generate the hash bee215a407b438cc74511780049e8013fa1b5d0136840bd71e912b20363f585e. The key to hash functions is that the same string will always generate the same Hash.

You can actually check this by using an online hash function calculator and checking that “LET’S ATTACK ON WEDNESDAY” will always generate the hash

So the Generals agree that for a message to be valid, the hash of the message must start with a fixed number of zeros (let’s say eighteen). To do this, they append a random number to their string (called a number only used once or nonce) so that “LET’S ATTACK ON WEDNESDAY 7dfh6r7f7w” generates the hash 000000000000000000fbf4c8996fb92427ae41e4649b934ca495991b7852b855 (this hash is completely made up, and you’ll soon understand why).

There are two characteristics about hash functions that make them great for this sort of task. The first is that there is no easy way to know which string will generate which hash. The only way to find which string will generate a hash that starts with a fixed number is to guess over and over again.

If you want to know how hard it is to generate such a hash, may I suggest you try coming up with a string that generates a hash starting with eighteen zeroes? Go on, I’ll wait…

Did you give up? I can’t blame you. It is estimated that the Bitcoin network currently has to make almost one octillion computations or guesses to find the appropriate nonce for a Block. That’s one followed by 30 zeroes! If it took you 10 seconds to make a guess, that’s still 31 million trillion years to find the nonce!

Modern computers excel at this type of repetitive task, and they would take only a couple of hours to guess the appropriate string.  Custom-made mining rigs are even more efficient, and they can find nonces in minutes. In fact, the combined computational power of the Bitcoin network allows them to make 10,000 quadrillion guesses every second! Of course, modern Bitcoin facilities are massive computer warehouses like the one below:

The other great thing about hash functions is that they only work one way, meaning that given any Hash, it is impossible to know which string generated it.

What is proof of work?

So the generals start appending the nonce to their messages (such as “LET’S ATTACK ON WEDNESDAY 7dfh6rhas86as97as097f7w). Although it was very difficult to come up with the correct nonce, it is very simple to check if the string and nonce generates the correct hash.

The generals now have a way to send messages which can’t be easily tampered with, as even if the enemy city intercepts the messengers, and even if they also have the same computers, it would take them a couple of hours to modify the message. If the generals send a couple of messengers each carrying the same message, the time it takes to modify the message ensures that at least one messenger with an untampered message will get to the other messengers before the enemy city is able to send a tampered message.

Let’s take things a step further. Let’s give the enemy city a supercomputer which can outperform the General’s puny computers. Let’s also assume that there are thousands of generals trying to lay siege to thousands of cities, all at the same time. The generals could then group their messages (we will call groups of messages “Blocks” from now on) and pool their computer’s hashing power to find the appropriate nonce.

Although it is very difficult for a single computer to guess the correct nonce, once one computer in the network has found it is very easy to share it with the rest of the generals, and everyone can validate that the correct nonce has been found in seconds.

As long as the combined computing power of the generals exceed that of the cities under siege, the odds will be strongly stacked in their favor. This is what proof of work is all about.

So what does this have to do with Bitcoin?

Its time to go back to Bitcoin. Have you ever wondered why somebody just can’t Copy Paste Bitcoins and make themselves rich?

The answer is the Blockchain. The Blockchain is essentially a public ledger where anyone can see who owns Bitcoins at any moment in time. The key to the Blockchain’s security is that Blocks containing new transactions will only be added if they contain the nonce that generates a satisfactory hash, proving that a significant amount of processing power was spent in figuring the nonce. That is Proof of work in action!

How does this all work in practice?

Let’s say I have one Bitcoin and I want to duplicate it by sending it to different people at the same time. I send two transactions, one where I send my Bitcoin to Bryan to purchase an online good and another where I send the same Bitcoin to Gregg to purchase another online good. For simplicity’s sake, assume I’m trying to buy very expensive digital books. This is what is known as a “double spending attack”. Let’s assume I also have a state-of-the-art mining rig to help me with my fraud.

What happens next?

Both transactions enter the mempool, which is a midway house of sorts. There they sit until they are picked by a Bitcoin miner, grouped into a Block, and mined. Mining is simply the act of finding the nonce for the Block which generates a satisfactory hash. After a Block is mined, it is added to the Blockchain.

Now, my two transactions aren’t the only two transactions waiting to be confirmed. The mempool contains at any one-time thousands of transactions. You can check the size of the mempool here, which is the aggregate of all transactions. A transaction is on average 495 Bytes and a single Block can contain 1,000,000 Bytes (1MB) worth of transactions.

So back to my attack. I first wait for someone else to validate one of my transactions. After a couple of minutes, the first transaction is confirmed, Bryan receives his Bitcoin and sends me my online book, I then furiously set my mining rig to mine the second transaction. Since it’s a powerful standalone rig, it takes it about an hour to mine the transaction. What happens next?

Well, a couple of things. Since the Blockchain’s ledger recorded an hour ago that I already sent the same Bitcoin to Bryan, I have to go back and insert my fraudulent Block before that Block and all Blocks validated by honest miners after that. I would then propose an alternate Blockchain to the rest of the network.

Here is where my con fails. The network will only recognize the longest Blockchain as the valid one. So I would have to generate a longer Blockchain than the existing one. That means that my puny individual mining rig would have to out-speed the entire Mining network, finding the proper nonce for the Block containing my fraudulent Block and all Blocks after that! And so, the second transaction is never recognized as valid and my plan is thwarted.
Therein lies the power behind proof of work. Any would-be attacked has to have at his disposal greater computing power than the rest of the combined miners.

Of course, it is not inconceivable that someone with malicious intent could acquire that amount of computing power. This is what is known as a 51% attack. However, that would require a significant investment in the Bitcoin network. And who in their right mind would try to undermine a system in which they have made a significant investment?

Follow us on twitter @cryptoiscomin

Subscribe to our newsletter to get the coolest infographics and articles from the crypto world