Bribery: The Double Double Spend

[cunicula]

Attackers can easily bribe rational miners to double spend using txn fees. [this seems likely to have been discussed before; point me there if my discussion is old hat]

Say attacker starts with significant balances in two addresses at block t-1: D (double-spend) and B bribe; attacker also has empty addresses as follows: A1,A2,... and C.

1) Mine a secret side chain block that extends block t-1, In the first block of your side chain, include a txn that (secretly) transfers B->A1.  (wait to get 1 side chain block before moving to step 2)
2) On the main chain in block t, send D to purchase something you want to steal. Simultaneously, include a txn that sends B->C in this block. (this is the 'double double-spend.' You plan to reverse both txns.)
3) Wait to get the good you purchased using D (the sooner the better)
4) Announce your attack chain. Send a sequence of bribes as follows: send a high-fee txn from A1 to A2. After this enters a block, send a high-fee txn from A1 and A2 to A3. After this enters a block send a high-fee txn from A1 and A3 to A4, keep sending out the bribe sequence until you overtake the main chain or your bribe fund is exhausted.
5) Simultaneously, after each attack block is found, identify the generation address on the attack block. On the main chain, Send block reward to this generation address using address C. These sends gets reversed if the attack succeeds. If the attack fails, these sends compensate the attack miners for participation.


Consider the rational miners problem: If the attack succeeds, honest miners get nothing. If the attack fails, honest miners get block reward.
                                                  If the attack succeeds then attack miners, get block reward + bribe. If the attack fails, then attack miners get block reward.
                                                  Therefore the dominant strategy is to attack. The probability of attack success is irrelevant.

Consider the attackers problem:       If the attack succeeds, then the attacker gets a stolen value of D - bribe.
                                                  If the attack fails, then the attacker loses n*block reward, where n is the number of confirmations on the initial spend.
                                                  Therefore, if p is the probability of attack success, you attack if  p(D-B) > (1-p)(block reward)n
                                                  Clearly, B has some positive influence on p, but it is hard to guess what. If all miners were atomistic and perfectly rational, then p is 1 for B>0, so you want to attack
                                                  whenever you buy anything of strictly positive value.

Notes: To mitigate this problem, it would help if ...

a) It was extremely difficult to make secret one-block long side chains. One block public forks are fine. If it were public, the double-spend in step 2 would set off alarm bells and prevent timely completion of step 3.
b) Miners were not rewarded with fees.

I think (a) is the larger problem, (b) is kind of a side issue. Even without fees, you could still offer ex-post rewards as was done in step (5). Fees just help you commit.

[kjj]

Don't forget that no one will ever trust the attacker again after he publishes the proof of his misdeeds for the entire world to see.  Also, no one should be accepting transactions on low confirmation counts unless they can afford to lose it.

[cunicula]

Don't forget that no one will ever trust the attacker again after he publishes the proof of his misdeeds for the entire world to see.  Also, no one should be accepting transactions on low confirmation counts unless they can afford to lose it.

The attacker and the miners are pseudonymous. Coins are fungible. He can wash the dirty coins, put them in a new unknown wallets, and attack again using a fresh identity.

[mskwik]

This seems to assume that miners are either working for one side or the other, it seems to me that if the "bribe" is less than the block generation amount the optimal mining strategy is to keep both chains going out as long as the attacker can afford and have the attack fail in the end.

[cunicula]

This seems to assume that miners are either working for one side or the other, it seems to me that if the "bribe" is less than the block generation amount the optimal mining strategy is to keep both chains going out as long as the attacker can afford and have the attack fail in the end.

The assumption is that mining is decentralized. Suppose you extend the main chain, then individually you get block reward if the attack fails, nothing otherwise. The attacker needs to distribute more bribes, but these are divided evenly (in expectation) across everyone mining the attack chain. It is not individually rational to extend the main chain in order to distribute handouts across all attack miners.

[kjj]

Don't forget that no one will ever trust the attacker again after he publishes the proof of his misdeeds for the entire world to see.  Also, no one should be accepting transactions on low confirmation counts unless they can afford to lose it.

The attacker and the miners are pseudonymous. Coins are fungible. He can wash the dirty coins, put them in a new unknown wallets, and attack again using a fresh identity.

In a transaction big enough that you can afford to bribe miners to reverse it?  Not likely.

[mskwik]

The assumption is that mining is decentralized.

And yet you have some centralized channel setup to announce your attack chain to miners?  Perhaps I'm misunderstanding it somewhere but doesn't the satoshi client not forward competing blocks until they become part of the longest chain?  I see how it mirrors game theory in that your individual reward might be highest helping the attacker, but the assumption there is that the players can't communicate with each other and I'm not sure that holds true in this case.

[cunicula]

The assumption is that mining is decentralized.

And yet you have some centralized channel setup to announce your attack chain to miners?  Perhaps I'm misunderstanding it somewhere but doesn't the satoshi client not forward competing blocks until they become part of the longest chain?  I see how it mirrors game theory in that your individual reward might be highest helping the attacker, but the assumption there is that the players can't communicate with each other and I'm not sure that holds true in this case.

Of course, I am assuming that people don't use the satoshi client to mine. Otherwise how can there be attackers? Instead they adopt some another client which is more flexible (allows communication with attackers), but which still produces valid blocks. You can think of the new client as League of Shadows P2Pool. They adopt this client because it works just as well for honest purposes, but also allows for extra earnings through illicit activity.

You mean the assumption is that the players can communicate with each other? (Otherwise how does the attacker announce his sidechain?) Yes, I'm assuming players can communicate freely and that the modified client allows them to do this. I think that is a pretty standard assumption. Assuming that no one can communicate at all except via the Satoshi client is bizarre.

How would communication across players possibly help them rationally fight the attacker?

[cunicula]

Don't forget that no one will ever trust the attacker again after he publishes the proof of his misdeeds for the entire world to see.  Also, no one should be accepting transactions on low confirmation counts unless they can afford to lose it.

The attacker and the miners are pseudonymous. Coins are fungible. He can wash the dirty coins, put them in a new unknown wallets, and attack again using a fresh identity.

In a transaction big enough that you can afford to bribe miners to reverse it?  Not likely.

I thought the point was that (if miners behave rationally and are atomistic), then any tx is big enough that you can afford to bribe miners to reverse it.

[FreeMoney]

I might be missing something but I don't see how this isn't just obvious. You can buy more mining power yourself or your could hire out.

[kjj]

Don't forget that no one will ever trust the attacker again after he publishes the proof of his misdeeds for the entire world to see.  Also, no one should be accepting transactions on low confirmation counts unless they can afford to lose it.

The attacker and the miners are pseudonymous. Coins are fungible. He can wash the dirty coins, put them in a new unknown wallets, and attack again using a fresh identity.

In a transaction big enough that you can afford to bribe miners to reverse it?  Not likely.

I thought the point was that (if miners behave rationally and are atomistic), then any tx is big enough that you can afford to bribe miners to reverse it.

Well, you are wrong about that.  If that is the conclusion you've come to, then you aren't tracking the costs and rewards properly along with the probabilities of success for all of the parties.  It gets worse when you add in reputation costs, but even ignoring those, it still doesn't work.

[cunicula]

Well, you are wrong about that.  If that is the conclusion you've come to, then you aren't tracking the costs and rewards properly along with the probabilities of success for all of the parties.  It gets worse when you add in reputation costs, but even ignoring those, it still doesn't work.

You fail in reading comprehension, perhaps intentionally. I said "if" indicating an assumption, not a conclusion. You are assuming that reputation is strictly a positive force, which is not necessarily the case.

If GPUmax has a reputation for paying a premium on shares and miners are greedy, then reputation can make things worse. I think this is freemoney's point that this whole scenario is obvious. He is thinking of a centralized double-spending business, rather than a decentralized mechanism of attack. If the business pays more for shares and maintains a reputation for doing so, it should get 51% of the hash power.

I am thinking of decentralized double-spending p2p software that any attacker can use. The nice thing about the decentralized mechanism is that it allows attacker to be anonymous. This might be preferred if attackers face real world retribution.

It might be difficult to make GPUmax an anonymous hidden service (not sure though).

Finally, perhaps you are referring to the costs of failed attack which sucks for the attacker. You can solve this by making the bribes really big and not insuring the miners against failure at all. Then you only pay out for a successful attack. Problem is that attack is no longer a dominant strategy for miners. Whether you attack or not depends on your prior beliefs about attack success. This problem is considerably more complicated because you have to specify how beliefs are formed. In general, there will be multiple equilibria and these will depend on miners prior beliefs.

[Mike Hearn]

Yes, this issue (and variants) have been discussed before.

This type of analysis has a few problems. The first is that it redefines the word "rational" to mean "short term thinker", which is not the same thing. Life is full of examples where you can make a quick buck in the short term but destroy your income over the long term, and somehow civilization still makes progress. A rational miner would not simply double-spend any transaction with high enough fees, because that would result in a short term profit at the cost of destroying confidence and thus usage of Bitcoin over the long run.

That possibility is explicitly addressed in Satoshis paper:

He ought to find it more profitable to play by the rules .... than to undermine the system and the validity of his own wealth.

The actual quote is discussing the case of trying to individually obtain enough mining power to outrun the chain and double spend, but buying hash power to do so is not much different.

So the only way this scenario can occur is if all miners end up being exclusively short term and being willing to sacrifice Bitcoin to get a few double-spend fees that they then immediately cash out. But many miners are in it for the long term, either for ideological reasons, or because they have large sunk costs in Bitcoin-specific hardware, or both. Killing confidence in the system is not in their interests.

The other problem is that it's not true that purchasers are always anonymous. Today that may often be true, but that's because Bitcoin is primarily used for relatively small and unimportant purchases. Nothing says merchants have to deal with anonymous customers, and if double spends become common merchants will just start requiring ID in order to sell you things, with some kind of distributed reputation system over those IDs. Eg, the Bitcoin Foundation does not sell membership to anonymous people.

Incidentally, I think eventually double spends will happen semi-regularly and anonymous purchases will become less common for that reason, but I think it'll happen for different reasons to what you think (ie not a conspiracy of short term miners).

[cunicula]

Yes, this issue (and variants) have been discussed before.

This type of analysis has a few problems. The first is that it redefines the word "rational" to mean "short term thinker",

In the OP I used "rational". In a reply, I clarified to write "rational" and "atomistic". "Rational", "atomistic" miners are of course "short term thinkers" by definition.
I invite you to point out any problems you see with the analysis in this case. I don't see any at all.

Incidentally, I think eventually double spends will happen semi-regularly and anonymous purchases will become less common for that reason, but I think it'll happen for different reasons to what you think (ie not a conspiracy of short term miners).

There is no conspiracy involved here. All of the miners are individually rational. They are not colluding in any way. There is a single attacker who mined one block and then leverages this to execute an attack in full public view.

You are being presumptuous. This post does not refer to what I think will happen. I think that PoW mining (if it survives at all) will become a completely centralized monopoly. The attack scenario is no longer relevant in this case, but this type of attack provides one important reason to expect the PoW monopoly to emerge or alternatively PoW to be supplanted by a more robust design. I'm not sure whether the monopoly will allow treat bitcoin like cash or credit cards (regular double spends). That will be up to the monopoly operator.

Could you explain why you think there will be regular double spends in the future?

[becoin]

That possibility is explicitly addressed in Satoshis paper:

He ought to find it more profitable to play by the rules .... than to undermine the system and the validity of his own wealth.

It is always amusing to see how rational people believe that all people are rational. I have to disappoint all believers in the rationality of homo sapiens. I agree that long term a human or organization of any kind has to be rational to survive, but the world is full of short term madness.

Even institutionalized madness is on the rise recently. For instance, the president of ECB Mario Draghi is such an example. When discussing the future of euro he said they will protect euro "whatever it takes"... Can you imagine what this can really take? Can you imagine what will it take if EUR, USD, YEN, GBP, CHF, etcetera all together need to be saved?

If you want to really protect a system you have to protect it against irrational behavior as well.

[Mike Hearn]

I'm not sure what "atomistic" means, are you sure that's the word you wanted? The definition is apparently "divided into separate and often disparate elements."

There is a conspiracy because the behavior you are suggesting all miners will adopt is not the behavior of the standard software, somebody would have to write the necessary patches and then others would have to switch their regular software to the modified version. That's a "conspiracy" in the sense that it only makes sense to do so if others do it too, hence they must collude. That collusion would certainly be detected, and the fact that Bitcoin was about to get less reliable would cause selloffs that depress the exchange rate, and perhaps closure of some merchants. Certainly any miner who had any investment in Bitcoin would see the value of that investment shrivel up long before users learned about the new "status quo" and began regularly trying to use complicated bribe schemes.

This is the problem with game theory. It reduces complicated situations and actors with many competing agendas down to simple automatons.

A much bigger problem is simply people who are paid directly to mine, via sites like HashPower or GPUMAX, and who don't care what they mine on. It simplifies mounting some kinds of attack but the general economics still hold.

[cunicula]

I'm not sure what "atomistic" means, are you sure that's the word you wanted? The definition is apparently "divided into separate and often disparate elements."

There is a conspiracy because the behavior you are suggesting all miners will adopt is not the behavior of the standard software, somebody would have to write the necessary patches and then others would have to switch their regular software to the modified version. That's a "conspiracy" in the sense that it only makes sense to do so if others do it too, hence they must collude. That collusion would certainly be detected, and the fact that Bitcoin was about to get less reliable would cause selloffs that depress the exchange rate, and perhaps closure of some merchants. Certainly any miner who had any investment in Bitcoin would see the value of that investment shrivel up long before users learned about the new "status quo" and began regularly trying to use complicated bribe schemes.

This is the problem with game theory. It reduces complicated situations and actors with many competing agendas down to simple automatons.

A much bigger problem is simply people who are paid directly to mine, via sites like HashPower or GPUMAX, and who don't care what they mine on. It simplifies mounting some kinds of attack but the general economics still hold.

You are right. Downloading special software or mining at a special pool like GPUMAX is a form of conspiracy. There is an important distinction between GPUmax and special software. GPUmax is easier to set up. Special software could duplicate the function of GPUmax. Because the software could be P2P and could behave just like bitcoind under non-attack circumstances, it would be more difficult to detect and destroy. It would also be more difficult to gauge the threat posed by such software. Moreover, the software would help the attacker remain pseudonymous. This is possible with GPUmax, but probably more difficult.

In game theory, "Atomistic" refers to the assumption that individual choices have no impact on aggregate variables, i.e. individuals are tiny and numerous like atoms; aggregate variables emerge through integration over infinite numbers of tiny atoms. It is a simplifying assumption for analyzing games with large numbers of players. Here it just means that individual decisions have no effect on whether the attack succeeds. The hashing power of any one decision maker is simply too small to make a difference. Therefore, individual decision makers ignore the effect of their decisions on attack success probability. This makes it irrelevant whether they have investments in bitcoin or not.

Sorry for being a little pissy.

I agree that game theory doesn't predict behavior very well. But there isn't a good alternative to game theory besides experimentation.

Anyways, the most interesting question is why you think there will be semi-regular double spends in the future. Why?

[Mike Hearn]

What speed is the right speed for the Bitcoin network?

  http://bitcoin.sipa.be/speed-lin-ever.png

The simplest answer of course is "as high as possible", but that's not a good answer because we can always divert more and more wealth into hashing. The right answer  is "as much as necessary but no more". Doing more work than necessary just wastes energy and the money needed to pay for it.

So how much is necesssary? Well, it's impossible to know today because merchants don't seem to be complaining about double spends. At least if this is a regular problem I've not seen any discussion of it. So it's safe to say that our current speeds are better than necessary. We can only really find out the speed that is necessary by letting the speed fall until people start complaining. As inflation dries up and we catch up with the best possible technologies for hashingn, speeds will eventually fall until double spends start happening with some degree of regularity. At that point the community will find some way to fund the network (insurance, assurance contracts, attaching fees to important transactions, whatever).
 
This opens the question of what the right speed is, given that people have differing tolerances for risk. Some people have claimed this is a fundamental weakness of Bitcoin and that funding network security post inflation will result in a race to the bottom that destroys the system, but I don't think so. I suspect Bitcoin will stabilize at some kind of group consensus on something that's "good enough". Users with extreme needs will have to wait, combine Bitcoin with security enhancing technologies like trusted computing / smart cards, use insurance, rely on reputation and risk analysis.

[cunicula]

Some people have claimed this is a fundamental weakness of Bitcoin and that funding network security post inflation will result in a race to the bottom that destroys the system

Right, I am the undisputed number one proponent of this argument. If you look at my post history you will see that about 50% of my posts are related to me screaming "bitcoin will fail because of a race to the bottom." That is how I got so many ignores.

If you are worried about this, why not try to solve the root problem? There are a number of promising approaches (e.g. requiring randomly selected sequence of private keys to sign hash(block,txns in block) before the block enters the chain.) Admittedly a hard fork is absolutely required for any solution. You don't have to create inflation or stop giving block reward to PoW miners. I don't think they can keep 100% of the txn fees though.

[Mike Hearn]

I'd rather wait until it becomes a problem. I disagree we need any hard forks. There are plenty of proposals that don't need that.