The P + Epsilon attack

A special thanks to Andrew Miller for finding this attack, and Zack Hess, Vlad Zamfir and Paul Sztorc for the discussion and the answers

One of the most interesting surprises in cryptocurrency in recent weeks has come from an attack on Schellingcoin Designed by Andrew Miller at the beginning of the month. Although it has always been understood that Schellingcoin and similar systems (including the most advanced Truth Consensus), count on what is so far a new cryptochemical security hypothesis not tested – which can be safely counted on people acting honestly in a simultaneous consensus game simply because they believe that everyone – the problems that have been raised so far have to do with relatively marginal production such as the capacity of the attacker. This attack, however, shows a much more fundamental problem.

The scenario is described as follows. Suppose that there is a simple schelling game where users vote to find out if a special fact is true (1) or false (0); Say in our example that it is actually false. Each user can vote 1 or 0. If a user votes the same thing as the majority, he obtains a P reward; Otherwise, they get 0. Thus, the payment matrix seems as follows:

The theory is that if everyone expects everyone to vote honestly, then their incitement is also to vote honestly in order to comply with the majority, and that is the reason why we can expect that others vote honestly in the first place; A self-reinforcing Nash balance.

Now the attack. Suppose that the attacker is credible (for example via an Ethereum contract, simply putting his reputation into play, or by taking advantage of the reputation of a supplier from Suste in trust) to pay X to voters who voted 1 after the game, where x = P + ε if the majority vote 0, and x = 0 if the majority votes 1. Now, matrix payment looks like this:

Thus, it is a dominant strategy for anyone to vote 1, no matter what you think that the majority will do. Consequently, assuming that the system is not dominated by the altruists, the majority will vote 1, and therefore the attacker will have nothing to pay for everything. The attack managed to resume the mechanism at zero cost. Note that this differs from the argument of Nicholas Houy on 51% attacks at zero cost against proof of stake (an argument technically extensible to proof of work based on ASIC) in that here Epistemic take-over is required; Even if everyone remains dead in a conviction that the attacker will fail, his incentive is always to be voted to support the attacker, because the attacker himself takes the risk of failure.

Recovery diagrams

There are a few avenues that can be taken to try to recover the Schelling mechanism. An approach is that instead of the Tour N of the Schelling consensus itself deciding which is rewarded according to the principle of the “majority is correct”, we use the round N + 1 to determine who should be rewarded during the Tour N, the default balance being that only the people who voted properly during the round N (both on the real fact in question and on which should be rewarded in round. Theoretically, this requires an attacker wishing to make an attack at no cost to corrupt not only a turn, but also all the future towers, which means that the attacker must make the required capital that the attacker must make.

However, this approach has two faults. First of all, the mechanism is fragile: if the attacker manages to corrupt a tour in the distant future by really paying P + ε to everyone, no matter who wins, then the expectation of this corrupt tower causes an incentive to cooperate with the attacker to behave at all the previous rounds. Therefore, the corruption of a lap is expensive, but corrupting thousands of laps is not much more expensive.

Second, because of newsThe deposit required to overcome the regime does not need to be infinite; You just have to be very very important (that is to say inversely proportional to the interest rate in force). But if all we want is to make the minimum-required bridge juice, then there is a much simpler and better strategy to do it, Pioneer by Paul Storcz: Require participants that they deposit a large deposit and build a mechanism by which the more links, the more funds at stake. At the limit, where a little more than 50% of the votes are in favor of a result and 50% in favor of the other, all of the deposit it has removed from minority voters. This guarantees that the attack is still working, but the bridge pot must now be higher than the deposit (almost equal to the payment divided by the discount rate, which gives us equal performance to the infinite round game) rather than the simple payment for each round. Therefore, in order to overcome such a mechanism, we should be able to prove that we are able to make an attack of 51%, and perhaps we can simply be comfortable to assume that attackers of this size do not exist.

Another approach is to rely on counter-coordination; Essentially, in a way coordinated, perhaps via credible commitments, on voting A (if A is the truth) with a probability of 0.6 and B with a probability of 0.4, the theory being that it will allow users to claim (probabilistic) the reward of the mechanism and part of the attacker at the same time. This (seems) to work particularly well in the games where instead of paying a constant reward to each voter in accordance with the majority, the game is structured to have a constant total gain, adjusting individual gains to achieve this objective is necessary. In such situations, from the point of view of collective rationality, it is indeed the case that the group makes the most profit by having 49% of its members voting B to claim the award of the attacker and 51% of voting has to ensure that the attacker’s reward is paid.

However, this approach itself suffers from the defect that, if the striker of the attacker is sufficiently high, even from there, we can make defection. The fundamental problem is that, given a probabilistic mixed strategy between A and B, for everyone, the return always (almost) linearly changes with the probability parameter. Therefore, if, for the individual, it is more logical to vote for B than for A, it will also be more logical to vote with a probability of 0.51 for B than with a probability of 0.49 for B, and the vote with probability 1 for B will work even better.

Consequently, everyone is lacking in the “49% for 1” strategy will simply vote for 1, and therefore 1 will win and the attacker will have managed to take a profitable takeover. The fact that there are such complicated regimes and are getting closer so close to “seem to function” suggests that perhaps in the near future, a complex counter-coordination scheme will emerge that actually works; However, we must be prepared for the possibility that no diagram of this type will be developed.

Other consequences

Given the large number of cryptoeconomic mechanisms that Schellingcoin makes possible, and the importance of these programs in almost all the attempts purely “without confidence” to forge any type of link between the cryptographic world and the real world, this attack represents a serious potential threat – although, as we will see later, the schemes schelling as a category are partly valid. However, what is more interesting is the much larger class of mechanisms that does not look like Schellingcoin at first glance, but in fact have very similar sets of strengths and weaknesses.

In particular, let us indicate a very specific example: proof of work. The proof of work is actually a multi-balance game in the same way as the Schelling schemes are: if there are two forks, A and B, then if you undermine the fork that ends up winning, you get 25 BTC and if you mine at the fork that ends up losing, you get nothing.

Suppose now that an attacker is launching a double expenditure attack against many parties simultaneously (this requirement guarantees that there is no single party with a very strong incentive to oppose the attacker, the opposition becoming rather a public good; alternately the two expenses could be purely an attempt to break the price with the short-circuit of the attacker at 10x lever), and everyone The striker for the double expenditure for B. by default. However, the attacker begins crediblely to pay 25.01 BTC to all those who mines on B if B ends up losing. Therefore, the payment matrix becomes:

Thus, the mining on B is a dominant strategy, whatever the epistemic beliefs, and therefore everyone mines on B, and therefore the attacker wins and does not pay anything at all. In particular, note that in the evidence of work, we have no deposits, so the required broth level is proportional only to the mining award multiplied by the length of the fork, and not at the cost of capital of 51% of all the mining equipment. Consequently, from the point of view of cryptoeconomic security, we can in a way say that proof of work has practically no margin of cryptoeconomic security (if you are tired of the opponents of proof of stake that point to you towards This article by Andrew PoelstraDo not hesitate to link them here in response). If we are really uncomfortable with the low subjectivity State of pure proof of participation, it follows that the correct solution could perhaps be to increase the evidence of work with hybrid proof of participation by adding security deposits and double voting penalties to mining.

Of course, in practice, proof of work has survived despite this defect, and in fact, it can continue to survive for a long time; It may be simply the case that there is a sufficiently high degree of altruism that attackers are not really 100% convinced that they will succeed – but then, if we are allowed to count on altruism, the naive proof of participation also works well. Consequently, the Schelling diagrams could also eventually work in practice, even if they are not perfectly solid in theory.

The next part of this article will discuss in more detail about the concept of “subjective” mechanisms, and how they can be used to theoretically circumvent some of these problems.