Alternatives for Proof of Work, Part 1: Proof Of Stake
This is a guest post by Ray Patterson.
This is another article from the series of publications on how various cryptocurrencies work. By popular requests this post is devoted to Proof of Work, Proof of Stake, and some other proof-of-something comparison. Make sure to check our previous article, "The Proof-of-Work in Cryptocurrencies: Brief History".
Proof of Work criticism
As we remember, the Proof of Work was born in the long past 1993, in the cryptographers' family; parents intended it to become the defender from DoS attacks and spam. However, it received an offer it could not refuse by some anonymous with Japanese accent: to become a basis for distributed timestamp server. The scheme seemed simple: network nodes "vote" for their version of transaction history by introducing their computational powers into calculating "rare" hashes. The version that gets the majority of votes is accepted by all nodes as the reference version.
An important aspect was ensuring high total hash power of the network: in order to defend against potential miscreant with his possible 51% of the network hash rate. Still, the initial concept of Proof of Work implied small tasks that could be performed by the client to access the server resources. Within the limits of such DoS-protection model even small powers of a client would not prevent him from plausible use of the resource, while large powers were not required. Thus miners motivation was implemented fairly simply: in kind, with bitcoins, i.e. practically with money.
It changed everything. In the world of cryptocurrencies, Proof of Work turned into a monster devouring electricity in the race for mining profit. Around 2012 the first serious complaints appeared, when the total performance of Bitcoin network surpassed that of the most productive supercomputer in the world (indeed, comparing PFLOPS and Gigahashes is not exactly correct, but... sometimes it is). "Waste of energy!" everyone cried. Shy protests from those reminding about the 51%-attack protection and ATM energy consumption were ignored, as the first alternative was already on horizon: Proof of Stake.
Proof of Stake
It appeared as an idea in one of posts on bitcointalk as far back as 2011. The first implementation was realized a year later, in 2012, in PPCoin cryptocurrency (now called PeerCoin). Later on, such protocols appeared in other projects as well, but all in due course.
Proof of Stake has various implementations with one single concept: the limited resource used for voting can be found not only on the outside (consumed power and hardware), but also inside the system itself: the digital coins. The owners of the coins, the stakeholders, naturally do not spend them when voting, but the coins are reserved for some period, providing for the limitation. Obviously, although PC is running in order to mine, no complex calculations are required.
How Peercoin's Proof of Stake works
(click to enlarge)
Miner's resource is his coins (not spent, of course). More exactly, the unspent transaction outputs, each corresponding to some number of coins. The mining process looks as follows:
- Selecting an output received at least 30 days ago;
- Forming the Kernel structure, which includes: determined data from the output (time of the block of its origin, its number in the block etc.), current time, and so called nStakeModifier (periodically re-computed block of pseudorandom bits);
- Hashing Kernel and verifying the resultant value against the current target, which depends on the current network complexity (higher complexity => lower target), "age" of the output ("older" output => larger target) and its sum (larger sum => larger target);
- If hash is greater than the target, return to 1), i.e. take next output;
- If output is "successful", we spend it in coinbase transaction (by sending to ourselves), add block reward and fees for included transactions and sign the whole block using the key related to the spent output.
- Voila, the block is done. Start searching the next one.
- The blockchain verification is determinate: current time is received from the block header, output data from the blockchain, nStakeModifier is also uniquely calculated for each block;
- Output should be "old" so that an attacker could not find a "good" output that allows for finding a block by transferring money between his wallets;
- nStakeModifier is calculated on the basis of the last blocks and is therefore incalculable. It makes mining even more unpredictable (and more resistant to possible attacks);
- The current timestamp from 2) can vary in very wide range: plus/minus an hour. Therefore, 7200 hashes should be actually checked for each output, not one;
- The "age" multiplier of the target has the upper limit of 90 days. Otherwise, an attacker could generate a number of blocks in a row with very high probability if he possessed only a few VERY old coins.
The essence of the PoS-mining is the same lottery as PoW one. However, you do not have to "pay" for the ticket with your computing power: variants are searched in a very limited window of own outputs and the process does not depend on CPU power. The only factors that influence your chances are your total number of coins and current complexity of the network.
This brings us the following benefits:
- Energy savings. One cannot contradict here, though it is possible to use some "useful work" as a PoW (see Primecoin) or ASIC-resistant functions (CryptoNight, Cuckoo Cycle, Ethash etc.), which limit the mining possibilities to ordinary PCs.
- No endless "arms race": total hashrate is now limited not by Moore's law and the laws of thermodynamics, but by total number of coins present in the wallets of users. On the other hand, it is hard to understand if the majority of resources is owned by honest users.
- Attack becomes more expensive. If I would like to buy 51% of the coins, the market reacts by fast price appreciation. And what is the point in attacking the network if all my resources are invested into virtual coins of the said network?
Everything seems perfect: we have practically replaced physical work with some virtual resource. But the problem is hidden exactly in this issue, is it not?
Proof of Stake criticism
Answer a simple question: what is the price of spent money? If someone approaches you with an offer to buy the private keys for the money you have long spent, what price will be acceptable? As the keys do not cost anything and no one needs them anymore, I guess you would be satisfied with any offer: money for nothing!
Now, imagine that for some moment in the past (let us call it X) it is true that 50% (or more) of all coins were allocated to the keys bought by the attacker. For simplicity, let X be the moment right after the creation of the second block, and someone bought the keys for both blocks. It means that had he returned to the past, he would have 100% of all coins.
Actually, he does not need to travel to the past physically. Starting from this moment, he can "rewrite the whole blockchain history" by mining with these old coins! Moreover, he will receive the reward for each new block and increase his funds. He does not need to create transactions either (although he can transfer money to himself).
At some point, his alternative blockchain will catch up and surpass the real one in blocks. The whole network will switch to it, as there are no syntactical differences between the two. The essential difference, though, will be in the fact that in one blockchain more than half of all coins will belong to the attacker. Thus, selling the ghost voters, you can lose the real ones.
This particular kind of attack can be prevented. PeerCoin, for example, practices regular checkpoints: the blocks signed by the developer's key. Reorganizing beyond these points is impossible. Still, it is but ad-hoc solution, which does not deal with the general problem: Nothing on stake.
This problem means that mining (voting) costs nothing and requires no physical inputs. If, for example, at some point two blocks on the same level appear (the chain fork), you can mine both versions of the chain simultaneously. With Proof of Work, it is impossible: every verified hash from the chain A is non-verified hash from the chain B. Proof of Stake, in its turn, allows you to search in all "alternate realities" at the same time, and even on any height (i.e. in the past).
With Proof of Stake, double-spend attack is simpler. The only requirement is to mine simultaneously two versions of the next block: one containing the transaction from you to the seller (who does not wait for N confirmations), and the other with transaction to you. If you find both blocks, then you send the first to the seller (and get your goods), and the second — to the rest participants. There is high probability that the second version of the blockchain will be continued, and you will get your money back.
The Proof of Stake problem lies in the fact that it pays to mine a number of alternative branches simultaneously. You can do this for free, with non-zero chance of success, i.e. increase the expected return. Proof of Work does not allow such tricks, so you only mine in one branch (you choose it). As a result, a consensus is achieved at some point in proof-of-work model, while it is impossible to guarantee convergence for pure Proof of Stake.
If you are interested in this issue, you can find more details here.
In the following episode
- War. War never changes. What other arguments do supporters of PoW and PoS have?
- Make Love not War: breeding PoW + PoS = Proof of Activity.
- What is your proof? Proof of Burn, Proof of Capacity.
- What the hell do the Byzantine Generals have to do with this?
The next article in the series will be published next week.
The images are illustrations by John Tenniel.
You can read the second part by following this link.