Proof of Stake (PoS) was first introduced in a paper by Sunny King and Scott Nadal in 2012 and intended to solve the problem of Bitcoin mining's high energy consumption. At that time, it cost an average of $150,000 a day to maintain the Bitcoin network. Today, this figure is at a staggering $6.7 million (if we assume a $0.12/watt cost and multiply that with the estimated 56,209,833 KWh of electricity that the Bitcoin network consumed on Oct. 13, 2017).

Rather than relying on the energy-dependent work of miners to add blocks, Sunny and Scott suggested an alternative method called "staking" where a deterministic algorithm would choose nodes based on the number of coins an individual had. In other words, stakers would have more chances of being selected to add a block to the chain and reap the reward if they "staked" more coins in their wallet.  They hoped this would avoid the ever increasing energy costs and hashrate difficulty of mining. However, their new consensus mechanism was not without its own issues.  

There are four main challenges in designing a Proof of Stake system:

Distribution. Since block rewards go to stakers, how do you distribute coins initially?

Monopolization. Those with a significant amount of coins reap a majority of all future coins.

51% attack. Just like how Proof of Work (PoW) has to be wary of a 51% attack from a miner, so too does PoS have to be wary of a staker who has a 51% stake weight.

Nothing at Stake (NoS). PoS adds a block when a node meets a set of conditions which includes stake weight. However, the coin forks when two nodes meet these conditions at the same time. The fork is then resolved by other nodes signing one of the two transactions. The hypothetical problem of NoS arises when 99% of all nodes sign both chains because there is no cost (nothing at stake) to verify these transactions. Therefore a 1% staker could potentially "double spend" by paying with coins on one chain but then verifying the other.

In light of this, the evolution of PoS can be understood by each coin attempting to solve these issues in their own way.  We will now look at Peercoin.

Sunny King created Peercoin (PPC) in 2013 to become the first cryptocurrency to implement Proof of Stake while still keeping Proof of Work (PoW). It addressed the 4 issues of PoS in the following ways:

Distribution. Peercoin uses a PoW-based decreasing distribution. In the beginning, PoW was heavily emphasized for PPC's initial distribution phase but has since then been decreasing.  

Monopolization. Coin age was implemented to prevent coin-rich stakers from dominating the rewards.

51% attacks. PPC's chain is completely secured by PoS even though it is a hybrid. Attacks are highly unlikely because it is incredibly expensive to perform an attack. The attacker must effectively purchase or bribe 51% of the staked coins in order to perform this action. Any attack would significantly devalue the coin and cost the attackers a great deal.

Nothing at Stake. PPC developers don't believe this would happen. However, Sunny implemented optional "checkpoints" at first in case there was a successful attack.  Now that the PPC's network has matured, checkpoints are in the process of being phased out.

This next phase of PoS history is called considered a pure proof of stake protocol without any mining and was first implemented by NXT on November 24, 2013. However, let's consider another coin, Blackcoin, that was also a pure proof of stake that was released shortly thereafter as it has a simpler protocol and had a fairer initial distribution phase.

Blackcoin was created by Pavel Vasin (a.k.a. Rat4) and was released in February 2014.  When Rat4 decided to create BLK, he set out to remove coin age and PoW.  He believed coin age would increase the chance of a 51% stake attack as older aged coins would need less than 51% of staking coins to cause a fork. He also believed that coin age disincentivized users from staking consistently. Rather, stakers were incentivized to remain offline for 90 days to maximize their chances of getting a stake thereby making the network less secure. Rat4's implementation of PoS v.2 protocol addresses the four issues of PoS in the following ways:

Distribution. BLK went through a temporary Proof of Work phase with no pre-mine to ensure fair distribution.

Monopolization. This was addressed via a fair distribution period.

51% attacks. It is incredibly expensive to buy enough coins in order to perform this attack.  Also, the coin would lose significant value.

Nothing at Stake. BLK dev's also believed this was not a threat. However, BLK included checkpoints to protect against hard forks.  Checkpoints will be removed in PoS 3.

Since Blackcoin, there have been several iterations of the PoS protocol. For example, Bitshares was the first to implement Delegated Proof of Stake.  But the newest iteration of PoS is Ethereum's (ETH) attempt at PoS.  The motivation for ETH to switch is primarily a desire to move towards a more eco-friendly and decentralized system.  If the Ethereum Virtual Machine is truly to be adopted world-wide, Bitcoin's current $6.7 million daily electricity cost would quickly be surpassed.

Ethereum's PoS system will implement a Byzantine Fault Tolerance (BFT)-style PoS. Validators will be randomly assigned block rewards, however consensus is formed through a multi-round process where every validator votes for a chain. Ethereum is NOT utilizing Proof of Stake at the moment and there have been some doubts as to whether or not it will actually be implemented. With that being said, here's how Ethereum hopes to solve the four ssues involved with PoS:

Distribution. ETH has already been distributed with approximately 70% sold in it's ICO in 2014 representing 70% of total of Ether in circulation. Eleven million was given to the Ethereum Foundation and continues its distribution via PoW.

Monopolization. ETH has already been distributed.  Another way ETH hopes to solve this issue is by locking coins in a smart contract in order to stake. Therefore, staking comes at the cost of liquidity.

51% attacks. As mentioned above, it is incredibly costly to buy or bribe nodes to participate in a 51% attack. Should an attack happen, Michael Gubik proposes utilizing social/business/exchange forums to select one of the forked chains in his Proof of Stake FAQ on Ethereum's github.

Nothing at Stake. Validators will be disincentivized from signing orphaned blockchains as they will be punished.

There have been many fully functional and secure iterations of PoS over the history of cryptocurrency from the Hybrid PoS-PoW to pure PoS to Delegated PoS.  The BFT-style PoS is the newest attempt to address the four main issues surrounding the protocol initially proposed by Sunny and Mark. Each coin reflects a different approach and each has its own strengths and weaknesses. However, the move to PoS reflects a larger philosophical move in the world of cryptocurrency towards a more eco-friendly and decentralized system.