ether

The Complete Guide to Proof of Stake

 

In this guide we examine proof-of-stake (PoS) consensus systems. We look at their theoretical advantages as well as weaknesses. We then analyse the specific details of some of the most prominent PoS systems attempted so far, where we learn that some PoS systems becomes increasingly complex to the point they became unrealistic. We review the latest Ethereum proposal, which we think is a significant improvement compared to previous attempts and could provide security benefits for the Ethereum network. Still, the system may still be reliant on proof-of-work (PoW), which is still used to produce the blocks while it is not entirely clear if the PoS element of the process contributes to ensuring nodes converge on a single chain.

 

Before getting into the specifics of Proof of Stake (PoS), it’s important to clarify what one is trying to achieve when building these consensus systems. Basically, trying to construct a data structure with the following properties:

  1. No one entity controls the content of the data;
  2. Participants agree on the content of the data e.g. nodes have a mechanism to decide between conflicting valid chains.
  3. The database can move forward.

PoW uses the most accumulated work rule to decide between competing valid chains. This is not only a solution to criteria above, but the PoW mechanism also solves the block production and block timing issue. While total accumulated work is the fork choice rule, a block producer is also required to include an element of PoW in each block, a stochastic process, and therefore the issue of who produces each block and when each block is produced, is also addressed by PoW.

PoS is the general concept of a fork choice rule based on the most accumulated stake. However, unlike PoW, this does not directly address the issue of who produces each block or when blocks are produced. Hence, these issues may need to be addressed by alternative mechanisms. PoW is also a solution to the coin distribution problem, something which may also require an alternative solution in PoS based systems.

Theoretical View of PoS: 

The Byzantine generals problem illustrates one of the main challenges involved when attempting to construct a data structure with the properties above. The issue is about timing and how to determine which updates to the ledger occurred first. If one third or more of the actors are disruptive, the problem is provably unsolvable, from a mathematical standpoint, as Leslie Lamport proved in 1982.

It is shown that, using only oral messages, [reaching agreement] is solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound two loyal generals

Source: The Byzantine Generals Problem (1982)

PoW can therefore be considered as an imperfect hack, which seems a reasonably strong Byzantine fault tolerant system, but certainly not a mathematically strong one. It is in this context, of imperfect systems, which one should analyse PoS alternatives, like PoW, these systems will also have flaws.

In PoS there are two competing philosophies. One of which is derived from PoW. Coins based on this include Peercoin, Blackcoin, and earlier versions of Ethereum’s PoS proposals. The second philosophy, is based more on Lamport’s academic research from the 1980’s and embraces the conclusion Lamport reached that a two-thirds majority is required to build a Byzantine fault tolerant system. Ethereum’s current iteration of the Casper proposal adopts this second approach.

The Advantages of PoS

PoS is typically looked at in the context of PoW, as an alternative that solves and/or mitigates against negative problems inherent in PoW based systems:

Environmentally friendly

The most widely cited advantage of PoS systems is the absence of the energy intensive process which PoW requires. If PoS based systems can achieve the same useful characteristics as PoW systems, environmental damage can and will be avoided. This is a significant positive for PoS.

Alignment of incentives

Another huge problem with PoW based systems is that the interest of miners may not align with that of coin holders, for example miners could sell the coins they mine and then only care about the short term, not long term coin value. Another issue is that the hashrate could be leased, with the lease holder having little economic interest in the long term prospects of the system. PoS directly ties the consensus agents to an investment in the digital coin aligning interests between investors and consensus agents.

Mining centralization & ASICs

Another key advantage of PoS based systems is potentially improving decentralization. PoW mining has a number of centralizing forces which arent applicable to PoS:

  • ASIC production is expensive and centralized;
  • There may be a limited number of cheap energy sources, with restricted access; 
  • Many aspects of mining can have economies of scale, e.g maintenance costs and energy costs, resulting in centralization.
  • Chip foundries are expensive and centralized;
  • ASIC related technologies can potentially be patented;

General & Economic weaknesses of PoS

As touched on above, Satoshi’s PoW systems appears to kill four birds with a single stone:

    • Chain selection (e.g the fork choice rule),
    • Who produces blocks, and;
    • When blocks are produced.
    • Coin distribution.

PoS only appears to be a proposed solution to the chain selection, leaving other problems open.

One of the criticisms of PoS systems is that they allocate new funds in proportion to the existing holdings. Therefore the “rich get richer” as the saying goes and it results in a few wealthy users holding a higher proportion of the wealth than the more socialist/egalitarian PoW alternative. If one invests in a PoS system at the start, you can maintain your share of the wealth, alternatively in a PoW system your wealth is diluted as new rewards are distributed to crypto miners. If rewards are allocated in proportion to existing holdings, you could argue its not inflation at all and that the reward is economically equivalent to adding more zeros to the currency. Thus one can even claim the reward system is futile and doesn’t provide an incentive at all. However this only applies if all users become PoS validators, while in reality some users will want to use the funds for other means.

Another big issue is that staking requires signing a message from a system connected to the web. Essentially, stakers are required to have a “hot wallet” which increases the risk that monies are exposed to theft from hackers. Although it may be possible to limit this downside by having a private key only entitled to stake for a short amount of time, after which the balance reverts back to the owner. However if there is a slashing rule (the punishment for voting on two conflicting chains), a hacker could conduct action which destroys the funds even if this mitigation strategy is used

Convergence Weaknesses of PoS: Nothing at Stake

Central to the consensus problem is timing and the order of transactions. If two blocks are produced at the same time, PoW solves the problem by a random process, whichever block is built on top of first can then take the lead and then miners are given an incentive to build on the most worked chain. PoW requires energy and a finite tangible resource and therefore miners have to decide which chain to distribute this resource to.

In contrast this process in PoS based systems is not entirely clear. If two blocks are produced at the same time, each conflicting block can build up stake. Eventually one block may have more stake than the other, which could declare it the winner. The issue here is that if stakers are allowed to change their mind to back the winner, such that the system converges on one chain, why would they not use their stake on various chains?

After all stake is a resource inherent to the chain and not linked to the real world, therefore the same stake can be used on two conflicting chains. Herein lies the so called “Nothing at stake” conundrum, which we view as the most significant issue currently facing PoS.

The “Nothing at Stake” Conundrum

The Nothing a Stake Issue Stake does not add to the convergence of the system, since the same stake can be applied to multiple competing chains, which is a risk free way of stakers increasing their reward(s). In contrast to this, in PoW based systems, energy is a real world finite resource and therefore the “same” work cannot be applied to a multitude of competing chains.
Defense 1 This issue can be avoided or mitigated against. The protocol can be adjusted such that if a staker uses the same stake on multiple chains, a 3rd party can give a proof of this to either chain, resulting in a punishment, such as the confiscation of the stake. Alternatively instead of a punishment, the “cheater” could lose potential rewards or be omitted from the staker pool.
Response from PoS skeptic The above defense is inappropriate and punishes what may be necessary behavior. For instance if a staker receives a block first, while the majority receives an alternative block first, it may be legitimate for that staker to change their mind and switch up to follow the majority. The process of changing your mind and switching to the majority to ensure the network converges is the point of the consensus system. If this behavior is punished, how would the system converge?

Either the economic value of the punishment is higher than the rewards for switching to follow the majority, or it is not. Therefore the nothing at stake problem means PoS systems can never make a contribution to system convergence and the idea is therefore flawed.

ether

Defense 2 The dilemma above can potentially be resolved in several ways. For instance:

  • Earlier proposals from Casper used several rounds of staking. Changing one’s mind in the early rounds can be legit and perhaps the punishment is small, while in later rounds the punishment for using the same stake in various competing chains increases, such that eventually users have a high degree of assurance over the finality of the system.
  • The most recent iteration of Casper aims to permit validators to change their minds, but only in “legit” situations and not when its considered “illegitimate”.
Response from PoS skeptic By adding several rounds or criteria in which validators can change their minds one is essentially increasing the complexity of the system. This is simply adding layers of obfuscation to conceal the inherent weaknesses illustrated by the nothing at stake problem, without solving the fundamental issues.
Defense 3 No system is perfect;  it’s mathematically impossible to construct a perfect system and therefore the nothing at stake problem isn’t solved, however the measures identified above mitigate the problems, such that these theoretical issues are unlikely to apply in the real world.

Another issue with PoS is the “long range attack” problem. This is the idea that attackers could buy a private key which had a large token balance in the past and then generate an alternative history from that point, awarding oneself more and more rewards based on the PoS validation. Due to the large amount of rewards given to the attacker, one could then generate a higher stake chain than the existing chain and a large multi year chain re-organization could be performed.

The solution to this problem is checkpointing, which is the process of locking in a certain chain state once a certain stake threshold has been met, such that it may never be re-organized.

Critics argue that this solution requires folks to keep their node online at all times, since an offline node can’t checkpoint. Some claim that if one goes offline, the security model therefore degenerates to “ask a friend”, since one is then dependent on asking others for their checkpoints. Although in the past the Bitcoin reference implementation included checkpoints, the purpose of these was to speed up the initial sync, although the impact of this could be said to result in an “ask a friend” security model.

If someone wants each individual user to fully verify all the rules and the state of the system, then relying on these checkpoints is not sufficient. Satoshi’s original vision appears to imply that the ability of nodes to be switched off and then verify what happened when one was gone is potentially important:

Nodes can leave and then rejoin the network at will, accepting the proof-of-work chain as proof of what happened while they were gone

Source: Bitcoin Whitepaper

Although this ecosystem is expanding, many businesses and exchanges operate 24/7 and are therefore required to keep a node running at all times, and can therefore do checkpointing. There are strong incentives preventing them from permitting a large chain re-organization. To many people, this is sufficient security and the risks posed by the long range attack problem are therefore irrelevant.

In a pure PoS system, stakers also are required to produce blocks. These systems have often functioned by selecting a sequence of authorized block producers randomly from a pool, where the probability is proportional to the stake. The issue we run into here is a source of randomness which is required inside the consensus system. If the blocks themselves are used for generating the entropy, stakers could try to manipulate the content in blocks in order to allocate themselves future blocks. Stakers may then require more and more computing power to try more alternative blocks, until they are allocated a future block. This then eventually and essentially results in a PoW system.

The stake grinding problem is less of a fundamental problem with PoS, when compared to significant issues like the “nothing at stake” problem. All that is required to solve this problem is a source of entropy in the network and an Ethereum smart contract like the RanDAO, in which anyone can participate, and can solve this problem.

 

Case Studies – Peercoin & Ethereum’s Casper

1 – Peercoin – 2012

Peercoin is a hybrid PoW and PoS system, built on the idea of coin age. The fork choice rules are the blockchain with highest total consumed coin age.

Coin age is simply defined as currency amount times holding period. In a simple to understand example, if Jim received ten coins from Alice and held it for ninety days, we say that Jim has accumulated 900 coin-days of coin age

Source: Peercoin Whitepaper

In Peercoin, some blocks were produced purely using PoW, while other blocks were produced using PoW where the difficulty adjusts based on the coin age destroyed by the miner in the transaction. For example, if Bob has a wallet-output which accumulated one hundred coin-years and expects it to generate a [PoS block] in two days, then Alice can roughly expect her 200 coin-year wallet-output to generate a [PoS block] in a single day.

Weakness Summary
Nothing at Stake This protocol aims to prevent miners using the same coins in a coinstake transaction on multiple chains by ignoring the second conflicting chain. However this is not sufficient and can result in nodes diverging, if they receive the conflicting blocks in a different order.
Block Production Solved by using PoW to produce the blocks.
Long Range Attack This was a serious vulnerability for Peercoin, an attacker can simply save up coin age by not spending their coins and then launch a re-org attack.

This was solved by centrally broadcasting checkpoints several times per day. Peercoin was therefore a centralized system.

Stake Grinding This may not have been an issue, because there was no selection from a validator pool as PoW was always required and coin stake altered the PoW target.

Our Conclusion

At the time Peercoin was an interesting early and novel approach, however the proposal resulted in a centralized system, not able to match the properties of PoW.

2 – Ethereum – Caper full PoS system – 2015

This is a full PoS proposal, based on “consensus by bet” methodology.

  • Blocks are produced from a pool of block producers, a random number generator is used to select whose turn it is to produce a block and then the producer is given a time window in which they can produce a valid block.
  • Validators can then make or take bets on block propositions, providing a probability each time, representing the return betters can make.
  • After several rounds of betting, as the probability approaches One or Ninety-Nine percent, the block is considered final.
  • There is a set of bonded validators, one must be in this set to make or take bets on blocks.

Source: Ethereum Blog

According to the Ethereum blog, betting should occur using the following strategies by default:

  • If the block isn’t yet present, but the current time is still very close to the time that the block should have been published, bet 0.5.
  • If the block is present, but it arrived either far too early or far too late, bet 0.3.
  • Some randomness is added in order to help prevent “stuck” scenarios, but the basic principle remains the same.
  • If the block is not yet present, but a long time has already passed since the block should have been published, bet 0.3.
  • If the block is present and it arrived on time, bet 0.7.

The default betting strategy had a formula (given below), to push the probability away from 0.5, such that the chain would move forward, with the probability expecting to either approach zero or one.

Let e(x) be a function that makes x more “extreme”, i.e. pushes the value away from 0.5 and toward 1. A simple example is the piecewise function e(x) = 0.5 + x / 2 if x > 0.5 else x / 2

If a validator bets when the probability is Ninety-Nine percent, the return is very small (a one percent return used as a measure from which the reward is calculated), in contrast a winning bet placed placed with odds of 0.5, represents a return of one hundred percent, which results in a higher return from the rewards pool.

The fork choice rule then is the sum of all the weighted probabilities which have crossed a certain threshold, say 0.99. For example a chain of 5 blocks, each with a probability of 1 will represent a score of five. Any validator who changes their mind after the 0.99 threshold has been crossed, can be punished (i.e slashed) for staking on multiple chains. While changing your mind before the threshold is considered legitimate and there is no punishment in that situation.

Weakness Summary
Nothing at Stake The protocol aims to prevent miners using the same coins to bet on various chains by using a punishment mechanism, in which validators would lose their deposit. This may harm the convergence of the system, although betting formula may move the probability away from 0.5, which is designed to help mitigate the issue.
Block Production The RanDAO contract may be used to provide entropy to select the block producer. This only provides a time window in which blocks could be produced, it is possible there is a lack of consensus over whether the block was produced within the time window or not, after which the betting process is supposed to resolve the dispute.
Long Range Attack The nodes checkpoint blocks once a certain probability threshold has been reached. The long range attack problem remains for periods in which nodes are switched to off.
Stake Grinding The RanDAO contract can solve the stake grinding issue

The proposal was not adopted by Ethereum. The proposal was never complete, as some parameters and aspects of the system lacked a specification. Although the consensus by bet approach was interesting, it seemed too complex and there were too many uncertainties. This approach illustrates the difficulties involved when constructing full PoS systems and how when one tries to address the weaknesses, it simply results in more and more complexity, until this system becomes unfeasible.

3 – Ethereum – Latest version of Casper – The hybrid PoW/PoS System – 2018

The current Casper proposal represents a change in philosophy or a pivot, compared to some of the earlier PoS systems. It returns to the academic work of Leslie Lamport in the 1980’s and Lamport’s theorem that these systems work if and only if two-thirds of agents in the system are honest.

Therefore the current version of Casper is less ambitious than before. PoS is no longer used to produce blocks or decide on the timing of said blocks, which is still done by PoW miners.

The PoS system is used as a checkpointing process. This proposal is superior to the more complex earlier iterations of Casper.

This system works as follows:

  • The PoS system is only used every one hundred blocks, to provide an extra layer of assurance over PoW, as a checkpointing system.
  • Participants in the PoS process send their Ether into a “validator pool”. 
  • Validators votes are only valid twelve confirmations after the last checkpoint block.
  • If the 2/3 threshold is not met, the chain continues to progress based entirely on PoW.
  • Every one hundred blocks validators put their stake behind a checkpoint block, while also referencing a previous checkpoint block. If two-thirds of the funds in the validator pool support a proposal, the block is considered justified.
  • Once a block is justified, it can be used as a reference for future votes. Once two-thirds of the stake use a justified block as a reference, this justified block is considered finalized and this finality takes precedence over PoW.
  • If stakers do any of the following banned behaviors, in return for a small four percent fee, a third party can provide a proof of this, such that the cheater loses their entire stake/deposit (slashing):
    1. Votes for multiple conflicting blocks at the same height.
    2. Votes for multiple conflicting blocks at different heights, but using conflicting reference blocks, unless this new reference block has more height.
    3. The Ethereum reward structure will be adjusted, such that PoS validators also receive a share of the rewards, in addition to the PoW miners.

There are only three problems with the new proposal:

  1. Over one third of the stakers are refusing to participate – in which case we are just back to a PoW based system
  2. Stakers changing their mind after finality so that more than two thirds supports an alternative chain – again, the long range attack problem
  3. Stakers reaching two-thirds majority support for a lower PoW chain than the current leading PoW chain, a new way of causing a re-organization. The most significant downside of this proposal.

Core to the assumption behind this system is that it is PoW which drives the chain forwards and that the PoS system only comes into play, once the PoW miners have decided on a chain, PoS votes aren’t even valid before twelve miner confirmations. Indeed, if the two thirds majority can’t be achieved then the chain continues on a PoW basis.

The core characteristic of this latest Casper proposal is that the PoW happens first, and only after this does PoS potentially provide an extra assurance against a chain re-org, orchestrated deliberately by hostile PoW miners. PoW therefore still provides computational convergence, with the PoS mechanism defending against the threat of a human threat of a miner re-org. Therefore although PoS provides this safety, it also provides extra risk, therefore its not clear if there is a net benefit.

Weakness Summary
Nothing at Stake Validators can vote on several chains, but not at the same height. This is designed to allow validators to change their mind, but only for “legitimate” reasons.

For the hybrid version of the model, the convergence issue can be solved by relying on PoW mining.

Block Production PoW miners produce blocks; therefore there is no issue related to selecting the block producer.
Long Range Attack Once two-thirds of the stake in the validator pool has used a block as a reference for voting, nodes finalize the block and there can’t be a re-org. The long range attack problem remains for periods in which nodes are switched off.
Stake Grinding PoW miners produce blocks therefore there is no stake grinding issue.

In the event of a contentious hard-fork and chainsplit, if the new chain alters the format of the validator checkpoint votes, two-thirds of the validators could conduct destructive re-orgs on the original chain, while avoiding punishment (e.g slashing) due to the new voting format. Validators could therefore destroy the original chain, whilst still moving forward on a new chain of their choice. This system could therefore be signficantly less resilient to being shut down.

 

PoW is relied on to resolve any Byzantine faults first, before the PoS process occurs. Therefore the system relies on PoW for both block production and for the crucial property of ensuring the system converges on a single chain. Although PoS mining may mitigate some risks (i.e hostile PoW miners), its unclear if it makes a contribution to convergence or security. The critics of PoS could therefore argue that any rewards redistributed from PoW miners to stakers unnecessarily dilutes system convergence and security.

Despite the plan to use this proposal as a stepping stone and as part of a gradual shift towards a full PoS system, this could be more difficult to achieve than some in the Ethereum community believe.

Olé Crypto,

CBNN

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.