The P + epsilon Attack

The P + epsilon Attack: A Fundamental Flaw in SchellingCoin

In recent weeks, a surprising attack on SchellingCoin has shed light on a fundamental problem in cryptoeconomics. Conceived by Andrew Miller, the attack highlights a flaw in the mechanism's security assumption, which has been a topic of discussion among experts. The attack, known as the P + epsilon attack, demonstrates that even with a simultaneous consensus game, the system can be vulnerable to manipulation.

The Attack Scenario

The scenario is as follows: suppose there exists a simple Schelling game where users vote on whether or not some particular fact is true (1) or false (0). In this example, let's assume the fact is actually false. Each user can either vote 1 or 0. If a user votes the same as the majority, they get a reward of P; otherwise, they get 0. The payoff matrix looks as follows:

The theory is that if everyone expects everyone else to vote truthfully, then their incentive is to also vote truthfully in order to comply with the majority, and that's the reason why one can expect others to vote truthfully in the first place; a self-reinforcing Nash equilibrium.

The P + epsilon Attack

Now, suppose that the attacker credibly commits (e.g., via an Ethereum contract, by simply putting one's reputation at stake, or by leveraging the reputation of a trusted escrow provider) to pay out X to voters who voted 1 after the game is over, where X = P + ε if the majority votes 0, and X = 0 if the majority votes 1. The payoff matrix looks like this:

The Dominant Strategy

It's a dominant strategy for anyone to vote 1 no matter what you think the majority will do. Hence, assuming the system is not dominated by altruists, the majority will vote 1, and so the attacker will not need to pay anything at all. The attack has successfully managed to take over the mechanism at zero cost.

Salvaging Schelling Schemes

There are a few avenues that one can take to try to salvage the Schelling mechanism. One approach is to use round N + 1 to determine who should be rewarded during round N, with the default equilibrium being that only people who voted correctly during round N (both on the actual fact in question and on who should be rewarded in round N - 1) should be rewarded.

However, this approach has two flaws. First, the mechanism is fragile: if the attacker manages to corrupt some round in the far future by actually paying up P + ε to everyone, regardless of who wins, then the expectation of that corrupted round causes an incentive to cooperate with the attacker to back-propagate to all previous rounds. Hence, corrupting one round is costly, but corrupting thousands of rounds is not much more costly.

Second, because of discounting, the required deposit to overcome the scheme does not need to be infinite; it just needs to be very very large (i.e., inversely proportional to the prevailing interest rate). But if all we want is to make the minimum required bribe larger, then there exists a much simpler and better strategy for doing so, pioneered by Paul Storcz: require participants to put down a large deposit, and build in a mechanism by which the more contention there is, the more funds are at stake.

Counter-Coordination

Another approach is to rely on counter-coordination; essentially, somehow coordinate, perhaps via credible commitments, on voting A (if A is the truth) with probability 0.6 and B with probability 0.4, the theory being that this will allow users to (probabilistically) claim the mechanism's reward and a portion of the attacker's bribe at the same time.

However, this approach itself suffers from the flaw that, if the attacker's bribe is high enough, even from there one can defect. The fundamental problem is that given a probabilistic mixed strategy between A and B, for each the return always changes (almost) linearly with the probability parameter. Hence, if, for the individual, it makes more sense to vote for B than for A, it will also make more sense to vote with probability 0.51 for B than with probability 0.49 for B, and voting with probability 1 for B will work even better.

Further Consequences

Given the sheer number of cryptoeconomic mechanisms that SchellingCoin makes possible, and the importance of such schemes in nearly all purely "trust-free" attempts to forge any kind of link between the cryptographic world and the real world, this attack poses a potential serious threat. However, what is more interesting is the much larger class of mechanisms that don't look quite like SchellingCoin at first glance, but in fact have very similar sets of strengths and weaknesses.

Proof of Work

Particularly, let us point to one very specific example: proof of work. Proof of work is in fact a multi-equilibrium game in much the same way that Schelling schemes are: if there exist two forks, A and B, then if you mine on the fork that ends up winning you get 25 BTC and if you mine on the fork that ends up losing you get nothing.

You mine on A You mine on B Others mine on A 250 Others mine on B 025

Now, suppose that an attacker launches a double-spend attack against many parties simultaneously (this requirement ensures that there is no single party with very strong incentive to oppose the attacker, opposition instead becoming a public good; alternatively the double spend could be purely an attempt to crash the price with the attacker shorting at 10x leverage), and call the "main" chain A and the attacker's new double-spend fork B. By default, everyone expects A to win. However, the attacker credibly commits to paying out 25.01 BTC to everyone who mines on B if B ends up losing. Hence, the payoff matrix becomes:

You mine on A You mine on B Others mine on A 2525.01 Others mine on B 025

Thus, mining on B is a dominant strategy regardless of one's epistemic beliefs, and so everyone mines on B, and so the attacker wins and pays out nothing at all.

Conclusion

The P + epsilon attack highlights a fundamental flaw in SchellingCoin and Modern Cryptoeconomic Mechanisms. Despite the best efforts of experts, the attack demonstrates that even with a simultaneous consensus game, the system can be vulnerable to manipulation. The attack has serious implications for the security of various cryptoeconomic mechanisms, including proof of work and proof of stake. While there are avenues to salvage the Schelling mechanism, the attack highlights the need for further research and development in the field of cryptoeconomics.

Source: https://blog.ethereum.org/en/2015/01/28/p-epsilon-attack