What does it cost for Proof of Stake (PoS) to work securely and successfully?

Proof of Stake (PoS) has always been the most controversial topic in the field of cryptocurrency.

Although this model has many undeniable benefits, including high efficiency, greater security and permanent immunity to hardware centralization, the PoS algorithm is often more complex than PoW-based solutions, and there have been widespread doubts about the feasibility of PoS. Some people believe that the "nothing Nothing at stake " problem is fundamentally unsolvable.

It turns out that these problems are solvable, and we can provide a rigorous argument that PoS, with all that it entails, can succeed, but only at a small cost. The purpose of this post is to explain what that cost is, and how to minimize its impact.

Economic Set and Nothing at Stake

First, let’s get to the basics. Generally speaking, the purpose of a consensus algorithm is to allow the system to safely update its state according to some specific state transition rules; at the same time, the power to execute these state transitions is decentralized among an economic group.

An economic group is a group of users who can be given the right to jointly perform state transitions through an algorithm; the important property required of an economic group for consensus is that it must be securely decentralized - meaning that no single role (or a colluding group) can control the majority of the group, even if that role is well-funded and has the potential to profit. So far, we have discovered three secure and decentralized economic groups, each corresponding to a class of consensus algorithms:

1. Holders of hashing power : Standard Proof of Work (PoW), or TaPoW. Note that there are two variants: those that require specialized hardware to participate, and those that require (ideally) general-purpose hardware to participate.

2. Stakeholders : All variants of PoS.

3. Social network of users : Ripple/Stellar type consensus.

It is worth noting that there have been some recent attempts to develop consensus algorithms based on traditional Byzantine fault tolerance; however, all of these approaches are based on an M-of-N security model, and one of the issues that arises when applying the concept of "Byzantine fault tolerance" is where N should be sampled from. In most cases, the economic groups used are stakeholders, so we will treat this new BFT paradigm as a clever subcategories of "PoS".

Proof of Work (PoW) has a nice property that makes it simple to design efficient algorithms for it: participation in the economic group requires participants to consume resources external to the system. This means that when contributing work to a blockchain, miners must choose one of all possible forks of the chain (contribute work to it, continue it) (or start a new one), and different options are mutually exclusive. Double-voting, even if the second vote is conducted many years after the first, is unprofitable because it requires you to spread your computing power across different votes; the dominant strategy is to focus your computing power only on the fork you think is most likely to win.

However, for PoS, the situation is different. Although the threshold for joining the economic group may be high (although we will see that this is not always the case), voting is free. Such a "naive PoS" algorithm simply tries to make every coin a "simulated mining machine" so that the owner of the coin has a specific probability of signing a block (producing a block) per second, thereby imitating the proof of work, so there is a fatal flaw: if there are multiple forks, the best strategy is to vote for all different forks. This is the core of "Nothing at stake".

There is a concept that tells us why you can't get a user to vote for only one fork in a PoS environment: "altruism-prime". Altruism-prime is a mixture of true altruism (which some users or software developers may have) and false altruism. The former is due to direct concern for others and network wealth, and moral disgust when doing obviously evil things (such as double voting); the latter is because people who hold coins don't want to see the value of their coins go to zero.

However, relying solely on altruistic dominant personality is unreliable, because the increase in the value of the coin generated by the integrity of the protocol is a public good and will encounter the problem of insufficient supply (for example, if there are 1,000 stakeholders, and each of their actions has a 1% chance of becoming a "critical" factor in the success of an attack that will cause the coin value to return to zero, then any stakeholder can be bribed by providing only 1% of the value of his holdings). Assuming the distribution of holdings is equivalent to the genesis block of Ethereum, the amount of bribe required will be between 0.3% and 8.6% of the total stake (total holdings) (or less, if the attack is non-lethal), depending on how you estimate the probability of each user becoming a critical factor. Nevertheless, altruistic dominant personality is still an important concept that algorithm designers should keep in mind, and its advantages will be obvious when it is useful.

Short-range forks and long-range forks

If we only consider short-range forks, i.e. forks that are less than a certain number of blocks away from the latest block (e.g. 3,000 blocks), then there is actually a solution to the "nothing at stake" problem: security deposits. In order to be eligible for rewards for voting on blocks, users must first deposit a deposit. If the user is found to have voted for multiple forks, someone else can publish a proof of these transactions on the original chain and take away the user's rewards. Therefore, continuously voting on one chain has become the dominant strategy.

Another set of strategies, called "Slasher2.0" (this is relative to the earliest deposit-based PoS algorithm Slasher1.0), only punishes voters who vote for the wrong fork, not voters who double-vote. This makes the analysis quite simple because it does not require voters to be arranged many blocks in advance (to prevent probabilistic double voting), although it is also costly because once there are 2 choices on the same height block, users may choose to support neither. If we want users to sign (vote), in this case, a variant of the "logarithmic scoring rule" can be used (here is a more detailed study). For the sake of discussion, (here it is directly assumed) Slasher1.0 and 2.0 have the same properties.

The reason why this approach only works for short-range forks is simple: users eventually have the right to get their deposit back, and once they get it back, there is no longer any reason not to use those coins (stakes) to vote on long-range forks. One way to deal with this problem is to make the deposit permanent, but these approaches have their own problems: unless the value of a coin continues to grow and accept new signers (voters), it will eventually ossify into a permanent aristocracy. Given that one of the factors that made cryptocurrencies popular was the public's dissatisfaction with the aristocracy having eternal power, replicating this in the digital world is unlikely to be accepted by most users. Only blockchains with specific uses that are destined to end and are pursuing a quick death should use the aristocratic model (for example, you can imagine a game based on a blockchain that only runs one round).

One approach to this problem is to combine the slashing mechanism described above (for short-range forks) with a backup solution, transactions-as-proof-of-stake. TaPoS counts the transaction fees of each block as the score of each block (requiring each transaction to include the hash of the most recent block to make the transaction not too trivial), and in theory, a successful attack must be very costly to achieve. However, this hybrid approach has a fundamental flaw: if we assume that the probability of a successful attack is close to zero, then each signer has an incentive to provide a paid service: re-sign all transactions signed by him for the forked chain (which will make the forks evenly matched); therefore, from a game-theoretic point of view, a zero probability of successful attack is not a stable equilibrium.

Do you think it is impossible for every user to open their own node.js web application to accept bribes? Yes, if everyone has such an incentive, there is a simpler way: sell old, unused private keys on the black market. Even without the black market, the coins of the PoS system will always be under this threat: some of the big players who bought coins in the pre-sale stage will eventually meet and collude with each other to jointly create a fork for their own benefit.

Because of all the above points, we can conclude that, unfortunately, the threat of initiating an arbitrarily long fork is fundamentally present; moreover, for all non-degenerate implementations, PoS algorithms face this fatal threat if they want to succeed under the PoW security model.

However, we can work around this obstacle with a slight (but fundamental) change to our security model.

Weak Subjectivity

While there are many ways to categorize consensus algorithms, in the following sections we will focus on the following. First, we will provide the two most common paradigms today:

• Objective : A new node joining the network only needs to understand (1) the definition of the protocol and (2) all blocks and other "important" messages that have been published. No other information is needed to reach the same conclusion about the latest state as other members of the network.

• Subjective : In such a system, different nodes will always reach different conclusions, and joining the network requires a lot of social information (such as reputation).

Systems that use social networks as consensus sets (such as Ripple) are necessarily subjective; a new node that only knows the protocol and data can be convinced by an attacker that the attacker's 100,000 nodes are trustworthy; so without reputation there is no way to deal with attacks. On the other hand, PoW is objective: the current state will always contain the state with the highest workload expectation.

Now let’s add a third paradigm to Proof of Stake (PoS):

• Weak subjectivity : A new node joining the network only needs to know (1) the protocol definition, (2) all blocks and other "important" messages that have been published, and (3) the states that are recognized as valid within N blocks from now; it can reach a consensus on the latest state with other participants in the network, unless there is an attacker who permanently has the ability to control more than X percent of the consensus set.

In this mode, we can clearly see that PoS works very well: we simply prohibit nodes from reverting more than N blocks, and set N to be the security deposit length. That is, if state S is valid and has been an ancestor of at least N valid states, then from now on, S' that is not a descendant of S must be invalid. Long-range attacks are therefore no longer a problem, because we only need to say that long-range forks are invalid according to the definition of the protocol. This rule is obviously weakly subjective, and the additional benefit is that X will be equal to 100% (that is, no attacker can cause a permanent split unless they create a fork longer than N blocks).

Another weak subjective scoring method is exponential subjective scoring , which is defined as follows:

1. Each state S has a "score" and a "gravity"

2. The score of the genesis block is 0 and the gravity is 1

3. score(block) = score(block.parent) + weight(block) * gravity(block.parent) , where weight(block) is usually 1, but more advanced weight functions can be used (for example, for Bitcoin, weight(block) = block.difficulty also works well)

4. If a node finds a new block B' and B is its parent block, and if the length of the longest fork extending from B is n, then gravity(B') = gravity(B) * 0.99 ^ n (note that in addition to 0.99, there can be other values ​​here)

Essentially, we are explicitly penalizing forks that come later. Unlike more naive approaches that rely on subjectivity, ESS is largely immune to permanent network splits; if the first and last nodes receive block B k blocks apart, a fork cannot persist unless the lengths of the two forks remain forever within roughly k percent of each other (if this is the case, then the different gravity values ​​of the forks will cause half of the network to always favor one fork as the higher-scoring fork, while the other half will always favor the other fork). Thus, ESS is weakly subjective, and X corresponds roughly to how close to a 50/50 split the attacker can create (e.g., if the attacker can create a 70/30 split, then x = 0.29).

In general, the "roll back at most N blocks" rule is better and less complex, but if users are willing to accept a higher degree of subjectivity (i.e. smaller N) in exchange for getting very high security faster (i.e. immunity to 99% of attacks after N blocks), then ESS may prove to be more effective.

inference

So what would a world driven by weak subjective consensus look like?

First, nodes that are always online do not suffer from the problem; for them, the definition of weak subjectivity is equivalent to objectivity.

Nodes that are online occasionally, or at least once every N blocks, will not encounter problems because they can constantly get updated status of the network.

However, nodes that are new to the network, and that only appear once in a long time, will not be able to rely on the consensus algorithm to protect them. Fortunately, for them, the solution is simple: when they first register, or come back online after a long period of being offline, they just need to get the hash of the most recent block from a friend, or a block explorer, or just their software vendor, as a "checkpoint" to import into their blockchain client software, so that they can safely update their current state from there.

This security assumption, the idea of ​​getting a block hash “from a friend”, seems lax to many; Bitcoin developers tend to point out that if the solution to long-range attacks is some alternative decision mechanism X, then the security of the blockchain ultimately depends on mechanism X, so in reality this algorithm is no more secure than directly exploiting X - their implication is that most X, including our social consensus-driven approach, are insecure.

However, this logic ignores why consensus algorithms exist in the first place. Consensus is a social process, and humans are very good at reaching it without any help from algorithms; perhaps the best example is stone coins, where a tribe on Yap Island uses collective memory to record changes in ownership of stone coins, almost like a blockchain (these stones, like Bitcoin, are an asset with no intrinsic value).

Why consensus algorithms are necessary is simply because humans do not have unlimited computing power and would rather rely on software to maintain consensus for us. In this sense, software as agents are very smart because they can apply very complex rules to very large amounts of state with perfect accuracy; but they are also very ignorant because they lack social information, and the design challenge of consensus algorithms is to create algorithms that require as little social information input as possible.

Weak subjectivity is the right solution. It relies on human-driven social information to solve the long-range attack problem of PoS. The role of the consensus algorithm is only to increase the speed of consensus (shortening weeks to a dozen seconds) and execute highly complex rules for large-scale states. The role of human-driven consensus is to maintain consensus on block hash values ​​for more than a certain period of time. Assuming that a tyrannical government is powerful enough to confuse blocks from a year ago, it will also be powerful enough to kill any PoW algorithm or cause confusion in blockchain protocol rules.

Also, note that we don't need to fix N; in theory, we could come up with an algorithm that allows users to lock up deposits for more than N blocks, and these deposits could allow users to have a more granular interpretation of the security level of the system. For example, if a user's last login was T blocks ago, and currently 23% of their deposits are locked up for more than T, then the user could use their own subjective scoring function, ignore signatures on new deposits, and successfully defend against attacks up to 11.5% of the total stake. A gradually increasing interest rate schedule could be used to incentivize long-term deposits, or for simplicity, we could just rely on the Altruism-dominant personality.

Marginal Cost: Other Objections

One objection to long-term deposits is that it encourages users to lock up their capital, which is inefficient and has the same problem as PoW. However, this argument can be argued from three perspectives.

First, marginal cost is not total cost. The marginal cost of PoS is a much smaller proportion of total cost than PoW. Users may not feel anything if they lock up 50% of their capital for a few months. 70% may be a little painful, but if there is no big reward, locking up more than 85% will be unbearable. In addition, different users will have different preferences in locking assets. Due to the combination of these two factors, no matter what the equilibrium interest rate is in the end, the marginal cost of most locked capital is much lower.

Second, locked capital is a private cost, but it is also an act that benefits the public good. Locking capital means that there are fewer coins available for trading, so the value of the currency will increase and lead to capital redistribution to others, which will create social benefits.

Third, security deposits are a very secure store of value, so (1) they replace the use of currency as a personal insurance tool, and (2) many users will be able to obtain loans secured by the same amount of currency with their security deposit.

Fortunately, there is a way to test these assumptions: launch a PoS coin with a 1%, 2%, and 3% annual staking reward and see what percentage of the coin is deposited in each case. Users will not go against their own interests, so we can use how much money users will spend on consensus to see how much inefficiency this consensus algorithm will bring; if proof of stake has a reasonable level of security at a lower reward level than proof of work, then we know that PoS is a more efficient consensus mechanism, and we can use different reward levels to get an accurate idea of ​​the ratio between total cost and marginal cost. Ultimately, it may take several years to get an accurate value for the cost of locking up funds.

In summary, we have now determined two points:

(1) The PoS algorithm can also be secure. In order to avoid the “nothing-at-stake” problem, it is both necessary and sufficient to change the security model and weakly embrace subjectivity.

(2) There are a lot of economic reasons to believe that PoS is more economically efficient than PoW. PoS is not unknowable; the past six months of formalization and research have determined its strengths and weaknesses, at least to a large extent comparable to PoW, and the uncertainty of mining centralization of PoW may always exist. Now, it is just a simple question of how to standardize the algorithm and give blockchain developers a choice.

(over)

Editor's note: This article was published in 2014 and explains how we need to change our security assumptions for the operation of PoS systems. What is noteworthy is the author's opinion at the end of the article: "Humans are very good at reaching consensus; consensus algorithms just speed up the process of reaching consensus", which seems to mean that the social consensus driven by humans is enough to support the security of a distributed system, and "weak subjectivity" is just a minor flaw. But are humans good at "reaching" consensus? No. From small lawsuits and policy debates to large international disputes and even wars, without exception, it implies that humans are not good at reaching consensus, because the state behind the consensus object is the rules, and humans will constantly impact the rules, interpret the rules in their own favor, and even directly destroy the rules. Because in the final analysis, humans are only good at discovering their own interests, not reaching consensus. Reaching consensus is often just a step to achieve interests, and if the interests are transferred, the consensus will be destroyed. Back to the question itself, in the world of objective consensus, the "Genesis Block" + the longest chain rule can accurately define a currency and solve the problem of counterfeit coins; but in the world of weak subjectivity, the Genesis Block cannot define the currency. To solve the problem of counterfeit coins, unless you are a validator from the Genesis Block, you can only rely on others. If the judgment and interpretation of the latest status of a system depends on a small number of people, then people who do not trust this small group of people will not use this system at all. This loses the so-called "social scalability."

Original link:

https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/

https://www.8btc.com/article/38216

Author: Vitalik Buterin

Translation & Proofreading: Babette & Shao Ping