I previously described how Bitcoin is secured by a Proof of Work (PoW) protocol. Now, I describe an alternative method of achieving the same goal — Proof of Stake (PoS). This is currently being used for some blockchains, such as Cardano, and there are also plans for Ethereum to move from its current PoW incarnation to a PoS system. Both methods have their benefits and drawbacks, with PoS requiring much less energy but, on the other hand, is more complex with more possible attack vectors. Opinion is divided on which is the better,with defenders of either system having very strong convictions. In this post, I concentrate on describing how proof of stake works and only briefly touch on the possible benefits of one method over another. There are many different implementations of proof of stake so, here, I give an overview of the methods used without concentrating on any one particular utilization.
As explained in an earlier post, whichever method is used to secure a blockchain, it should require miners to spend some resource in order to build blocks. For PoW chains like Bitcoin, this resource is computing power or hashrate. For PoS chains, the resource is the underlying tokens or cryptocurrency represented by the blockchain itself. More precisely, as it just requires miners to lock up coins for a period, it is the opportunity cost of these coins that they spend. This is an internal resource of the blockchain rather than an external one as with PoW. Before going any further, there is a slight matter of terminology. The people who build blocks for a proof of work chain are called miners whereas, in proof of stake, they are called validators. Other terms, such as forgers, are also in use. Personally, I think it would have been simpler to use the same word regardless of the protocol but, to be consistent with the common usage, I will refer to block builders as validators.
Let’s just refresh our understanding of what a protocol needs to do. It should;
- allow anyone with the necessary resources to participate in building the blockchain.
- allow the network to reach agreement on a single global blockchain state at each time.
- (immutability) ensure that, once a block is added and considered to be confirmed, then it will remain in the chain indefinitely.
Furthermore, these properties should continue to hold even in the event that a minority of validators are acting dishonestly or, even, are collaborating to attack the network.
In proof of stake, individuals register to become a validator by locking up a quantity of the blockchain asset. The protocol then divides up time into a sequence of successive slots, one for each block. It needs to assign one validator per slot, and do this in a way such that, on average, the number of slots assigned to each validator is in proportion to their stake size. Then, when their time slot is reached, it is the job of the validator to collect together transactions from the mempool, and construct a valid block to append to the chain. In return, they receive a reward which can be one of, or a combination of, the transaction fees in the block and the block reward.
Each block is appended to the one constructed in the previous time slot so that, as time progresses, the validators continually add blocks on top of blocks, building the chain. Figure 1 shows this procedure with the cryptopunks acting as validators. Unlike with PoW where anyone who is able to create a valid block can submit it for inclusion, here the protocol needs to verify that the block used in each time slot has indeed been created by the validator assigned to it. This can be achieved with public key cryptography where, when they purchase a stake, each validator has to supply a public key. They then sign their blocks using the associated private key, proving that they were created by or, at least, approved by the assigned validator.
Leader Selection
In PoW, miner selection happens automatically. At any time, anyone is allowed to produce the next block. The first person to do so, and get their block transmitted to and accepted by the network, will be the winner. In practice, the probability of each miner winning the race will be proportional to their hashpower.
In PoS this is process is not automatic, so the protocol needs to specify a way of assigning a validator to create each block. The validator assigned to produce a block in a given time slot is referred to as the slot leader, and there are various ways in which the leader can be selected.
Random Selection: The leader is chosen at random, so that each validator has a probability of being selected in proportion to his or her stake size. This is closest to the behaviour of PoW, but there are major difficulties in implementing such an approach. One obstacle is that blockchain protocols are deterministic, so there is no way for it to produce truly random selections.
One idea is to try and use a pseudo-random number, such as a hash of the previous block. While it is true that strong hash functions such as SHA256 behave like a pseudorandom number generator, this approach would allow the producer of the previous block to influence the choice. They could produce several different blocks, find the one whose hash has the most beneficial outcome for themselves, and only transmit this particular block to the network. In the worst case, this approach could devolve into a de facto proof of work protocol, where validators expend a lot of computing power to create as many blocks as possible, and only releasing the one with the ‘best’ hash value for adding to the blockchain.
Another idea is to require the validators themselves to submit the random numbers used to select the next leader. While we cannot trust a single validator to do this randomly, there are ways in which we can allow multiple validators to all ‘vote’ on the choice of random number used for the selection, in what is termed a leadership election. There are various ways of organising this, and I do not want to spend too much of this post going through them in detail, so will only briefly describe one method now. We break the process into rounds. In round one, each validator submits a hash of their choice of random number. This commits them to a particular choice without revealing it. In the second round, they reveal their choices. Finally, all of the revealed random number choices are combined by adding, xor’ing, or similar. As long as a single validator really chooses at random, then the final result will also be random. It is still possible for a validator to bias the final result, by simply failing to reveal the their choice in the second round if they determine that the final computed result would not be to their liking. To discourage such behaviour, the protocol can penalize them by excluding them from the validation process or slashing a part or all of their stake.
Deterministic Selection: The leader is chosen deterministically from the set of available validators. This approach also presents some difficulties. If they know who is going to be selected leader, validators would probably only want to stake during times at which they know they will get to create a block. At other times, they are likely to drop out of the validation process since it requires them to lock up their stake without reward. This would reduce the total number of validators at any given time, reducing the security of the blockchain by allowing potential attackers to gain a majority of the total stake. To guard against this behaviour, the leader can be based on coin age, which is the product of the stake size and length of time that it has been staked. Only those with the largest coin age would be selected, requiring validators to keep their stake for a sufficiently long time to be selected to build a block. After they have been selected, and collected the rewards, their coin age would be reset to zero so that they again have to hold their stake for a sufficient length of time to be reselected. In practice, many PoS implementations can be considered as a mixture of random and deterministic leader selection.
It is common to combine multiple consecutive time slots together into epochs. The set of leaders for an epoch is determined at its beginning, so that anyone hoping to build any blocks should lock up their stake at least before the epoch starts and hold it until after it finishes. If the number of slots in an epoch was equal to the total number of validators (each with an equal stake), then we could simply cycle through them all giving everyone a chance to build a block. More likely, they are not equal. Then, random selection through a leadership election can be used to select the set of leaders and the number of slots that they are each assigned during the epoch. To explicitly determine the leader for each slot, a deterministic function of the random number chosen for the epoch, the validators public key, and the slot number can be used. As the random number selection only has to be made once per epoch, this reduces the amount of time and effort spent choosing leaders. For example, Cardano currently has one slot per second and an epoch length of five days, or 432,000 slots. Also, more than one leader can be chosen for a slot, in which case the next leader gets to choose which block to build on top of and hence determine which is kept in the blockchain.
Missing Blocks
Although the protocol can choose which validator is to be assigned leader for each slot, it cannot force them to build a block. What can we do if a leader fails to perform their duty? In terms of building the chain, all that we can do is to skip this slot. The next slot leader will then have to build their block on top of the previously produced one. It would be a problem if too many leaders failed to produce blocks, as it would reduce the frequency and capacity of the blockchain, and impact on the security if there are too few blocks.
There is already an incentive for leaders to produce blocks when asked, since they would not receive the reward if they failed to do this. However, to further increase this incentive some blockchains will slash all or part of their stake. While this can seem rather punitive, especially since network connectivity or other such issues could cause them to accidentally miss their slot, it is no worse than what happens with proof of work. If a miner on a PoW chain was to construct a valid block but fail to submit it to the network in time, then they would lose all rewards even though they would have spent considerable energy on producing the block. In PoS, where coins are locked up to become a validator, rather than actually being spent, the costs and associated rewards are considerably smaller. Hence, slashing the stake brings the cost of missing a slot closer to that of PoW.
Forks
As with other decentralised protocols, it is possible for a proof of stake blockchain to fork. This occurs when the chain splits into two or more separate chains, meaning that the network no longer maintains a unique state. It can also potentially affect immutability. If most of the network was to converge on one particular fork but, then, get overtaken by a different one, the state of the chain could change meaning that transactions could be lost. Even worse, it opens up the possibility of double spend attacks. It is therefore necessary to guard against this so that blocks which are already confirmed (by having a number of blocks already built on top of them) will not be affected, meaning that only forks differing from the main chain by a very small number of blocks should be tolerated.
For now, let us consider how forks can occur in a PoS blockchain. Figure 2 below shows one such case. Here, the leader for the fourth slot has produced a block but, for whatever reason, the next leader did not build upon it choosing, instead, to build on the third block. This creates a fork, with one branch containing the block produced in the fourth slot and the other containing the one produced in the fifth.
How could this have happened? Maybe there were network issues, meaning that the block produced by leader four did not reach all other validators in time. So, for a period of time, the network is effectively split with each half working on their own fork. Alternatively, maybe the fourth leader was late in producing their block. The next one thinks that the slot has been missed so starts building on the third block instead. More nefariously, it is possible that the fifth leader intentionally decided to ignore the fourth block in order to remove it from the chain. It is even possible that the leader of the fourth slot is collaborating with some other validators to attack the blockchain by producing their own fork in private.
Another way that a fork could occur is if more than one block is produced in a single slot, as shown in figure 3. Some blockchains, like Cardano, can assign more than one leader to a slot. However, the situation in figure 3 has a single leader producing two blocks, which is definitely bad behaviour. Then, other validators continue building on top of different choices for block four, causing a fork.
Nothing at Stake
In proof of work, forks are common and an accepted part of the mining process. At any one time, there will be many miners all working on adding to the same chain. If two or more of them both find valid blocks at about the same time, then they will likely both be submitted to the network, creating a fork. The idea is that, for subsequent miners who are aware of more than one branch of the chain, they need to decide which one to work on when creating a new block. Since the protocol accepts the longest chain as the true state, miners are incentivized to concentrate their efforts on this one. Creating blocks on any other branch would likely be a waste of energy and effort, since the block reward would only exist in this branch whereas the money spent mining is real. As soon as one branch becomes the longest, the majority of miners will concentrate on appending to this, further extending its lead. In short order, other branches will get left behind and become orphaned as they have next to no chance of ever being accepted. This is called the Nakamoto consensus and helps ensure a single consistent global state, with reorganisinations restricted to a very small number of blocks.
Unfortunately, in proof of stake, things are not so simple. The cost to a validator of building a block is to lock up a stake of the asset, which is internal to the chain. Any external work required, such as computational effort, is insignificant. Consequently, adding to a chain only has a significant cost to a validator if that branch becomes the dominant one. This is known as the nothing at stake problem.
If a fork occurs, and a validator is aware of more than one branch, then the incentive is to add blocks to all chains for which they are selected as a leader. Not only does it not cost them anything but, if they do that, then they receive validation rewards and do not have to pay a penalty for missing a slot regardless of which branch is the eventual winner. If a fork occurs in a naive PoS implementation then the likely situation is that all validators would continue building both branches, as in figure 4 below. This starts off similar to figure 2 above, where the fifth slot leader misses the fourth block, and builds on the third instead, thereby forking the chain. However, all subsequent leaders produce blocks for both chains.
The effect of validators building on both chains is that they both continue to grow over time, without either one falling behind and being orphaned. Even if we were accept only the longest branch as being the correct one, it could at any time get overtaken by the other. Any practical PoS implementation needs to disincentivize building on multiple branches at once, and try to ensure that a single chain becomes the dominant one accepted by the network. There are two main ways of doing this.
Chain-based: The idea in chain-based proof of stake is that validators who build blocks in multiple branches at once get penalized by having their stake slashed. In figure 4, for example, each of the leaders from the fifth slot onwards would have their stake slashed, in both of the branches, discouraging such behaviour. Of course, the protocol applied to any particular branch can only depend on what happens in that branch, and not on any others. It cannot see who has been building on other branches of a fork. To get around this issue, we allow leaders to report validators working on competing forks by including a proof of the offending behaviour in their blocks. This can take the form of signed block headers of the competing branch. To encourage such reporting, the validators who include the proof of misbehaviour can be rewarded from the penalty paid by the offender. There are two main ways in which the penalties can be distributed.
- If a validator creates blocks on competing branches, then they are penalised on each of them, but not on any branch where they do not create any blocks.
- If a validator creates blocks on any chain, then they are penalised on all competing branches. Any branch containing a proof that the validator produced blocks in a competing one will slash their stake, regardless of whether or not they also produced blocks in the current one.
Clearly, this is with the proviso that they can only be penalized on a fork that contains a proof of the competing blocks. The second method may seem overly punitive, since even validators who produce blocks exclusively in one branch will still be penalized in other branches. However, it is closer to the incentives of PoW where a miner producing blocks on the ‘wrong’ chain will lose their reward when it gets orphaned, but still had to put in the work to produce it. The second method also solves some problems that are still present with the first approach. For one, it forces validators to choose their branch very carefully, since they will get penalized for choosing the wrong one. Also, a validator with a very small stake may only have a small probability of being assigned as a leader over the staking period. Then, it can be very unlikely that they would be a leader in both branches, so they would just build on whichever branch they can, regardless of whether or not it is the leading one. With the second method, they would only build on the leading branch.
Regardless of how the penalties are assigned, we cannot stop some validators from colluding to produce a private fork, and working on this simultaneously with the main chain. They can only be penalised after the fork is made public so that their behaviour is reported.
Byzantine Fault Tolerant (BFT): This method is used by leading proof of stake blockchains, such as Cardano. In BFT proof of stake, a block is not accepted as soon as it is produced by a slot leader. Instead, it is required that other validators vote on it, and will be accepted once it receives votes from a sufficient proportion of validators (e,g., two-thirds of them). So, in this approach, validators are required to send signed messages containing their votes for valid blocks. Since people should not vote for multiple branches at once, validators can also send messages reporting such behaviour so that offenders can be penalised by having their stake slashed and/or their validation rewards confiscated. The blockchain will then contain these messages in addition to the raw blocks produced by the leaders.
Suppose, for example, that a block receives votes from over two-thirds of the validators. Also, suppose that at least two-thirds of the validators are honest, and would not simultaneously vote for blocks in competing forks. Then, it is logically impossible for a competing block to also have received so many votes. This means that, assuming at least two-thirds of the validators are honest, and with a two-thirds validator vote threshold for accepting a block, we can be sure that only one branch of a fork will survive.
Regardless of which approach is used to discourage forks, proof of stake chains are still susceptible to long-range attacks. A group of validators could work in private to produce a fork, but only release it publicly after a long time has elapsed including multiple epochs. Then, by the time that the fork is released, they may have already collected their staking rewards and sold most of their stake in both chains, so it is no longer possible for either of the methods described to above to impose an adequate penalty. For this reason, payment of rewards can be delayed and stakes frozen for some time after the blocks have been produced. However, there will still be susceptibility to attacks over a longer period than this. This can be mitigated by simply requiring nodes to not accept chain reorganizations replacing blocks produced over a period longer than, say, four months. Such long-run attacks would be obvious to everybody when they happen, and some argue that they would not be accepted with the protocol code being updated to reject the competing fork. In any case, it would cause major issues for the blockchain.
Delegated Proof of Stake
Although anyone can become a miner for a PoW blockchain, in practice they are dominated by mining pools. Such pools are controlled by a centralized party, with the actual work outsourced to a large collection of participants. The central authority builds most of the block, deciding which transactions to include, which existing block to build off, and so on. Pool members are just assigned the task of finding a nonce to solve the proof of work problem. Block rewards are distributed amongst the members in proportion to their hashpower. This reduces some overheads and the variance in the reward. Many miners will be so small that they hardly ever, if ever, produce a valid block although, when they do, they would receive the entire block reward. By using a pool, these miners can obtain much more steady income.
While proof of stake generally has lower entry requirements, it is still subject to these benefits of scale. There can be significant minimum stake sizes and, even if the protocol allows sufficiently small stake sizes there can still be a significant variance of rewards depending on whether or not they manage to get assigned as a slot leader. In addition, requirements such as being always online could be a problem for some potential validators. For such reasons, staking pools are still popular with PoS where pool members lend an amount of the asset to the owner of the pool who, in return, pays back a proportion of the staking rewards.
Delegated proof of stake (DPoS) attempts to improve on regular staking pools by making them part of the protocol. Here, holders of the underlying asset can vote for a delegate, who will act as a validator and build blocks on the chain. Voting is done by pooling together users tokens and linking them to the delegate. Any rewards earned will be automatically distributed to the users in proportion to their stake in the pool. This removes possible trust issues of staking pools since users retain ownership of staked tokens, rather than passing it to a pool owner, and fixes the fair distribution of rewards in the protocol code. This further reduces the entry requirements for participating in the blockchain, since pool participants do not need to run a node, create blocks themselves, or remain online. On the other hand, it is sometimes argued that it can lead to centralisation by becoming dominated by a small number of large stake pools.
Several blockchains, such as Cardano, use DPoS, whereas others such as Ethereum 2.0 do not.
Comparison with Proof of Work
Both PoW and PoS have their specific benefits and drawbacks. Although these are a source of constant debate, I list some of these differences here.
- PoS has much lower energy requirements, making it environmentally friendly and less wasteful.
- PoW is much simpler with fewer possible attack vectors. It is also more battle-tested, being used in the very first and biggest valued cryptocurrency.
- PoS has lower entry requirements for participating in building blocks, since there is no need to purchase and maintain expensive mining rigs and source plentiful cheap electricity.
- It is argued that PoS can lead to a small number of people with large stakes controlling the chain, increasing centralization and domination by a few big players. In answer, it is often pointed out that PoW tends to be dominated by a relatively small number of large mining pools.
- While PoW is very successful for particularly high value blockchains, such as Bitcoin, it can work less well for smaller ones which do not achieve such a large hashrate. Instead, smaller chains may be able to achieve better security with PoS.
- PoW is subject to regular small forks and orphaning of blocks. This can become an issue if the time between blocks becomes comparable with the time taken for them to be distributed across the network. This effectively limits the block production rate and size. It is often argued that BFT based PoS chains can handle a faster production rate due to resistance to such forks.
- Sharding, as planned for Ethereum 2.0, is based on PoS. This is because validators do not choose which of the shards to work on but, instead, get assigned randomly to different shards. With PoW, splitting the chain into multiple shards would divide the hashrate between these, with miners getting to choose which one to work on and possibly leaving some shards with a low hashrate. In answer, though, merged mining is a method of using PoW to work on multiple chains at once, which could potentially work well with sharding.
For further details on proof of stake, Ethereum wiki has a very informative FAQ.
Zero Knowledge 