Topic: Bribery: The Double Double Spend (Read 5550 times)

I was asked to copy the following post by DeanBrettle from the newbie area:

https://bitcointalksearch.org/topic/m.2526828

Probably best to continue the discussion on that thread if you want to respond.

----

This is my contribution to the November 2012 discussion of the potential for a Double Double Spend attack on bitcoin. Since it is an old thread, I'll start by trying to recap the existing discussion.


As described in cunicula's original post, the attacker secretly mines a side chain block containing a double spend and then, after the victim has received enough confirmations to accept the original spend, the attacker bribes miners to mine on his side chain. Every time a side-chain block is mined the attacker pays the miner, on the main chain, an amount equal to the block reward, and also pays some small amount to the miner on the side chain in addition to the block reward that the miner automatically receives for mining a block. By paying the rewards on the main chain and the bribes on the side chain from a separate double spend, the attacker only pays the rewards if the attack fails. However, if miners are purely profit-driven the attack should succeed because mining the side chain is just as profitable as mining the main chain if the attack fails and it is more profitable if the attack succeeds.

mskwik pointed out that the satoshi client doesn't propagate blocks that aren't on the longest chain so the attacking miners would need to be running a client that allowed them to share the side chain while they were attacking. cunicula agreed but didn't think it was safe to assume that miners would refuse to run a more profitable client.

Mike Hearn said that miners wouldn't take part in such an attack because the attack would destroy confidence in bitcoin, which is something they have a lot invested in either financially or ideologically. He also said that if double spends become too common, merchants would require identification and a reputation system would emerge to prevent them.

cunicula's preferred fix is requiring blocks to be signed by a sequence of randomly selected private keys. If signers refused to sign blocks containing double spends, then double spends could not occur.

The rest of the thread is a discussion of the separate issue of what will happen to bitcoin as the block reward drops to zero and what, if anything, should be done about it. While I think that is an important issue, I want to focus on the attack that cunicula proposed in his original post.


Since I didn't find Mike Hearn's response particularly reassuring, I went looking for other reasons that the attack might not be as easy as cunicula's explanation makes it seem. I think I've found two things missing from cunicula's analysis.

First, the victim is a player as well, and has at least one potential counter-strategy. Once he sees the side-chain, he can bribe the miners to mine blocks on the main chain instead of the side-chain. He can even play the same type of strategy as the attacker, paying the block reward on the side-chain for blocks mined on the main chain, and paying a bribe on the main chain.

Second, any pool operator or solo miner in possession of a locked post-fork main chain block reward will lose that reward if the attack succeeds. These entities are collateral damage from the perspective of the attacker, but they have a financial interest in stopping the attack, perhaps even stronger than the victim of the double spend. They are players as well and can use the same counter strategy as the victim. Let's call these players plus the victim collectively defenders.

With these two additions, the dominant strategy for rational miners then becomes mining for whichever side (the attacker or the defenders) offers the largest bribe.

This leaves the attacker in a war of attrition game with the defenders. The first thing to note is that depending on how the defenders play this game, the attacker might lose or might need to pay more than the value of the double spend in order to win. This means that attacking is *not* a dominant strategy as cunicula suggested. Moreover, my understandating is that the symmetric Nash equilibrium for such a war of attrition game involves both sides paying the miners at least the amount that the losing side has at stake. As a result, even if the attacker managed to win the war of attrition using a Nash equilibrium strategy, the expected cost would make the attack unprofitable, so the attacker would still not attack to begin with.

Comments?

I don't want to argue with you about definitions. Public good is a loosely defined term. The key characteristics as you note are "non-excludable" and "non-rivalrous", but most "public goods" do not completely fit this description. You might find these lecture notes on public goods helpful:
http://are.berkeley.edu/courses/EEP101/spring05/Chapter07.pdf

You can certainly make broadcasting TCP transactions excludable (for example by imposing a minimum fee to get them accepted in blocks). Pools can do this by forming a 51% cartel and rejecting all blocks include free or cheap transactions. Alternatively a monopoly 51% pool can form. The problem is that these solutions look very much like Paypal/Visa/MC and I once hoped that bitcoin developers had higher aspirations.


Let's examine a few problems with assurance contracts.

1) Basic Assurance Contract

Say you write some shareware that needs to a server to run. You can solicit $1 donations to support the server and say that if I get 100 of these, then I will run the server, if not then I will return the donations.
You are arguing that committing to return the donations if you get less than 100 serves as some kind of magic bullet. I think this is ridiculous.

Say that I value the service at v>1. Let x(1)>0 be the probability that the service operates if I contribute and x(0)>0 , x(0)x(0)v. Rearranging you get that I contribute if v>(x(1)/[x(1)-x(0)]).

Note that as x(1) approaches x(0), the valuation necessary to motivate my contribution becomes infinite. The distance between x(1) and x(0) decreases as the number of contributors increases. If you solicit small contributions from a large number of people x(1) will be very close to x(0), so no one will contribute. Even if you ask them for a very small amount.

The only approach that could work is soliciting very large contributions from a small number of big corporate donors. Then you potentially have x(1)>>x(0). I'm not sure if CorporateCoin is what everyone had in mind.

2) Dominant Assurance Contract [I have never seen an example of a contract like this in actual use, anywhere. It is easy to set up. Curious that this supposedly 'promising' concept has not been adopted by any of the assurance contract operations]

In the dominant assurance contract, there is an entrepreneur who insures the assurance contract against failure.  Perversely, after they have submitted funding, the contributors may now hope the project fails. One reason we may not see this on kickstarter is that it is an advertising platform (the contributors are supposed to aid the project, not try to hamstring it.)

Okay, back to the contract. The entrepreneur promises to refund the original contribution + a penalty, y>0, if the funding goals aren't met.

Therefore the previous problem becomes,

I contribute if x(1)(v-1)+(1-x(1))y>x(0)v. Now we contribute if v>[X-y(1-X)]/[x(1)-x(0)].
This is good because we can increase the probability of funding if the goals aren't met by offering a bonus y. If the bonus is large enough, then you will always contribute here. But the bonus is not a free lunch. The entrepreneur is taking risk here. He loses money if the fundraising fails y*n, where n is the # of contributors. Thus he needs to skim some profit off the donations.

This raises a number of concerns for me:
1) Ex-post the contributors may want the project to fail and could potentially benefit from sabotaging it. This is not a good structure for a collaborative project.
2) The arrangement requires the 'entrepreneur' to skim rents off of everyone else's donations. Compare this to say a minimum fee. With a minimum fee you get $1 of hashing power for every $1 collected with this arrangement you only get whatever is left over after the 'entrepreneur' takes his cut. Thus even if the contract works well, it will still be inferior to simply imposing a minimum fee.
3) The arrangement might be vulnerable to sabotage. Suppose that 'entrepreneur 1' offers a dominant assurance contract with a payoff y. I then contribute heavily to his contract, but not enough to put it over say 50% prob of success. Now I release my own dominant assurance contract with a payoff 2y. The new contract might persuade people to switch from his contract to mine. If my contract succeeds and his fails, then I scam entrepreneur 1 for a big profit. But wait... If I could scam the entrepreneur why doesn't another entrepreneur come along and try to scam me? Maybe I should never offer a contract in the first place? The existing literature, basically just one paper by an economist (http://www.iso.gmu.edu/~atabarro/PrivateProvision.pdf), does not consider this issue at all.

[The sabotage issue is complex and would require a lot more work than I am willing to put in to analyze. It alarms me that the existing literature hasn't even considered this.]

No, that statement just isn't correct. The definition of a public good is one in which exclusion isn't possible. The very first sentence of the Wikipedia page for public good says this:


I think this disagreement over definitions may be the root of our argument. Network security is clearly a public good, anyone can use it just by bringing up a TCP connection and broadcasting some transactions. Assurance contracts are well studied way to provide such goods, albiet one that hasn't been used much until recently - but things like Kickstarter are showing the way. You haven't provided any convincing arguments as to why this won't work.

Chris, the point of this thread are that the developers have thought of lots of counter strategies, network assurance contracts are just one. cunicula rejects all of these, but that doesn't mean he's right.

Yes, but most cases where you see private arrangements to provide public goods working, there is some way of excluding outsiders from use of the public good. Thus the set of potential free-riders is limited. This is one of Elinor Ostrom's points. She argues that private arrangements work well for example in small communities. (e.g. where the public good is a grazing field, you let everyone in your community bring their animals to graze on the field. If you see some outsiders grazing on the field, then you send thugs to take them out.)

I don't think there is a counter strategy in bitcoin. As you can see, the developers are opposed to modifications of the core protocol. There are counter strategies in alternate chains. One counter strategy is to require all blocks to be signed by a sequence of n randomly selected private keys before they enter the blockchain. You can't acquire these signatures without announcing your block (destroying secrecy). This makes secret double-spending almost impossible.

Without a secret block, the attacker cannot issue enforceable bribes. He could still bribe people to extend his chain, but bribes wold have to be paid after signers extend the attack chain. The signers would have to trust the attacker to make good on bribe promises.

I am curious to know if anyone has thought of alternate counter strategies.

It seems to me that cunicula has identified a really interesting vulnerability! I would be very interested to know if there is a counter-strategy or not.

Yeah, it is an extreme example.

I don't think the problem is that global warming is not interesting to potential participants. Plenty of people are concerned, aware, and pay attention. Otherwise it could not be a political issue.

It is more of 1) scaling 2) time constraints (the desired outcome spans a long time, but the contract cannot easily incorporate participants from the future) 3) Inability to sanction people who don't participate (for example by excluding them from use of the shared good).

I think all of these problems are pertinent to bitcoin.

That example seems rather extreme. If something hasn't solved global warming, it's a failure? Pretty much everything fails that test.

Anyway, the problem with it is the outcome is not interesting to potential participants. The number of participants is limited by geography, awareness, scarcity of attention, funds, etc. Even with a huge scheme it's very likely the outcome would make no difference to most peoples lives.

So I agree that assurance contracts can't solve that. It's really up to scientists to save us from that. The existence of creative works funded by assurance contracts is a better example of how they can succeed.

An example of a likely failed assurance contract (my judgement yours may differ) is the following ad:  "Double Your Difference Offset Matching program, individuals can purchase carbon offsets to reduce their carbon footprint beyond what is typically possible with efficiency. When you purchase an offset, Entergy will double the impact of your purchase by matching up to five tons of carbon offsets purchased per individual."

This is an assurance contract for a public good. I don't see global warming as solvable via voluntary private sector arrangements.

 
Maybe someday bitcoin's monthly operation will be paid for by raising funds on kickstarter (that is a famous provider of assurance contracts). I wouldn't hold my breath.
 

I find an argument that starts with "I cannot show you an example of failure because failure is so obvious it's never happened" to be unpersuasive, especially because failure is not obvious - if you have to make complicated arguments based on game theory then almost by definition the failure isn't obvious. Humanity seems to have infinite capacity for trying bad ideas, I'm sure if you look you can find at least one comparable example.

The point of assurance contracts is to ensure that public goods are provisioned by ensuring the cost doesn't fall exclusively on the person who benefits the most, it's a solution to the problem of "the user who benefits the most from system contributes 100% of the effort to maintaining system reliability. Every single other user contributes zero."

We understand that you prefer alternative designs. At some point I'm not sure it's worth debating in more detail any more. Bitcoin isn't going to become a proof of stake system, the only way for you to really win this argument in the eyes of the world is to build a competitor that works better. If I'm right and at some point double spends do become an issue, then your competitor may look more attractive if it doesn't have that problem. Chain-trade scripts can be used to atomically swap Bitcoins for Cunicoins, perhaps on a fully automated p2p exchange, so the transition would not be too disruptive.

This is very difficult. Assurance contracts comparable to bitcoin are not observed because the idea is obviously unworkable. In most cases, failure would be anticipated and the experiment would never be tried.

Are you familiar with the noncooperative game theory on these issues (just the basic issue not assurance contracts)?

The most directly relevant paper is "System Reliability and Free Riding" by Hal Varian (Chief Economist at Google)
http://ns2.datacontact.dc.hu/~mfelegyhazi/courses/BMEVIHIAV15/readings/05_Varian2004system-reliability-free-riding.pdf

Abstract:
System reliability often depends on the effort of many individuals, making reli-
ability a public good. It is well-known that purely voluntary provision of public
goods may result in a free rider problem: individuals may tend to shirk, resulting
in an inffecient level of the public good. How much effort each individual exerts will depend on his own benefits
and costs, the efforts exerted by the other individuals, and the technology that
relates individual effort to outcomes. In the context of system reliability, we
can distinguish three prototypical cases.

The relevant prototypical case for bitcoin is the "sum of effort case." In this case, reliability is determined by the sum of efforts of all users. The nash equilibrium is that the user who benefits the most from system contributes 100% of the effort to maintaining system reliability. Every single other user contributes zero. This is also true if there is an attacker trying to destroy the network. The attacker wins if he benefits more from destroying the network than the highest valuation user benefits from saving it. The total value of the network is irrelevant. The highest valuation user determines aggregate network security.

I will think about the economics of organizing an assurance contract. I'm pretty sure that the contract's viability will depend on the distribution of user valuations. The more equal these are, the more effective the assurance contract would be. I will think more about it. However, let me reiterate that even if an assurance contract is viable in some cases it will remain a grossly inferior substitute to a securely designed system.

Alright, I'll check out her work. I'm not sure any previous situation is comparable to Bitcoin, so we'll have to wait and see how well it works in practice.


"Impossible to sanction free riders" is pretty much the definition of a public good. The point is you don't need to sanction them. The good gets created anyway by the people who care enough about it that they want it for themselves.


You first - provide an example comparable to Bitcoin where it didn't.

I can't see that subsidizing ASICs is going to run enough miners out of business.  Many don't, and never did, need to be profitable in any practical sense.  Many of the early full time miners were just disiplacing the electric resistive heating for their flat with as much mining heat as they could manage; simply displacing one electric heat source for another, with the potential of gaining bitcoins in the process.  Even if pool miners could be run out of business (something that I question for reasons beyond the above situation) the long term reduction of difficulty simply makes mining more attractive for those who can still justify it.

Again, there are easier was to do that, and cheaper too.  That's why I say it is uninteresting, and why I had assumed that we were talking about something entirely different.

Exactly, kjj. This is not only the critical part but the final part because this will be the end of bitcoin. Attackers achieve their goal - bitcoin is crashed and current monetary monopoly stays intact!

No, I meant exactly what I said, "no one else".  Would you use bitcoin if, for example, the Federal Reserve Bank was the only miner?

By everyone and no one you probably mean everyone and no one among miners?!

Not explained at all, merely stated.  Adding subsidized ASICs to the mix will increase difficulty, at least until the point that everyone stops using the system entirely, at which point the only person left mining is the subsidizer, and he can set the difficulty to whatever low value he wants, but, and this part is critical, but no one cares because no one else is using it.

As for opencores, go for it.  I'm totally in favor of more designs and cheaper chips.  Considering that we are (probably, heh) going to go from zero publicly available ASIC designs to at least three in the next 12 months, I wouldn't say that open hardware is critical here, but it is always desired and appreciated.

Already explained on my previous post. You kill competition among miners through subsidized ASIC and you have what you want.

Bitcoin community is too much focuced on open source software but open source hardware is equally important for the bitcoin network. What about donating to a bitcoin specific ASIC project on OpenCores.org?

Yawn.  If you want to destroy bitcoin, it would be cheaper to round up all of the miners and shoot them.  If you want to reduce the difficulty, but still keep a functioning system, what are your options?

My apologies, I had taken the total destruction option to be an assumed, but uninteresting, path.