What is the use of Proof Of Work and Proof Of Stake algorithms?

The Ethereum project is in the process of getting rid of the Proof Of Work Algorithm. We’re going to see a Proof Of Stake algorithm running at a significant scale (Casper).

But what are these Proof Of Work and Proof Of Stakes algorithms? What are they used for exactly? And are they important?

In the three pillars of the Blockchain, I described the core components of Distributed Consensus:

• P2P protocols enable the creation of an organic network of machines. These machines can exchange data efficiently.
• Blockchain Structures allow each participant to ensure the Database’s integrity. They make it fast and easy to compare states, no matter the database size.
• Finally, Proof Of Work / Stake algorithms give the system a way to progress and converge towards a new state.

Imagine a system with NO Proof Of …

We have a network of servers connected through P2P protocols. These machines use Blockchain Structures to store and compare data.

• A user connects to one of these machines and submits an operation like “Send X Ethers TO Y”.
• The server checks the transaction, produces a new block an sends it to the network.
• Others servers receive this block, verify and accept it. Then they forward this block to the rest of the network.

Each participant broadcasts every new Block. It’s like a virus spreading.

But what happens when multiple users submit operations to different servers?

Each server receives a block and broadcasts it, from one machine to the next. They spread and some servers receive both Blocks.

The blockchain relies on the idea that we allow only a single CHAIN of events. These servers must make a choice:

• Keep the block I already know?
• Accept the new block?

“Keep the block I already know”
When a machine is contaminated, it never changes again, the system freezes.

“Accept the new block”
Each machine changes its mind whenever another participant sends them a block. The system oscillates and converges very slowly. Or it never agrees on a single Block.

In both cases, the network may never reach a consensus ever again!

Distributed System, Pre-Blockchain

What we have so far is a common model in Distributed Systems. We should allow a single leader to emit modifications.

In the case of Distributed System, this is a good enough solution. Having a single server responsible for changes is simple to implement and reliable. It spares us from dealing with concurrent modifications of the database.

But we need to trust all the members to agree on ONE leader. And we need to trust them to broadcast changes coming from the leader ONLY.

The keywords Leader Election and Master-Slave Replication signal this “semi-centralized” model. For example:

• Apache Kafka: “Each partition has one server which acts as the “leader” and zero or more servers which act as “followers.” The leader handles all read and write requests for the partition while the followers passively replicate the leader.”
• Apache Mesos: “If the Mesos master is unavailable, existing tasks can continue to execute, but new resources cannot be allocated and new tasks cannot be launched. […] Mesos has a high-availability mode that uses multiple Mesos masters: one active master (called the leader or leading master) and several backups in case it fails.”
• MySQL: “In this environment, all writes and updates must take place on the master server. Reads, however, may take place on one or more slaves.”

In a decentralized system, we cannot rely on the same algorithms. We do not know every participant; they may connect, disconnect, cheat and lie, etc.

That’s where we use Proof Of …

Methods like Proof Of Stake of Proof Of Work give each member of the network a “recipe” to accept blocks. This recipe allows each participant to take local decisions. They know which block to keep, which to broadcast and which blocks to ignore.

They are local rules that make the system converge globally to a new consensus. These algorithms enable networks such as Bitcoin and Ethereum to decide on a single block among the millions that may be submitted at any moment.

This is an introduction. Later we’ll dig deeper into each algorithm: Proof Of Work is a cornerstone piece of technology. And the Proof Of Stake is a clever way to reimplement leader election.

Photo by Laura Kranz.