How Proof Of Work works and why try to get rid of it?

We hear a lot about Proof Of Work and Proof Of Stake. And It’s hard to talk about Blockchain Platforms like Bitcoin and Ethereum without getting into mining.

But what is Proof Of Work? How does it work and how does it relate to mining? More critical: why are some projects trying to get rid of it?

The Need For Proof Of

In a Distributed Consensus Platform architecture, you find:

• Blockchain structures that prevent any data tampering
• peer-to-peer protocol to exchange data in a decentralized and public network
• Proof Of algorithms like Proof Of Work and Proof Of Stake. They give each member of the network some rules on how to choose and spread new states of the system.

Without the Proof Of Work algorithms, Bitcoin does not work:

Members of the network would propose new blocks ad nauseum and the system would grind to a halt. Going round and round without ever deciding on a SINGLE new block.

Twitch Plays Pokemon: Every member may propose a new move for the character. Participants have conflicting objectives (aka Trolls). The character wobbles.

The Proof Of Work gives each member a way to deal with a new block:

• Keep and broadcast it
• Ignore it

I described this as the necessity of Proof Of. Here we are going to dig into ONE of these algorithms: the Proof Of Work.

A solution to pick new block: Temporise their creation

If you can slow down the creation of new blocks, then you don’t need to choose between many blocks. Just keep the one you got. There is no risk of members flooding the system with a scarce resource.

But time is a fragile notion in a distributed system. Even more in a public network where members may cheat.

If we want to slow down block creation we have to do it by force:

A Mathematical Puzzle for 8 years old:

Let’s try out a simple game that’ll help us figure out the rest:

I pick a random number between 1 and 10. You have to find this number.

— Hum, is it 4? No, it is not. — 8? No. — 7? Yes! You Won!

You’ll need a few tries to figure out this number. On average, you’ll have one-tenth of a chance to find the answer on the first attempt. Then 1/9, etc.

You could try 1, 2, 3, 4, … or 10, 9, 8, 7, …. No strategy is better than the other because I pick the number at random. You don’t get any information except Successs / Failure.

This is a game where finding the solution takes some time. But it is easy to verify.

Round two: Another player joins. You collude with them: they pick Odd numbers, you will propose Evens numbers. Now, the “Players” have 1/5 chance to find the solution on the first round, then 1/4, etc. Players can find the answer twice as fast as before.

From the game master side, I can change the problem’s constraints:

Now I pick a number between 1 and 20

The probabilities are back to the original setup. The players have a 1/10 chance to find the number during the first round.

We can “resize” our problem to adapt to the players

Our game has a substantial weakness. There is a single game master that knows the solution. In the following, we’re going to decentralize this so that each participant work on their instance of the game.

PoW: A Decentralized Math Puzzle

Back to a Blockchain System. We care about these packets of data called Block. A participant wants to send a new block with the following payload:

ALICE SEND 1 BITCOIN TO BOB

They compute the hash for this block. It’s a unique cryptographic fingerprint:

SHA384("ALICE SEND...") = 3796601003deefd3662a8e...

This result is deterministic but acts like random: the only way to know what it looks like is to do the computation. And there is no relationship between two results.

There it is, some randomness to implement our previous game.

We’re going to add a constraint on this fingerprint:

I want it to start with 0.

I use hexadecimal here, which means that we would have a 1/16 probability to find a hash that starts with 0. For example:

ALICE SEND 1 BITCOIN TO BOB
NONCE=39

If we compute the hash of this block:

SHA384('ALICE SEND...NONCE=39') = 01c2c2e0e499a841e623e...

This Nonce is the “garbage” field that lets us produce different fingerprint without changing our payload.

When new participants join and start computing hashes, the network will find new solutions more often. To counter-balance this, we can change the constraints:

The hash of a block should start with 00. Then 000, etc.

Changing the difficulty changes the time it takes for the network to come up with a new block. Similar to our first game.

Each member computes the difficulty locally. But for their block to be broadcast by others, they have to follow the constraints picked by the majority. Hostile participant or not.

The properties of our previous game are back. In a decentralized way

Asymmetry

Looking for the Nonce is Mining!

Each miner is going to:

1. Accept transactions,
2. Accumulate these into a single block
3. Compute Hash.

The miner generates a Nonce. Compute the hash of their block. Generate another Nonce. Compute the new Hash. And so on.

Sometimes they find a gold nugget: a (payload, nonce, hash) tuple that fits in the network’s constraints. The miner sends this block to the rest of the system.

Finding a Nonce requires computing a lot of hashes, thousands, millions and more. But checking a block only requires a single hash computation. This check piggybacks on the Blockchain’s data tampering protection algorithms, which makes it virtually costless.

This asymmetry slows down the creation of new blocks despite hostiles members. It is easier to ignore a hostile member than to produce a toxic block.

Wastefulness

We slow down new blocks by force: each new block requires spending a lot of energy.

With every new miner, the network’s difficulty increases a little. There are millions of devices in a race to compute hashes that are useless: we only keep one.

Sadly, the “mining” analogy still holds: The Proof Of Work is the Coal-burning plant of the Blockchain ecosystem.

This fact is not the most persuasive argument against Proof Of Work though. A “regular” infrastructure consumes and wastes a lot of energy. Buildings need to be secured; security software needs to be maintained; etc.

Re-centralization

But you may already see the primary limitation of this method: The more energy you put into the blockchain, the more power you get over it.

Each member is incentivized to put in more energy to compute and verify more blocks. But computing power equals voting rights (generating blocks). So the more energy a member puts in, the more likely they can mess with the system.

Finally

We saw how the Proof Of Work… works: it is a mathematical game that relies on pseudo-randomness. It can slow down every member of the network to give enough time for each block to spread and become the new point of consensus.

But we also clearly see that Proof Of Work is wasteful. And much worse: it centralizes back the “brain” of the consensus towards conglomerates of miners. Hence the research for alternatives, such as the Proof Of Stake.