Ethereum Blog

The P + epsilon Attack

Introduction

user

Vitalik Buterin


LATEST POSTS

Ethereum Dev Roundup: Q1 (Boring Edition) 07th April, 2017

Ethereum Dev Roundup: Q1 01st April, 2017

technical

The P + epsilon Attack

Posted on .

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

One of the more interesting surprises in cryptoeconomics in recent weeks came from an attack on SchellingCoin conceived by Andrew Miller earlier this month. Although it has always been understood that SchellingCoin, and similar systems (including the more advanced Truthcoin consensus), rely on what is so far a new and untested cryptoeconomic security assumption – that one can safely rely on people acting honestly in a simultaneous consensus game just because they believe that everyone else will – the problems that have been raised so far have to do with relatively marginal issues like an attacker’s ability to exert small but increasing amounts of influence on the output over time by applying continued pressure. This attack, on the other hand, shows a much more fundamental problem.

The scenario is described as follows. Suppose that there exists a simple Schelling game where users vote on whether or not some particular fact is true (1) or false (0); say in our example that it’s 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. Thus, the payoff matrix looks as follows:

You vote 0 You vote 1
Others vote 0 P 0
Others vote 1 0 P

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.

Now, the attack. Suppose that the attacker credibly commits (eg. 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. Now, the payoff matrix looks like this:

You vote 0 You vote 1
Others vote 0 P P + ε
Others vote 1 0 P

Thus, 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. Note that this differs from Nicholas Houy’s argument about zero-cost 51% attacks on proof of stake (an argument technically extensible to ASIC-based proof of work) in that here no epistemic takeover is required; even if everyone remains dead set in a conviction that the attacker is going to fail, their incentive is still to vote to support the attacker, because the attacker takes on the failure risk themselves.

Salvaging Schelling Schemes

There are a few avenues that one can take to try to salvage the Schelling mechanism. One approach is that instead of round N of the Schelling consensus itself deciding who gets rewarded based on the “majority is right” principle, we 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. Theoretically, this requires an attacker wishing to perform a cost-free attack to corrupt not just one round, but also all future rounds, making the required capital deposit that the attacker must make unbounded.

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 (ie. 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. At the limit, where slightly over 50% of votes are in favor of one outcome and 50% in favor of the other, the entire deposit it taken away 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 discounting rate, giving us equal performance to the infinite-round game) rather than just the payout for each round. Hence, in order to overcome such a mechanism, one would need to be able to prove that one is capable of pulling off a 51% attack, and perhaps we may simply be comfortable with assuming that attackers of that size do not exist.

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. This (seems to) work particularly well in games where instead of paying out a constant reward to each majority-compliant voter, the game is structured to have a constant total payoff, adjusting individual payoffs to accomplish this goal is needed. In such situations, from a collective-rationality standpoint it is indeed the case that the group earns a highest profit by having 49% of its members vote B to claim the attacker’s reward and 51% vote A to make sure the attacker’s reward is paid out.



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.



Hence, everyone will defect from the “49% for 1” strategy by simply always voting for 1, and so 1 will win and the attacker will have succeeded in the costless takeover. The fact that such complicated schemes exist, and come so close to “seeming to work” suggests that perhaps in the near future some complex counter-coordination scheme will emerge that actually does work; however, we must be prepared for the eventuality that no such scheme will be developed.

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 – although, as we will later see, Schelling schemes as a category are ultimately partially salvageable. 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.

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 25 0
Others mine on B 0 25

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 25 25.01
Others mine on B 0 25

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. Particularly, note that in proof of work we do not have deposits, so the level of bribe required is proportional only to the mining reward multiplied by the fork length, not the capital cost of 51% of all mining equipment. Hence, from a cryptoeconomic security standpoint, one can in some sense say that proof of work has virtually no cryptoeconomic security margin at all (if you are tired of opponents of proof of stake pointing you to this article by Andrew Poelstra, feel free to link them here in response). If one is genuinely uncomfortable with the weak subjectivity condition of pure proof of stake, then it follows that the correct solution may perhaps be to augment proof of work with hybrid proof of stake by adding security deposits and double-voting-penalties to mining.

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

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

profile

Vitalik Buterin

https://ethereum.org

Comments
user

Author Dima Starodubcev

Posted at 9:41 pm January 28, 2015.

Do i understand correctly that DPOS is more resistant to this kind of attack than POW?

Reply
    user

    Author Vitalik Buterin

    Posted at 1:46 am January 29, 2015.

    DPOS technically has only the weaker altruism-prime level of formal cryptoeconomic security, since attackers can bribe rational actors to vote for them. It essentially relies on either (i) people enjoying civic activism as a hobby, or (ii) wealth concentration, as a security assumption, and the latter is hard to guess in the long term and the former is hard to model 🙂

    Reply
      user

      Author Matias Romeo

      Posted at 9:50 am January 29, 2015.

      Even if an attacker could bribe a group of shareholders (or a wealthy one) to vote for him (against their interests), other shareholders can remove him from the elected position which in fact will imply a loss for the attacker.

      I cant see incentives for the attacker given that he knows that the damage he can make to the network will be very short in time (if any)?

      Reply
        user

        Author Vitalik Buterin

        Posted at 6:14 pm January 30, 2015.

        > other shareholders can remove him

        But what if 51% of them get bribed? This does not require active collusion; just an automatic daemon paying out $5 to anyone who votes for the attacker, after which point people will see the pattern and join in. It’s a tragedy-of-the-commons problem. So DPOS requires 51% altruism, which is a quite different assumption from 51% non-collusion.

        (Although DPOS in practice is somewhat more secure, because in actuality it works a bit differently from the way people think it works; I’ll expand on this in my next post)

        Reply
          user

          Author Matias Romeo

          Posted at 6:23 am January 31, 2015.

          > what if 51% of them get bribed

          51% of the shareholders != 51% of the voting power.

          The vote is not forever, and can be changed anytime.

          So a rational shareholder can receive the $5 and quickly remove his vote since he knows that maintaining his vote for a bad behaving delegate will only harm the value of his shares.

          The dynamic for electing or removing a delegate is very quick (10 seconds), so we can think of it as continuos election process based on some public visible metrics.

          Another different thing is instead of buying “votes” the attacker could buy shares (the necessaries to vote for himself) to later destruct the network.

          We can think of it as a takeover of the company in order to break it later.

          If this happens shareholders can thanks the attacker for the money, fork the network on a consensus block, and start all over again.

user

Author Joshua Davis

Posted at 3:12 am January 29, 2015.

This is so awesome. I’ve been working on this exact problem for more than 100 hours for my insurance DAO and I learned a couple of important things:

1. Schelling games work best when the participants are protecting a common resource that already belongs to them and their reporting of the truth is motivated several factors at the same time:
A. Do I get a reward if I guess the correct answer?
B. If I provide a corrupt answer or if I attempt to collude with other players will this harm the reputation of the system that I have a vested interest in? Example: in the case of an insurance DAO if schelling points could be used to determine the outcome of claims then corrupt answers would harm the reputation of the DAO into which participants have already paid their premiums. Why then would perspective applicants desire to open up a new policy? If I am incentivized to see an increase in policy holders then I am incentivized to maintain the reputation of the system (dividend awards for mutual insurance companies).
C. If I provide a corrupt answer or if I attempt to collude with other players will this create a trend that would render the system corrupt in the future when I need to benefit from its use? Example: in the case of insurance if the claims process is corrupted to the point where the claims cannot be fairly determined then if in the future I become a claimant I will not be fairly awarded thus I should fairly award claims.

2. Schelling games work well when questions can be rephrased such that the system receives a range of answers rather than only yes or no and only a few closest to the median get rewarded. Yes the attacker can broadcast what he wants people to vote and he can set up a smart contract to bribe those who voted with him but what if among 21 participants there is only one award given for the answer which is the median. In the case of multiple people choosing the same answer which happens to be the median then one of them is selected at random. The attacker broadcasting the attack value and then providing bribes would require that he actually pay out all those bribes since in the example given above the attacker doesn’t pay a price if the majority agrees with him because they are awarded for being in the majority and in this case that award only goes to 1 out of 21 participants. Trying to award the 50% closest to the median and excluding the two 25% outlier guesses doesn’t seem to work nearly as good as providing a large award to the 1, 2 or 3 people who actually are the median.

Anyways just my 2 cents. This article was excellent but I think that there are multiple strategies for overcoming these types of attacks. No questions exist which must of necessity be phrased as a yes or a no a 1 or a 0. It is my assertion that every question which seems binary can in actuality be rephrased to produce a range of answers. Even when deciding if a will and testament should be paid out by asking the question “Is this person alive” that question could be rephrased as “two Schelling games of 21 people are taking place simultaneously and you need to guess the number of people in the other schelling game who will vote that this person is actually dead.” Then compare the answers against each other and provide only one award to the person closest to the median (chosen at random if necessary).

~J

Reply
user

Author Robert

Posted at 2:14 pm January 29, 2015.

Sounds like Warren Buffet’s Billionaire’s Buyout Plan, http://www.gametheory.net/News/Items/013.html

Reply
    user

    Author Joshua Davis

    Posted at 11:53 pm January 29, 2015.

    I just read you link. Very cool!

    Reply
    user

    Author pidgeon

    Posted at 6:54 am March 24, 2015.

    The question really comes down to whether or not you believe algorithms that take power away from people are the solution to our problems. As for me, it makes perfect sense to empower people who choose to join/leave a system and enjoy the dynamic fluctuations that come along with real human empowered foundations of blockchain governance.

    Some people actually believe that an algorithm can rule a system better than we can. This is concerning…especially when coupled with a short/medium-term profit motive.

    Reply
    user

    Author zack

    Posted at 7:29 pm April 17, 2015.

    It looks like Warren Buffet invented this attack, not Andrew Miller.

    Reply
user

Author Eugene Wang

Posted at 3:32 am January 30, 2015.

To me, this sounds like a financial 51% attack. There’s a caveat to the attack: If the attacker is known to not have enough funds to pay that 51% of the money, the nash equilibrium will settle at the point where the attacker can pay everyone that participates in the attack, and the attack falls flat.

Reply
user

Author Vagarantoui

Posted at 8:58 pm February 1, 2015.

Yep understood none of that! But im more certain than ever that you guys are doing the right thing and making the world a better place. In our society we are not allowed to discuss certain subjects even with good intentions. I hope your system allows us to create all kinds of places where people can talk to each other without fear and come to solutions based on truth.

Reply
user

Author crainbf

Posted at 10:46 pm March 29, 2015.

Ah, somehow had missed this post.

We did an episode just recently describing attacking Bitcoin in very similar ways:
– Bribing miners to join the attack so they’re economically incentivized to do so regardless of their beiief about the probability the attack will succeed.
– Shorting Bitcoin in financial markets so the goal of the attack is to crash the price, not to double-spend.
(- Optional: Executing the attack after the block halving, when the hash rate, value of hardware and thus cost of attack all collapse).

It wouldn’t be possible now, but when there is a way to short bitcoin without owning bitcoin (e.g. Bitcoin ETF or OTC derivative market on Wall St.), this will become possible and I think that would be extremely dangerous for Bitcoin.

https://letstalkbitcoin.com/blog/post/epicenter-bitcoin-68-kamikaze-attack-block-halving-and-the-perils-of-proof-of-work

Reply
user

Author psztorc

Posted at 5:24 pm May 16, 2015.

As you’ve indicated right at the top, we’ve discussed this attack and I don’t find it relevant. On my forum I pushed a pro-Truthcoin defense (“mixing”) which went above and beyond and actually let you milk the attacker, but here let me push the general defense (“counter-contracts”) which simply makes the attack irrelevant:

[1] Strategy is a portfolio of real options.

[2] Let r(s) be “the real option to execute a P+e attack, targeting behavior s for promotion”.

[3] In your proof of work example above, you claim that r(B) costs zero.

attacker credibly commits to paying out 25.01 BTC to everyone who mines on B if B ends up losing.

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.

[4] If that is the case, I have the option to introduce r(A), also at a cost of zero. This pays “out 25.01 BTC to everyone who mines on A if A ends up losing”.

[5] Combined, r(B) and r(A) yield something which “pays out 25.01 on B if B loses” and “pays out 25.01 on A if A loses”. If A wins, nothing extra is generated on A; if B wins, nothing extra is generated on B. Only worthless coins are generated on worthless forks.

You didn’t even need r() to do that, any DoubleSpendAttempt() would have done the same.

By the way, you’ve spelled my name correctly at the top, but incorrectly in the hyperlinked section (people misspell my name all the time, I’m over it). And thanks for the shoutouts.

Reply
    user

    Author Vitalik Buterin

    Posted at 5:55 am May 17, 2015.

    So this is the “altruists can make counter-contracts” argument. Sure, I agree. But if we are relying on altruists to be stronger than attackers, then we might as well just forget the incentivization and have a simple vote.

    Reply
      user

      Author psztorc

      Posted at 5:58 am May 17, 2015.

      But if we are relying on altruists to be stronger than attackers,
      We are not. r(*) costs counter-attackers nothing, just as it cost the attacker nothing. This does not involve altruism whatsoever.

      Reply

Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

View Comments (16) ...
Navigation