Why isn’t Ethereum on Proof-of-Stake already?

Published in

IBBC.io

18 min readDec 22, 2018

Since a few years, Proof-of-Work has been the object of all critics: “PoW is not scalable, PoW is wasteful, PoW will destroy the planet!” In order to solve these problems, Proof-of-Stake (PoS) is supposedly the miracle solution. Every new altcoin on the market now boasts to be running on PoS in order to overcome the big guys’ (Bitcoin, Ethereum) limitations. PoS is not completely new however, and discussion about moving Ethereum to PoS have been running since at least 2014. How come that we are not there yet and that the two most prominent blockchain projects are still running on the lousy PoW?

PoS is very complicated

The obvious reason why Ethereum is not powered by a PoS consensus yet is that it is exceedingly difficult. We will try to explain here why.

The general question that PoS tries to answer is the following:

Can we achieve the same level of security as a Proof-of-Work (PoW) system while not depleting physical scarce extrinsic resources to do it?

The designers of such a consensus algorithm mainly face these following challenges:

Nothing at stake
Long Range Attack
Cartel Formation

Nothing at Stake

Proof-of-Work requires the consumption of a resource external to the system (electricity for computation, buying ASICs, …). When “working” to contribute to the blockchain a miner must choose which of all possible forks to contribute to and the different options are mutually exclusive. Double-voting (working for multiple forks in the blockchain) is a suboptimal strategy since it requires you to split your mining power among the different votes (Cf. figure 1). The optimal strategy is always to put your mining power exclusively on the fork that you think is most likely to win. This also accounts for double-voting where the second vote is made many years after the first.

Fig 1. In PoW, the optimal strategy is to mine for the branch that you think will prevail. (Figure courtesy of *[1]*)

With proof of stake, the situation is different, as your voting power doesn’t depend on a consumption of a resource external but based on your stake of a resource internal to the system. Voting becomes thus virtually free. A “naive” version of proof of stake copying PoW functioning by making stakes a virtual mining rig with a certain chance per second of signing a block, have a fatal flaw: if there are multiple forks, the optimal strategy is to vote on all forks at once (Cf. figure 2). This is the core of “nothing at stake”.

Fig 2. In the naive implementation of PoS without slashing, the economical optimal strategy is to double-vote. (Figure courtesy of *[2]*)

Voters can indeed vote for multiple conflicting blocks at a given block height and thus legitimate 2 branches without incurring any cost for doing so. The economically optimal strategy becomes voting on as many forks as you can find.

The widespread answer to this is to put to the amount of capital staked (that gives its voting power to the node) at risk in case of misbehavior. This in-protocol penalty is also known as slasher. The goal is to re-create under a different form the penalty of double-voting so that it is optimal to vote only for one branch. However, compare with a priori external work, on-chain penalties are much more complicated to enforce.

Long Range Attack

A long range attack is a scenario where an adversary creates a new branch on the blockchain starting from the genesis block and tries to overtake the main chain.

Long range attacks are possible because of what we call weak subjectivity. This is the idea that a new node joining the network (or back online after a significant time offline) cannot purely “objectively” tell the main chain among all the potential branches published by the nodes of that blockchain.

PoW is immun to such issue. The longest chain rule in PoW is enough to counter it as it would require a tremendous computational power (and thus financial) effort to reach the length of the main chain with a side chain. A new node coming onto the network with no knowledge except (i) the protocol definition and (ii) the set of all blocks and other “important” messages that have been published can thus independently come to the exact same conclusion as the rest of the network on the current state (objectivity).

This is not the case in PoS because of the notion of costless simulation. In PoS the computational power used to validate the blocks is not significant. The cost of generating a block is thus costless in the off-chain world.

Because of this (otherwise amazing feature), the longest chain rule is challenged under PoS.

There are different forms of long range attacks. The currently known ones are:

Simple long range attack.
A Posteriori corruption: Use private keys of nodes that staked out (and thus have now nothing-at-stake) to counterfeit old blocks and try to outpace the main chain.
Stake bleeding. The attacker “stalls” the main chain as much as he can (every time he is elected to publish a block on the main chain) and publish as many block as possible in the alternative attacker chain (copying transactions off the main chain) to maximize his stake in this one. This strategy will eventually give the attacker the majority of the stake on his branch and will start expanding faster than the main chain.

Cf. [3] for more details about long range attacks.

Cartel Formation

Cryptocurrency is currently incredibly concentrated. This means that, for most crypto-currencies, very few actors possess a major share of the voting power (mining power, share of staked coins, …). This represents a danger because it is easier for few wealthy/powerful actors to agree on a pact than for many poorer spread out actors. How do you make sure these few wealthy actors in the system don’t form a cartel? Cartel of this sort is to be absolutely expected and a proper blockchain architecture should be designed for this kind of oligopolistic market.

It is to be noted, that this issue impacts also PoW systems. Indeed, cartels of 51% of the mining power of any Proof-of-Work blockchain have a strong incentive to censor the other miners. Even though this major issue is not often mentioned, few projects in the space are exempt of this reflection.

PoS in the sense that it reinforces the wealthy with more block rewards is even more affected.

PoS raises multiple other concerns, questioning all fundamentals of the Blockchain industry from the technical, economic and other perspectives. All could not be treated in this paper.

One that worth be noted however is the fear that PoS would create an incentive to hoard the coins in order to stake them rather than put them in circulation.

PoS in the crypto-space

We saw that PoS is extremely complicated and is still a subject of active research and debate. If it hasn’t been fully cracked down yet (and maybe never will), how can all the altcoins (shitcoins?) in the crypto-space pretend to use it? As usual with distributed system, it is always about trade-offs. In this part, we will try to expose the common trade-offs accepted by the different class of PoS projects currently in the market and detail the pros and cons of such solution, without entering too much into details.

The two major tenets in Proof-of-Stake design are chain-based PoS and Byzantine Fault Tolerant-based PoS. Chain based PoS, such as PoSv3, simulates Proof-of-Work consensus, in that the protocol assigns the right to commit a single new block to a pseudorandomly-selected validator, where the new block is linked to a parent block of the previously longest chain. BFT based PoS on the other hand, proposes a radically different approach to solve the consensus problem.

PoS v3 (QTUM)

Qtum is built upon “Proof-of-Stake Version 3”. This type of Proof of Stake (PoSv3) is built for UTXO based blockchains.

Side Note: UTXO stands for Unspent Transaction Output. The UTXO model was the first blockchain model, deployed as a fundamental part of how the bitcoin blockchain works. From the technical standpoint, bitcoins are more like receipts than actual coins. If Alice, a miner, finds a block, the system issues her a receipt (transaction) stating that she is owed (rather than she owns) N bitcoins (currently N = 25). This receipt is a single transaction and is currently unspent. Transactions can have two states: spent or unspent. When Alice goes to purchase a good or a service from Bob for 1 bitcoin, she will consume (spend) the 25 bitcoin transaction to create two new transactions. One transaction has Bob as recipient for the 1 bitcoin she owes him, the other transaction is to herself for the rest of the bitcoins (change).
This model is generally opposed to the Account Model. For certain applications, the account model is simpler than the UTXO model as it maintains a shared state across all the nodes using a database and the transactions simply update the shared database when needed. The account model is the one used by Ethereum.

In a PoW system, the block header is hashed along with a nonce to create a block hash which must be less than some target to “win” that block. PoSv3 instead has a kernel hash which is composed of several pieces of data that are not readily modifiable in the current block. The Kernel Hash contains, among other things, the current block time, with the bottom 4 bits set to 0 to reduce granularity. Thus the blocktime can only be represented in 16-second intervals. This is the only thing that varies across time during staking process.

Instead of a coinbase transaction in a PoW system, the Qtum PoS system has a coinstake transaction. A prevout transaction is the UTXO used to create this staking transaction. The only way to change the current kernel hash (and try to meet the target to mine a block) is therefore to change the prevout UTXO you’re using to create the block or change the current blocktime. Each UTXO can only be used once every 500 blocks (~24 hours) to produce a staking transaction.

The pseudo-code for finding a valid kernel hash is elegantly described in [4]:

while(true){ foreach(utxo in wallet){ blockTime = currentTime - currentTime % 16 posDifficulty = difficulty * utxo.value hash = hash(previousStakeModifier << utxo.time << utxo.hash << utxo.n << blockTime) if(hash < posDifficulty){ done } } wait 16s -- wait 16 seconds, until the block time can be changed }

This systems mimics fairly closely the way PoW functions but adapts the difficulty of mining based on the stake of the node.

Qtum deals with the nothing -at-stake problem with the so-called “Decentralized Governance Protocol” which manages how forks work on chain.

The DGP implements a decentralized and democratic governance system and allows blockchain parameters to be modified quickly and seamlessly without ecosystem disruption [5]. The details of this is still very fuzzy and not widely documented.

BFT-based PoS (Tendermint)

Tendermint is the first and most widely known implementation of a Byzantine Fault Tolerant (BFT) Proof-of-Stake consensus algorithm to the blockchain domain.

BFT-based PoS protocols pseudo-randomly assign a validator the right to propose new blocks during a multi-round voting process. Committing and finalizing blocks depends on a supermajority (>2/3 of the total voting power) of all validators signing off on the proposed block.

Currently Tendermint protocol selects block proposers deterministically. Given that you know the validators set and each validator’s voting power, you could compute exactly who the next block proposers will be in the next rounds. This is a serious point of failure for Tendermint as knowing who will be the next proposer, an attacker could launch a DDoS attack against him and potentially halt the chain from progressing.

Tendermint is designed under partial (or weak) synchrony. Weak synchrony means that it does rely on timing assumptions in order to make progress, but in contrast to synchronous systems, the speed of progress does not depend on system “hard-coded” parameters, but instead depends on real network speed (Cf. below for more details).

The current design underlying Tendermint really favors safety and finality over liveness (Cf. below for definitions): it is very likely that in the real world, the system will actually halt (and thus become useless), until the participants organize outside of the protocol to restart the system.

Delegated Proof-of-Stake (Steemit, EOS)

Variant of the typical PoS model, DPoS requires coin holders to vote for “delegates” (or witnesses), who are then responsible for maintaining the blockchain and are rewarded for it. Token holders thus delegate their rights to other participants who can then stake tokens on behalf of the small actors. Delegated Proof of Stake (DPoS) was proposed as a solution to incentivize small token holders to continue to participate in the system.

Definitions:

Block producers are responsible for creating and signing new blocks. They are limited in number, and are elected by the voters.
Block validators in DPoS refer to full nodes who verify that the blocks created by block producers follow the consensus rules. Any user is able run a block validator and verify the network.

If a block producer is found to be malicious, it is penalized as the token holders won’t vote for it in the next round and it will thus be removed from the list of trusted delegates.

DPoS clearly sacrifices decentralization for throughput (scalability) due to the low number of block producers. This tradeoff could be acceptable for some applications which would tend to favor scalability over complete security. However, for critical applications, such as the base layer, full decentralisation and securit is an absolute necessity.

DPoS raises many yet unanswered questions about governance and the risks asociated. These questions are extremely complex and go far beyond “simple” technical matters as we can learn from the debate between Vitalik Buterin [7] (who argues that witnesses in dPoS have incentives to form a plutocracy of cartels and bribe voters) and Daniel Larimer [8] in these articles.

Distributed Byzantine-Fault-Tolerance (NEO)

dBFT consensus is mainly represented by NEO and by the recently announced Binance Chain.

As in dPoS, DBFT relies on the elections of delegates by the regular coin holders. The same concern as in dPoS also hold here.

The current NEO consensus whitepaper can be found here.

Where is Ethereum concerning PoS?

As said earlier, PoS is nowhere new to Ethereum and the Ethereum foundation has been consistently researching for 4 years now. The switch (at least parital in the first place) to PoS is a major piece of its roadmap to scalability. However, contrary to most altcoin projects, Ethereum takes its time to thoroughly research the topic from a very theoretical standpoint, in order to build on strong foundations and avoid jeopardizing everything that has been built so far.

The 2 Caspers

In the past years the Ethereum attempts to shift to PoS have gravitated around 2 competing projects, Casper FFG (the Friendly Finality Gadget) and Casper CBC (Correct-by-Construction), with Vitalik Buterin and Vlad Zamfir respectively as leading figures.

Casper FFG

We won’t go in the details here as we already partly covered Casper FFG in the previous article:

Overview of Ethereum Scalability Solutions

Introduction to Ethereum's answers to the scalability challenge: Casper FFG, Plasma and Sharding.

medium.com

It is also still unclear to me if this idea of smart contract based Casper still holds and if research on Casper FFG is still on. Priority has apparently been given to the full more complex Casper implementation as an independent chain (CBC detailed next), supposedly because designed in such a way that integrating sharding (another critical step to scalability) would be much easier.

Casper CBC

The objective of this research lead by the Ethereum foundation is to theoretically define a family of “correct-by-construction” consensus protocols that share the same proof of asynchronous, byzantine-fault-tolerant consensus safety. Examples of members of this family of protocols include “Casper the Friendly Ghost”, a blockchain consensus protocol, but also a binary consensus protocol for example or, more interesting, a sharded blockchain consensus protocol.

The system is not completely described and questions about the very applicability of what is “proven” in the papers ([9] and [10]) remain.

That aside, let’s go into the details of Casper CBC. Let’s first define the terms above.

“The Correct-By-Construction methodology defines a set of principles and derives correctness by logical induction from these first principles.” The goal is thus to define a very strong correct theoretical foundations and then build upon and inherit all past proofs and guarantees.

Synchrony v. Asynchrony:

Synchrony: messages within the network are delivered with a fixed time frame. We assume that there is a maximum time for messages to be delivered.
Asynchrony: there is no guarantee of a message being delivered (under any fixed time).

In reality, the synchrony assumption doesn’t hold. Consensus should thus be design for as asynchronous environment as possible. It makes things much more difficult to achieve termination.

The asynchrony leads to what is called the FLP impossibility (defined in Impossibility of Distributed Consensus with One Faulty Process [14], researchers Fischer, Lynch, and Paterson). It states that it is impossible to reach consensus among deterministic asynchronous processes if there is one or more faulty processes. The only ways to circumvent this impossibility is to either to relax the asynchrony assumption (use partial synchrony assumptions) or going for non-determinism.

Safety:

A protocol guarantees safety if it guarantees that all non-faulty processes agree on the same output. Despite malicious actors and potential involuntary failures, we don’t end up several valid transaction logs.

Liveness:

Liveness if the concept that the system keeps moving forward and doesn’t stagnate. In the context of a blockchain, liveness means the blockchain keeps growing by adding new valid blocks. Liveness is obviously crucial because if the blockchain stalls, it becomes useless.

Finality:

Finality is the affirmation that all well-formed block will not be revoked once committed to the blockchain. Transactions contained in a block can’t thus be part of the commonly accepted history at time t and be arbitrarily changed or reversed at time t+1.

Finality is thus vital, at the core of designing a blockchain consensus protocol. Depending on the nature of the protocol finality can come in 2 very different fashions:

Probabilistic finality. This is the type of finality provided by protocols like Bitcoin’s Nakamoto consensus. As the block containing a transaction sinks deeper into the chain, the probability that the transaction will not be reverted increases. Indeed, the deeper the block, the more likely that the fork containing that block is the longest chain and will remain as such. However, the probability will never reach 1, no matter how long you wait. For Bitcoin, it is commonly recommended to wait until a transaction is 6 blocks deep into the blockchain before considering the transaction as finalized, to ensure that there is a very low likelihood of that transaction being reverted.
Absolute finality refers to the type of finality provided by PBFT-based protocols such as Tendermint. Once a block was proposed and approved by a sufficient share of the validators, the block is commited and automatically finalized absolutely. The block can’t be reverted.

We can mention also the notion of economic finality, in which it becomes monetarily costly for a block to be reverted. In PoS with slashing, if a validator double-votes, their entire stake could get slashed, making it exceedingly expensive to harm finality.

Even though absolute finality sounds absolutely better, the CAP theorem actually lays out the trade-off between consistency and availability that has to be made. Where you want to be on this compromise really depends on your use case. In order to be running dApps, you should tend to favor consistency. Casper CBC achieves absolute finality.

CBC Consensus

Let’s first define the environment we are in: validators weighted by their stake who can send messages to each other to arrive at consensus.

A typical message contains:

A consensus value. If we are building an integer consensus algorithm, then the consensus values will be integers. If we are building a blockchain consensus algorithm, then these consensus values will be blocks.
A reference to the sender of the message.
A justification: reference to some protocol state. In an asynchronous protocol, the notion of absolute time is non-trivial. There is indeed no reason that 2 messages sent one after the other will arrive in this order to other nodes. One way to prove an notion of time / ordering, is to give a reference to an earlier protocol state (a protocol state itself is a set of earlier messages).

Message structure = (value, validator, justification).
A state sigma is the set of all past messages.

Fig. 3: In the schema above, there are two validators s1 and s2. The messages from each validator reference the protocol state they are aware of and is published.

The notion of state transition formalizes the concept of time and what “after” means in the distributed environment: state 𝜎2 follows 𝜎2 if the 𝜎2 includes all messages composing 𝜎2. Each state 𝜎 then defines a new “futures cone”: the set of possible states the protocol may transition to starting from state 𝜎.

An estimator is a function, that given a protocol state, returns a set of consensus values. Estimators are not further defined in the CBC paper.

There are 2 types of faults defined:

The proposed value must be in the set of consensus values returned by applying the estimator on the justification. Anyone receiving the message can run the estimator on the justification and verify than the message respects this rule / is valid.
We say a validator equivocates when it sends 2 or more messages, none of which being justified by a protocol state containing the other (no message is “later” than the other). In other words, the validator creates an alternative timeline as the protocol state is the only measure of “time”. Validators that do not equivocate will always have at most one “latest” message.

Fig. 4: In this case of a binary estimator, validator s2 is equivocating. He justifies two different messages M2 and M2' from the same state σ’.

Consensus failure will occur when a sufficiently large number of participants engage in this type of Byzantine behavior.

A node achieves finality on a value after it has seen a sufficiently high number of validators propose the value in valid messages. A unique feature of Casper CBC is that the “sufficiently high” number depends on the node thanks to the absence of a defined “in-protocol” fault tolerance. The threshold of amount of faulty validators voting power (in percentage of total voting power) is not hard-coded in the protocol. Each node can decide its own threshold it is willing to tolerate.

This feature is possible in Casper CBC because, contrary to most other consensus protocols, there is no build in concept of “epochs.” If you have theses rounds and some of the validators advance to the next one, all the validators need to advance with them.

Having this in-protocol threshold t (usually 1/3) set in stone is also an incentive for miners to try to create cartels to bring together around t + ε or (1-t) + ε (ε being small) percent of the total voting power. Not imposing this threshold is thus greatly beneficial to the security of the system.

Casper CBC — The Friendly GHOST

Based on this theoretical definitions, we can define further a blockchain consensus mechanism based on GHOST (Greedy Heaviest Observed Subtree). GHOST is a chain selection mechanism (It can be thought of as a variant to the longest chain rule).

The consensus values are the set of all possible blocks and we define the estimator to return all blocks which are equal to or descendants of the blocks returned by running the GHOST fork choice rule on the justification.

This is theoretically enough to get brand new blockchain consensus mechanism with the properties listed above !

Recently, an unsolicited “peer review” [15] of the Casper CBC whitepaper draft [16] criticized some of the results presented, leading to a heated debate in the community. Most people defending the draft claim that the review righteously attacks the elements missing from the draft more than what is in the drafts and that these missing pieces will come. Whatever the future may bring, this is one more proof that the development of this new consensus algorithm that would be the foundation for POS for ether is still very early stage.
You can find an excellent summary of the debate if the “conclusions” in this tweet thread [17].

Conclusion

We have seen in the course of this article that the long road to improve the old and wasteful, yet only unchallenged, PoW consensus is perilous, raises numerous challenges and trade-offs and call for solutions coming from different research backgrounds. The very ambitious Casper is still very much at the state of early research. At this stage (or at any stage for that matter) any claim, coming from an altcoin, to use a miraculous PoS consensus that solves all issues without any tradeoff is fallacious and should seriously be frowned upon. It is yet unclear what necessary trade-off and implementation will be the best suited to answer the needs of any blockchain in terms of security, reliability and scalability. If one thing is certain, it is that there won’t be a one size fits all solution and that understanding the constraints under which a particular application runs under is of the utmost importance.

The complexity of such research on PoS certainly highlights the “simple” beauty and effectiveness of the Proof-of-Work consensus securing the blockchain since the very beginning.