Partnered With:

How to Learn to Love Weak Subjectivity

Read this article in 31 Minutes

Explain in detail PoS, the most controversial topic in the field of cryptocurrency.

Original title: "Dry goods | How to learn to love weak subjectivity"

Original source: Ethereum enthusiasts

Proof of Stake (PoS) has been one of the most controversial topics in the cryptocurrency space.

Although this model has many undeniable benefits, including efficiency, greater security and centralization of hardware The permanent immunity of PoS, the PoS algorithm, is often more complicated than the PoW-based scheme, and there have been widespread doubts about the feasibility of PoS. Some people think that the "nothing at stake" problem cannot be solved at all.

It turns out that these problems are solvable and we can provide a tight argument that PoS with all it It can be done, but at a small price. The purpose of this article is to explain what this cost is and how to minimize its impact.

Economic Set and "Nothing at stake"

First, follow the script. Generally speaking, the purpose of the consensus algorithm is to allow the system to safely update the state according to some specific state transition rules; at the same time, the rights to perform these state transitions are dispersed among an economic group.

An economic group is a group of users who can be given the right State transitions are collectively performed algorithmically; an important property required of an economic group for consensus is that it must be securely decentralized - meaning that there is no one actor (or one colluding group ) can control the vast majority of this group, even if the character is well-funded and potentially profitable. So far, we have discovered three secure and decentralized economic groups, each corresponding to a class of consensus algorithms:

Holders of computing power: Standard Proof of Work (PoW), or TaPoW. Note that it comes in two variants: those with specialized hardware and (ideally) general-purpose hardware.

Stakeholders: All variants of PoS.

Social Networking of Users: Ripple/Stellar Type Consensus.

It is worth noting that there have been recent attempts to develop Consensus algorithm; however, all of these methods are based on the M-of-N security model, and a problem that needs to be faced when applying the concept of "Byzantine Fault Tolerance" is where N should be sampled. In most cases, the economic groups used are stakeholders, so we will treat this new BFT paradigm as a clever subcategory of "PoS".

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

There is a concept that can tell us why you cannot let a Users voted for only one fork: "altruism-prime". Altruistic dominant personality is a mixture of true altruism (some users or software developers may have) and false altruism, the former is motivated by direct concern for others and online wealth, and doing obviously evil things (such as moral disgust when double voting); the latter because holders also don’t want to see their coin value go to zero.

However, relying solely on an altruistic dominant personality is unreliable because the coin value generated by the integrity of the protocol Improvement is a public good and suffers from undersupply (e.g. if there are 1000 stakeholders, each of their actions has a 1% chance of becoming a "critical" factor in the success of an attack , and this attack will cause the currency value to be zeroed, then for any stakeholder, he only needs to provide 1% of the value of his currency to bribe him). Assuming a distribution of holdings equivalent to Ethereum's genesis block, the amount required to bribe would be anywhere from 0.3% to 8.6% of total stake (total holdings) (or less if the attack is non-lethal ), depending on how you estimate the probability of each user being a pivotal factor. Still, altruistic-dominant personality is an important concept that algorithm designers should keep in mind, and its advantages are evident when useful.

Short-range forks and long-range forks

If we only consider short-range forks, that is, forks that are less than a certain number (say, 3000 blocks) away from the latest block, then there is actually a solution to the "Nothing at stake" problem: a security deposit . In order to be eligible for block voting rewards, a user must first deposit a deposit, and 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 then take The user's reward. Therefore, continuously voting on a chain becomes the dominant strategy.

Another strategy, called "Slasher2.0" (which is Compared to the earliest deposit-based PoS algorithm Slasher1.0 ), only voters who voted for the wrong fork are punished, not double voters. This makes the analysis fairly simple, as it does not require voters to be scheduled many blocks in advance (to prevent probabilistic double-voting), although there is a cost, as once there are 2 choices at the same height block , the user 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 (studied in more detail here). For the convenience of discussion, (here directly considered) Slasher1.0 and 2.0 have the same properties.

Why this method is only effective for short-range forks is simple: users Ultimately has the right to withdraw the deposit, and once the deposit is withdrawn, there is no longer any reason not to vote on long-range forks with these coins (equity). One way to deal with this problem is to make the deposit permanent, but these methods 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 deposit. Aristocracy ruled. Given that one of the factors that made cryptocurrency popular is the public's dissatisfaction with the eternal power of the aristocracy, it is impossible to replicate such a thing in the digital world to be accepted by most users. Only those specific-purpose blockchains that are destined to end should use the aristocratic model when pursuing quick death (for example, you can imagine a blockchain-based game that only runs for one round).

One type of solution to this problem is to combine the aforementioned slashing mechanism (for dealing with short-range forks) with A backup scheme, the transaction itself is PoS (transactions-as-proof-of-stake), combined. TaPos counts the transaction fees of each block as the score of each block (each transaction is required to include the hash of the latest block so that the transaction does not become too trivial), theoretically, a successful attack must cost a lot of money in order to achieve. However, this hybrid approach has a fundamental flaw: if we assume that the probability of an attack being successful is close to zero, each signer has an incentive to provide a fee-based service: re-sign the forked chain All transactions (so that the forks will be evenly matched); therefore, from the perspective of game theory, an attack with zero probability of success 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 a motivation, there is an easier way: sell old, no longer used private keys on the black market. Even if there is no black market, the currency of the PoS system will always be under this threat: those who bought the currency in the pre-sale stage will eventually meet and collude with each other to create a fork for personal gain.

Because of all the above points, we can conclude that, unfortunately, such arbitrarily long-range forks The threat is basically there; moreover, for all non-degenerate implementations, the PoS algorithm faces such a fatal threat if it wants to succeed under the PoW security model.

However, we can bypass the this hindrance.

Weak Subjectivity

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

Objective: a node newly joining the network only needs to Knowing (1) the definition of the protocol and (2) all the blocks and other "important" news that has been published, no other information is needed to reach the same conclusions about the latest state as other members of the network.

Subjective: In such a system, different nodes will always come to different conclusions, to join the network First, a large amount of social information (such as reputation) must be obtained.

Systems (such as Ripple) that use social networks as consensus sets are necessarily subjective; one only knows the protocol and The new nodes of the data can be persuaded by the attacker that the attacker's 100,000 nodes are trustworthy; so there is no way to deal with the attack without reputation. PoW, on the other hand, is objective: the current state will also always contain the state with the highest expected amount of work.

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

Weak subjectivity: new nodes that join the network only need to know (1) protocol definition, (2) all blocks and other published "important ” message and (3) the state that has been recognized as valid within N blocks from the present; that is, it can agree with other participants in the network on the latest state, unless an attacker permanently owns more than X% The ability to control the consensus set.

In this mode, we can clearly see that PoS works very well: we just prohibit nodes from returning Reverting over 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 then on, S' that is not a descendant of S must be invalid. Long-range attacks are thus less of an issue, since we suffice to say that long-range forks are invalid by the protocol's definition. This rule is obviously weakly subjective, and has the added bonus that X will equal 100% (i.e., no attacker can cause a permanent split unless creating a fork longer than N blocks).

Another weakly subjective scoring method is exponential subjective scoring, defined as follows:

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

The score of the genesis block is 0, and the gravity is 1

score(block) = score(block.parent) + weight(block) * gravity(block.parent), where weight(block) is usually 1, of course you can also use more advanced weight functions (for example, for Bitcoin weight(block) = block.difficulty would also work well)

If a The node finds a new block B' and B is its parent block, if the length of the longest fork extending from B is n, then gravity(B') = gravity(B) * 0.99 ^ n(Note, In addition to 0.99, there can also be other values here)

Essentially, we This is to explicitly penalize later forks. Unlike more naive approaches that rely on subjectivity, ESS essentially avoids permanent network splits; if the interval between the first node and the last node receiving block B is k blocks, the fork cannot last for a long time unless the lengths of the two forks remain forever within roughly k percent of each other (if so, then Different gravity values for forks will cause one half of the network to always favor a certain fork as the higher-scoring fork, while the other side will always support the other fork). Thus, ESS is weakly subjective, and X roughly corresponds to how close to a 50/50 split the network can be created by an attacker (e.g., if an attacker can create a 70/30 split, then x = 0.29).

In general, "at most "Back N blocks" rule is better and less complex, but if the user is willing to accept a higher degree of subjectivity (ie smaller N) in exchange for getting very high security faster (ie immune to 99% of attacks after a block), ESS may prove to be more effective.

Corollary

Then, What would a world driven by weak-subjectivity consensus look like?

First of all, always-on nodes don't suffer from problems; for them, weak subjectivity by definition etc. Valuing objectivity.

Occasionally online nodes, or nodes that are online at least 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 nodes that appear only once in a long time, will not be able to rely on consensus Algorithms to protect them. Fortunately for them, the solution is simple: when they sign up for the first time, or come back online after being offline for a long time, they just need The provider gets the hash of the most recent block, imports it as a "checkpoint" into their blockchain client software, and can safely update their current state from there.

This security assumption, the idea of getting a block hash "from a friend", is a problem for many It seems imprecise; Bitcoin developers often point out that if the solution to the long-range attack is some alternative decision mechanism X, then the security of the blockchain ultimately depends on mechanism X, so in reality this algorithm No more secure than exploiting X directly - their implication is that most of X, including our social consensus-driven approach, is 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 of this is stone coins, a tribe on the island of Yap who enshrine stone coin ownership in their collective memory Alteration, almost a blockchain (the stones, like bitcoin, are an asset with no intrinsic value).

Why consensus algorithms are necessary is simple, 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 states with perfect accuracy; but they are also very ignorant, because they lack social information, and the consensus algorithm The design challenge is to create algorithms that require as little social input as possible.

Weak subjectivity is the right solution. It relies on human self-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 (reducing weeks to tens of seconds) and to implement highly complex rules for large-scale states. The role of human self-driven consensus is to maintain a consensus on the block hash value over a certain period of time. Assuming 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 chaos in the rules of the blockchain protocol.

Also, note that we don't need to fix N; in theory, we could come up with an algorithm that allows Users lock deposits over N blocks, and these deposits allow users to interpret the security level of the system in a more granular manner. For example, if the user's last login was T blocks ago, and from the current point of view, the lock-up period of 23% of the deposit is longer than T, then the user can use his own subjective scoring function, ignoring the signature of the new deposit, so as to successfully defend Come attack up to 11.5% of total stake. Rising interest rate arrangements could be used to incentivize long-term deposits, or for simplicity we could just rely on altruistic dominant personalities.

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 problems as PoW. However, this view can be objected from three angles.

First, the marginal cost is not the total cost, and the ratio of PoS marginal cost to total cost is much smaller than that of PoW . Users may lock up 50% of their capital for a few months without feeling anything, 70% is a bit of a pain, but without big rewards, locking up 85%+ is unbearable. In addition, different users will have different preferences in locking assets. Because of the combination of these two factors, regardless of what the final equilibrium interest rate is, the marginal cost of locking up the vast majority of capital is much lower.

Second, locked capital It is a private cost, but it is also an act of public interest. Locking up capital means there are fewer coins to trade, so the value of the currency will increase and lead to a redistribution of capital to others, which creates social benefits.

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

Fortunately, there is a way to test these hypotheses: issue a PoS coin, set at 1% per year, 2%, 3% staking rewards, see what percentage of coins are deposited in each case. Users will not be against their own interests, so we can use how much users will spend on consensus to see how much inefficiency this consensus algorithm will bring; if proof of stake is at a lower level of return than proof of work , with a reasonable level of security, 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 success. Ultimately, it may be several years before we can figure out exactly how much the cost of locking up funds is worth.

In short, we have confirmed two points now:

(1) The PoS algorithm can also be safe. To avoid the "nothing-at-stake" problem, change the security model, and weakly embrace subjectivity, both necessary and already adequate.

(2) There are substantial economic reasons to believe that PoS is more economically efficient than PoW. PoS is not agnostic; formalization and research over the past six months have identified strengths and weaknesses that are at least largely on par with PoW, whose mining centralization uncertainty may always exist. Now, it's just a simple question of how to standardize the algorithm and give blockchain developers a choice.

Editor’s note: This article, published in 2014, illustrates how the operation of a PoS system requires us to change our security assumptions. What attracts attention is the author's opinion at the end of the article: "Humans are very good at reaching consensus; the consensus algorithm just speeds up the speed of reaching consensus." This seems to mean that the social consensus driven by humans is enough to support a distributed The security of the traditional system, and the "weak subjectivity" is only a small flaw in the white jade. But are humans good at "reaching" consensus? not. From lawsuits, policy debates, to international disputes and even wars, without exception, it implies that human beings are not good at reaching consensus, because the state as the object of consensus is behind the rules, and human beings will continue to attack the rules and make changes to the rules. Conducive to their own interpretation, and even directly violate the rules. Because in the final analysis, human beings are only good at discovering their own interests, rather than reaching a consensus. Reaching a consensus is often only a step in achieving 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 exactly define a currency and solve the problem of counterfeit currency; but in the world of weak subjectivity, the creation block The currency cannot be defined. To solve the problem of counterfeit currency, unless you are a validator from the genesis block, you can only pretend to be someone else. If the adjudication and interpretation of the latest state of a system depends on a small group of people, then people who do not trust this small group of people will not use the system at all. This loses the so-called "social scalability".