The P + epsilon Attack

Special thanks to Andrew Miller for coming up with this attack, and to Zack Hess, Vlad Zamfir, and Paul Sztorc for discussion and answers.

One of the most interesting surprises in cryptoeconomics in recent weeks has been schelling coin It was invented by Andrew Miller earlier this month. Although SchellingCoin and similar systems (including more advanced systems) have always been understood, truth coin consensus), must rely on a so far new and untested cryptoeconomic security premise – that those who act honestly in a simultaneous consensus game believe that everyone else will do so. can be safely trusted – the issues raised so far include the ability of an attacker to exert a small but increasing amount of influence on the output over time by applying continuous pressure. Address important issues. This attack, on the other hand, points to a more fundamental problem.

The scenario is explained as follows. Suppose there is a simple Schelling game in which users vote on whether a particular fact is true (1) or false (0). In this example, we can say that it is actually false. Each user can vote 1 or 0. If users vote the same as the majority, they will get a reward of P. Otherwise, 0 is returned. Therefore, the payoff matrix becomes:

you cast 0 votes you cast 1 vote
Other people cast 0 votes P 0
Other people cast 1 vote 0 P

The theory is that if everyone expects everyone else to vote honestly, their motivation is to vote honestly themselves in order to follow the majority, which is why others vote honestly in the first place. This is the reason why we can expect this. Self-reinforcing Nash equilibrium.

Now for the attack. Suppose an attacker performs a credible act of paying her , or by leveraging the reputation of a trusted escrow provider). If the majority votes 0, then = P + ε, if the majority votes 1, then he X = 0. Now, the payoff matrix looks like this:

you cast 0 votes you cast 1 vote
Other people cast 0 votes P P+ε
Other people cast 1 vote 0 P

Therefore, the dominant strategy is for everyone to cast one vote, regardless of what the majority does. Therefore, assuming the system is not dominated by altruists, the majority votes 1 and the attacker does not have to pay anything. This attack successfully hijacked the mechanism at zero cost. Note that this is different from Nicholas Hui’s argument. Zero-cost 51% attack on proof of stake (A discussion that is technically scalable to ASIC-based proof-of-work) Here: epistemological takeover is necessary; even if everyone is entrenched in the belief that the attacker will fail, their incentives will still vote in favor of the attacker because the attacker himself bears the risk of failure. It is to do.

Schelling scheme relief

There are several steps you can take to repair the Schelling mechanism. One approach is to use round N + 1 to determine who gets rewarded during round N, rather than having Schelling consensus round N itself determine who gets rewarded based on the “majority is right” principle. Decide which. There are only two default equilibria. Those who vote correctly during round N (both on the actual facts of the issue and on who should be rewarded in round N – 1) should be rewarded. Theoretically, this would require an attacker who wanted to perform a costless attack to destroy not just one round, but all future rounds, and the required capital deposit that the attacker would have to pay. will be unlimited.

However, this approach has two flaws. First, this mechanism is fragile. If an attacker was able to corrupt some round in the distant future by actually paying everyone his P+ε, regardless of who won, the expectation of that corrupted round would cause the attacker to There is an incentive to cooperate in the attack. Backpropagate to all previous rounds. Therefore, breaking one round is costly, but breaking thousands of rounds is not so costly.

Secondly, the reason is discount, the deposit required to overcome this scheme does not have to be infinite. It just has to be very large (i.e. inversely proportional to the prevailing interest rate). But if you just want to increase the minimum amount of bribes required, there is a better and simpler strategy for achieving that. pioneered by Paul Stoltz: Requiring participants to deposit large sums of money and incorporating mechanisms in which the more disputes there are, the more funds are at risk. At the threshold of slightly more than 50% of votes favoring one outcome and 50% favoring the other, the entire deposit is taken away from minority voters. This ensures that the attack still works, but the bribe is not the amount paid each round, but rather the deposit (approximately equal to the amount paid divided by the discount rate), giving performance comparable to an infinite round game. ) must be larger. Therefore, to overcome such a mechanism you would need to be able to prove that you can perform a 51% attack, but perhaps you are just content to assume that no attacker of that size exists. .

Another approach is to rely on counter-adjustment. Essentially, it somehow arranges, perhaps via a reliable commitment, to vote for A (if A is true) with probability 0.6 and vote for B with probability 0.4. The theory is that this allows users to (probabilistically) claim a portion of the mechanism’s rewards and rewards. At the same time bribe of the attacker. This means that rather than paying a fixed reward to each voter that conforms to the majority, the game is structured to get a fixed total reward, and the individual rewards must be adjusted to achieve this goal. It (seems to) work especially well in certain games. In such a situation, from a collective rationality perspective, 49% of group members would vote for B to claim the attacker’s reward, and 51% would vote for B to ensure that the attacker’s reward is paid. It is true that you can gain the most by voting for A. .

However, this approach itself has a flaw in that if the attacker’s bribe is high enough, he or she can still defect. The basic problem is that given a stochastic mixed strategy between A and B, the returns to each always vary (approximately) linearly with the stochastic parameters. Therefore, if it is more rational for an individual to vote for B than for A, then it is more rational to vote for B with probability 0.51 than with probability 0.49, and voting for B with probability 1 also works . Better.

Therefore, simply voting 1 all the time forces everyone out of the “49% to 1” strategy, allowing 1 to win and the attacker to successfully take over at no cost. The fact that such a complex plan exists and is so close to “appearing to work” suggests that perhaps some complex counter-coordination plan that actually works will emerge in the near future. I am. However, one must prepare for the contingency that such a plan is not developed.

further results

The vast number of crypto-economic mechanisms that Schering coins enable and the importance of such schemes in almost all purely “trust-free” attempts to forge any kind of link between the crypto world and the real world. Given its nature, this attack poses a potentially serious threat. – However, as we will see later, Schelling schemes as a category are ultimately partially salvageable. More interesting, however, is a much larger class of mechanisms that at first glance look nothing like Schering coins, but in fact have very similar strengths and weaknesses.

In particular, let’s take proof of work as a very specific example. In fact, proof of work is a multiple equilibrium game in much the same way as a Schelling scheme. If there are two forks, A and B, he can earn 25 BTC by mining on the winning fork. You won’t gain anything if you end up losing.

you are mine in A you are mine in B
Others mine with A twenty five 0
Others mine with B 0 twenty five

Now suppose an attacker launches a double-spend attack against many parties simultaneously (this requirement ensures that there is no single party with very strong incentives to oppose the attacker, The opposite would instead be a public good; alternatively, double spending could be a purely public good). The attacker attempts to crash the price by selling short with her 10x leverage), calling the “main” chain A and the attacker’s new double-spending fork B. By default, everyone expects A to win. However, the attacker promises that if B loses, he will pay everyone who mined with B 25.01 BTC. Therefore, the payoff matrix becomes:

you are mine in A you are mine in B
Others mine with A twenty five January 25th
Others mine with B 0 twenty five

Therefore, the attacker wins and pays nothing because mining on B is the dominant strategy, regardless of an individual’s epistemic beliefs, so everyone mines on B. In particular, with proof-of-work there is no deposit, so the level of bribe required will be proportional only to the product of the mining reward and the length of the fork, rather than his 51% capital cost of all mining equipment. be careful. So from a cryptoeconomic security perspective, in some sense, proof of work has virtually no cryptoeconomic security margin at all (which is why proof of stake opponents say next If you are tired of pointing out things like This article by Andrew Poelstra, feel free to link here as a reply). If you are really feeling uncomfortable, Weak subjectivity Considering pure proof-of-stake conditions, perhaps the correct solution is to enhance proof-of-work with hybrid proof-of-stake by adding deposit and double voting penalties to mining. This means that there is a possibility.

In reality, of course, despite this flaw, proof of work is here to stay, and in fact may continue to be around for a long time to come. It may be only if the degree of altruism is high enough that he is not 100% sure that the attacker will actually succeed. However, if you are allowed to rely on altruism, a simple proof of stake can work just fine. Therefore, Schelling schemes may also simply work in practice, even if they are not completely sound in theory.

In the next part of this post, I will elaborate on the concept of “subjective” mechanisms and how they can be used to theoretically avoid those problems.

Related Article


Leave a Comment