A crash course on Proof-of-Stake (Part II)
Proof-of-Concept for Proof-of-Stake
Table of contents
- Prerequisites and Motivation
- A Proof-of-Concept for Proof-of-Stake (this post)
- Introduction to Decentralized Random Number Generation
- Verifiable Delay Functions and Verifiable Secret Sharing (coming soon)
- Nothing at Stake and Long Range Attacks (coming soon)
So far we have learned that the core idea of Proof-of-Stake is to use “Stake” rather than “Work” or computational power to secure the voting mechanism of blockchains against Sybil attacks. This replacement is only possible with the help of a Decentralized Random Number Generation (DRNG) mechanism to select the next miner; this mechanism, unlike Proof-of-Work, doesn’t require massive computations.
In this post, I introduce a naive practical Proof-of-Stake scheme and examine it to extract some general understanding about Proof-of-Stake. This naive practical scheme in addition to educational importance has a historical significance as it enabled the first real-world implemented Proof-of-Stake blockchains like NXT and Peercoin.
Proof-of-Concept for Proof-of-Stake
Assume we want to build a Proof-of-Stake fork from Bitcoin! And we’ll call it Bitcoin made Proof-of-Stake or BTP for short. First, we have to add two new and special purpose transaction types to the system as follows:
- Staking transaction: Any person can stake (lock-up) any amount of money with this type of transactions to become a stakeholder.
- Withdrawal transaction: Stakeholders, people who already have staked some coins using staking transactions, can withdraw their stake with this type of transactions.
As per ordinary transactions, anybody can generate Staking or Withdrawal transactions, and they need to get included in the blockchain to be effective. Moreover, we are going to end Proof-of-Work. Thus we remove the nonce field in blocks. (Recall: every valid block includes a golden nonce which is a 32-bit number that makes the hash of the whole block lower than a target. A golden nonce is an answer to hash puzzles that miners are supposed to solve.)
Assume N stakeholders have already staked some coins. In each round, after the creation of each new block, the protocol has to select miner of the next block randomly from available stakeholders with probabilities relative to the ratio of their stake to the total stake. Let’s use the hash of the last block as a source of randomness and select miner of the next block according to it. Although hash functions are deterministic functions, they are very sensitive to changes in the input, and it is a common tradition to use the result of a hash function for an arbitrary input as a source of randomness.
To be precise, we sort N available stakeholders in order of their addresses and assign to each of them a non-overlapping interval of length equal to ratio of its stake to total stake times to output range of the hash function (thus, the sum of length of assigned intervals is equal to max(hash(x))-min(hash(x))+1). The stakeholder that its corresponding interval includes the hash of the last block gets the chance to mine next block, and if he does so, he’ll get rewarded.
Let’s take a loot at the following simplified example, the figure shows a situation that all previous stakeholders withdraw their stake while A, B, and C join as new stakeholders in block number m. We use SHA256 as our hash function, output of SHA256 is a 256-bit number so its range is 2²⁵⁶. I just made some assumptions about the hash of each block.
Notice that there must be a mandatory minimum delay, say d seconds, between blocks to provide enough time for the new block to get propagated throughout the network. Hence, although block creation does not require solving hard hash puzzles that take huge time, we still need to delay the process.
But what if the selected miner does not broadcast the new block? The selected miner may crash or happen to be malicious. Well, if the selected miner did not respond in D seconds, obviously D > d, protocol punish him by burning some of its stake and assign the task of producing the new block to the next stakeholder in the list.
The so-called protocol is going to get executed in a decentralized way. It means everyone run the protocol on their computer and everyone got their local view of the blockchain. Hence, each person must locally decide whether the selected miner of the next block has delayed more than D seconds or not. For example, assume that right now the length of the longest chain is m and V is selected as the miner of the block number m+1. If you receive the new block created by V before D seconds and I receive it after D seconds, from your view, V has acted honestly and got the reward, while from my view, V is malicious or unaccountable and gets punished. Hence, network delay or malicious behavior may cause forks in the blockchain.
We already have completed key parts of our specification, find some marketing partners and get ready to launch our huge campaign for BTP fork! Yeaaaaay!
But wait for a second, let’s do some security analysis first 😁.
Security Analysis of BTP
1) Bias of last block hash
Assume you are the selected stakeholder to generate the next block. You can decide which set of transactions to put in your block. Thus you have control on the input of the hash function, and hence on the resulting output of it. Why not try to make yourself the next miner again? You need to test some different set of transactions before you get timed out, before D seconds pass, and hopefully find a set of transactions that makes you miner of the next block again. So hash of the last block as a random number is bias-able, which is not good. We investigate this issue in the upcoming post about Decentralized Random Number Generation.
2) Need for a new fork-choice-rule
As I mentioned earlier, in BTP forks may happen as a result of network delay or block withholding (the act of not broadcasting the mined block publicly) by the selected miner. These forks need to get resolved; otherwise, the network becomes obsolete after a short while, because people can no more agree on the order of transactions. Fork-choice-rule is the common basis to choose between different forks.
Proof-of-Work uses “follow the longest chain” as the fork-choice-rule, and it guarantees eventual agreement on the canonical blockchain, but if we use the same idea here malicious parties can easily attack and make the whole system stop functioning!
Here is how: Assume you are the selected next miner and you are a respectable attacker! At first, you do not publish anything publicly and pretend that next selected miner does not respond and move on the next miner until according to the protocol you become the selected miner again, and you repeat the same procedure. Meanwhile, as you get rewarded you stake more and more in your privately held version of the blockchain, so it makes your work easier as you hold larger and larger part of the total stake. While the public network is forced to wait at least d seconds for each block to get propagated you can generate new blocks as fast as you can (which is way faster than one block per d seconds). Eventually, you have a longer chain and then you publish it. Congratulation, you have reverted all transactions in this period and even won a significant amount of reward. This type of attacks is known as Long Range Attacks.
From what we have seen above, “follow the longest chain” is not acceptable as the fork-choice-rule of our Proof-of-Stake scheme, but maybe other options like “follow the chain with the most stakes” do the trick for us. We will talk about fork-choice-rule, and it’s relation with typical attacks in upcoming posts.
What is next?
We have learned about the core idea of Proof-of-Stake and a naive practical approach to implementing it. However, as you have already understood we need to take a closer look at Decentralized Random Number Generation and possible attacks, and that is exactly what we are going to do in following posts.
Go to Part III, if you are ready for Decentralized Random Number Generation.
