What is the concept of "Proof of Work"?

With the media coverage of cryptocurrencies, NFTs and other products based on "blockchain"-type technologies, we regularly hear about POW verification.

POW stands for "Proof Of Work" (or "preuve de travail" in French).

To take just the most well-known example, Bitcoin, uses the concept of Proof Of Work for mining new blocks for instance, but what does this actually mean? Let's find out together!

Theory

In 1993, Cynthia Dwork and Moni Naor were looking for a solution to drastically reduce spam received through a network of email addresses, which was becoming critical.

They arrived at the idea of an asynchronous verification protocol, making things difficult for spammers, while keeping life easy for recipients.

This method is "Proof Of Work": the concept is to ask machines wishing to send emails to perform a computational task, as a way of showing proof of "motivation".

Like a captcha, but reserved for machines this time!

Let's imagine this in real life: Even if you are standing in front of me, I've decided to only listen to you if you find (without the help of a dictionary), a valid French word, containing 9 letters, starting with "g" and ending with "t".

There's a good chance you'll spend tens of minutes trying to find such a word, and if your message isn't of the utmost importance, you won't make the effort to perform this "calculation".

Yet, if you do find it, on my end, verification is very simple: I look at the word, I count the letters, I check the beginning and the end, and I agree to talk to you.

The theoretical concept of Proof Of Work therefore comes down to requiring a machine to make a computational/algorithmic effort, while making verification effortless!

Putting it into practice

Let's go back to our Bitcoin example. This famous cryptocurrency uses proof of work as a consensus protocol for two distinct tasks:

• Mining new blocks (creating new "coins")
• Validating existing transactions

A consensus protocol allows a set of nodes in a decentralized system to reach agreement.

And in this case, agreement on the veracity of the data, in case illegal data has been injected.

When one of the machines has found the solution to the problem posed to create a new block, for example, all the other machines on the network can instantly validate the result.

The Proof of Work protocol prevents it from simply being the number of machines that tips the balance, but also computing power and involvement in the network.

This makes it more difficult for malicious machines to gain access, since the return on investment of an attack becomes unappealing.

The PoW algorithm behind Bitcoin

I've given you a simplified version of a theoretical algorithm with a word to find at the beginning of this article, but you'll see that the real algorithm isn't so far off, just more "computer science" and "cryptographic".

This algorithm is commonly called "HashCash", the name of the first project in which it was implemented, and it is based on the "SHA-256" hashing method.

For a machine to validate a block, it must start from a string, and by adding a number to this string (called the "nonce"), make the SHA-256 hash of the result start with four zeros, for example.

Which would give:

• Base string: "Hello, world!"
• We add the integer: "Hello, world!0"
• The hash of the string+nonce: "1312af178c253f84[...]ec81976192e2ec934c64"

Does this hash start with 4 zeros? No, so we keep incrementing:

• "Hello, world!1": "e9afc424b79e4f6ab42d99[...]be78e948a9332a7d8"
• "Hello, world!2": "ae37343357a829759162e[...]32aa475cf05fd4266b7"
• ...
• "Hello, world!4250": "0000c3af42fc31103f1fd[...]7cc52ea464e12dcd4e9"

Bingo! The valid "nonce" is therefore 4250. All that remains is for the other nodes on the network to validate my result, and I will have validated a block!

Note that in reality, Bitcoin's PoW algorithm doesn't use a number of zeros for verification, but rather a target natural number that the hash must be strictly lower than, but the concept is the same.