P + Epsilon attack

Special thanks to Andrew Miller for presenting this attack, and to Zach Hess, Vlad Zamfir, and Paul Storck for discussion and responses.

One of the most interesting surprises in the crypto economy in recent weeks came from the attack on Shilling currency Conceived by Andrew Miller earlier this month. Although it has always been understood that SchellingCoin and similar systems (including more advanced ones). Truth Queen Consensus), which relies on what is so far a new and untested assumption of cryptoeconomic security – that one can safely rely on people behaving honestly in a concurrent consensus game just because they think everyone else will do so – the problems raised so far must be addressed. Relatively marginal issues such as the attacker’s ability to exert small but increasing amounts of influence on the outcome over time by applying sustained pressure. On the other hand, this attack shows a more fundamental problem.

The scenario is described as follows. Suppose there is a simple Schelling game in which users vote on whether or not a given fact is true (1) or false (0); Let’s assume in our example that it is actually wrong. Each user can vote 1 or 0. If the user votes with the same majority vote, he will receive a reward P; Otherwise they would get 0. Therefore, the payoff matrix looks like this:

The theory is that if everyone expects everyone else to vote honestly, then their incentive is to vote honestly as well in order to conform to the majority, which is why one would expect others to vote honestly in the first place; Self-reinforcing Nash equilibrium.

And now the attack. Suppose the attacker credibly commits (for example, through an Ethereum contract, or simply by putting one’s reputation at risk, or by leveraging the reputation of a trusted collateral provider) to pay X to voters who voted 1 after the game ends, where X = P + ε if the majority voted 0, and X = 0 if the majority voted 1. Now, the payoff matrix looks like this:

Thus, it is a dominant strategy for anyone to vote 1 regardless of what you think the majority will do. Hence, assuming that the system is not controlled by influencers, the majority would vote 1, and thus the attacker would not need to pay anything at all. The attack succeeded in taking control of the mechanism at no cost. Note that this differs from Nicholas Hoy’s argument about 51% zero cost attacks on Proof of Stake (a technically scalable argument for ASIC-based proof-of-work) where there is none here Cognitive appropriation required; Even if everyone remains completely convinced that the attacker will fail, their incentive is still to vote to support the attacker, because the attacker bears the risks of failure himself.

Saving Schelling charts

There are a few avenues one can take to try to salvage the Schelling mechanism. One approach is that instead of the Nth round of Schelling consensus itself determining who gets the reward based on the “majority is right” principle, we use the N+1 round to determine who should be rewarded during the Nth round, with the default equilibrium being that only Reward people who vote correctly during Round N (either on the actual fact in question or on who should be rewarded in Round N – 1). In theory, this requires an attacker willing to perform a free attack to spoil not just one round, but all future rounds, making the required capital deposit the attacker must make unlimited.

However, this approach has two drawbacks. First, the mechanism is fragile: if an attacker can spoil a round in the distant future by paying P + ε to everyone, regardless of who wins, the expectation of that spoiled round causes an incentive to cooperate with the attacker in order to backpropagate all previous rounds. Hence, spoiling a single round is expensive, but spoiling thousands of rounds is not much more expensive.

Secondly because rivalThe deposit required to beat the scheme need not be infinite; It just has to be very large (i.e. inversely proportional to the prevailing interest rate). But if all we want is to increase the minimum bribe requirement, there is a much simpler and better strategy for doing so. Created by Paul Storks: Requiring participants to make a large deposit, and building a mechanism whereby the greater the dispute, the more money is at risk. At the high end, where just over 50% of the votes are for one outcome and 50% for the other, the entire deposit you took from minority voters. This ensures that the attack still works, but the bribe must now be greater than the deposit (roughly equal to the payout divided by the discount rate, giving us equal performance for an infinite round game) rather than just the payout per round. Thus, in order to overcome such a mechanism, one would need to be able to prove that one can perform a 51% attack, and we may be comfortable simply assuming that there are no attackers of that size.

Another approach is to rely on counter-coordination; Essentially, somehow coordinating, perhaps through reliable commitments, on voting A (if A is the truth) with probability 0.6 and probability B 0.4, the theory being that this would allow users to (probabilistically) claim the mechanism’s reward and part of the reward. Bribe the attacker at the same time. This (seems) to work particularly well in games where instead of paying a fixed reward to each majority-compliant voter, the game is designed to have a fixed overall reward, and individual rewards need to be adjusted to achieve this goal. In such situations, from the point of view of collective rationality, the group achieves the highest profit by having 49% of its members vote B to claim the attacker’s bounty and 51% vote A to ensure that the attacker’s bounty is paid. .

However, this approach itself has the flaw that if the attacker’s bribe is high enough, it is even possible for him to defect. The basic problem is that in the presence of a probabilistic mixed strategy between A and B, the return always changes (almost) linearly with the probability parameter. Hence, if it makes more sense for an individual to vote for B than to vote for A, then it would also make more sense for an individual to vote with a probability of 0.51 for B than to vote with a probability of 0.49 for B, and voting with a probability of 1 for B will work even better.

Hence, everyone will defect to the “49% to 1” strategy by simply always voting for 1, so 1 will win and the attacker will have succeeded in the free take. The fact that such complex schemes exist, and that they are close to a “successful phenomenon,” suggests that perhaps in the near future complex counter-coordination schemes that actually work will emerge; However, we must be prepared for the possibility that such a scheme will not be developed.

Other consequences

Given the sheer number of cryptoeconomic mechanisms enabled by SchellingCoin, and the importance of such schemes in almost all purely “trust-free” attempts to establish any kind of connection between the crypto world and the real world, this attack poses a potentially serious threat – although, As we will see later, Schelling schemes as a class are ultimately only partially salvageable. However, what is even more interesting is the much larger class of mechanisms that don’t look exactly like SchellingCoin at first glance, but actually have very similar sets of strengths and weaknesses.

In particular, let us point to one very specific example: proof of work. Proof of work is actually a multi-equilibrium game in the same way that Schelling diagrams are: if there are two forks, A and B, then if you mine the fork that ends in a win, you get 25 bitcoins and if you mine the fork that ends in a loss you get nothing .

Now, suppose the attacker launches a double-spend attack against many parties simultaneously (this requirement ensures that no single party has a very strong incentive to oppose the attacker, and instead the opposition becomes a public good; instead, the double-spending could simply be an attempt Breaking the price by the attacker shorting with 10x leverage), calling the “main” chain A and a new double-spending fork for attacker B. By default, everyone expects A to win. However, the attacker is credibly committed to paying 25.01 BTC to everyone who mines B’s coin if it finishes B is at a loss. Then the payoff matrix becomes:

Thus, mining on B is a dominant strategy regardless of one’s epistemological beliefs, so everyone mines B, and thus the attacker wins and pays nothing at all. In particular, note that in Proof of Work we have no deposits, so the level of bribe required is only proportional to the mining reward multiplied by the fork length, not the 51% capital cost of all mining equipment. Hence, from the point of view of crypto-economy security, one can more or less say that Proof-of-Work has no margin of safety for the crypto-economy at all (if you’re tired of Proof-of-Stake opponents directing you to… This article was written by Andrew Poelstra(Feel free to link it here in response). If the person is really uncomfortable with Weak self In the case of pure proof-of-stake, it follows that the correct solution might be to augment proof-of-work with hybrid proof-of-stake by adding security deposits and double-voting penalties to the mining.

Of course, in practice, proof of work has survived despite this flaw, and may even continue to survive for a long time; It may just be that there is a high enough degree of altruism that the attackers are not 100% convinced that they will succeed – but then, if we are allowed to rely on altruism, naive proof of stake works well too. Hence, Schelling’s schemes too may simply end up working, even if they are not entirely theoretically sound.

The next part of this post will discuss the concept of “self” mechanisms in more detail, and how they can be used to get around some of these issues theoretically.