Mining cartel attack

[RHorning]

I came across an idea that I think is worth discussing in regards to a kind of "attack" on the bitcoin network.  I'm calling this a "mining cartel attack".  I have no idea if this is being done right now, and I'm being pre-emptive in terms of describing it as I'm sure the thought has come across the minds of some other people too.  Perhaps I'm missing an essential element of Bitcoin here, but I think this could be a serious issue and I'm not sure of what protections, if any, are in place to stop this.

The assumption right now is that anybody can create a new block through the block generation system in place on Bitcoin and simply throw CPU cycles that eventually will be recognized in one form or another.  So far that is true and in fact I've been able to create a block doing just that as have many on this forum and elsewhere.  I consider that at least for the moment "proof" this attack isn't happening right now, at least for myself.  As long as everybody is being mostly honest and understanding that the strength of the network thrives by having as strong of a block chain as possible, this will continue to be the case.

Instead, in a "mining cartel attack", I'm proposing that a substantial number of "miners" who possess a substantial fraction of the computing power of the network, but not necessarily 50% of the network, could form into a cartel that would only recognize blocks generated by each other.  Perhaps they would let a few other blocks get past them from time to time to hide this attack, but the vast majority of the new blocks recognized by this cartel would have to be produced by cartel members.  BTW, the "letting a few other blocks past" also reduces the percentage of the network needed by this cartel to pull off this attack as those other blocks are actually contributing to the overall strength by including "independent miners".

Bitcoin works by recognizing the longest block chain in terms of proof of work.  Since this cartel is mostly rejecting blocks from other nodes yet they have some substantial computing power under their control, they can create longer chains as a group than the rest of network, especially if the rest of the network is disorganized and consists of mostly small-time "independent miners" not in a cartel.  It doesn't take much here, even if only on occasion they are rejecting a few blocks from non-members of the cartel.  This in turn, from an economic viewpoint, is going to strengthen the cartel members by "winning" more blocks and thus block generation coins and transaction fees associated with those chains more dominated by the cartel.

The programming for such an attack would be quite tricky, especially if you are trying not to get caught quickly that this kind of manipulation is happening.  It is something that could "scale" with the proportion of the network controlled by this cartel as the closer they get to 50% control of the CPU resources of the network also regulates how many "non cartel" blocks can be rejected in favor of cartel members.  I'd have to do some simulations to see what percentage of the network would be needed to reject any blocks from other miners as I don't think a single PC could do this attack at all.

Presuming in an ideal situation where the mining cartel persists with this attack, on a social level many of the non-cartel members would drop out of mining (it is already happening anyway) as they simply can't get their blocks recognized and think the effort of running the CPU isn't worth the effort.  Cartel members would be claiming that the issue is mainly because of increased mining difficulty (which may be true as well) but it should be noted that isn't the only issue here.  Still, the net effect is that the mining cartel ends up with an increasingly larger portion of the network and thus firmer control over the ability to manipulate the network to their own advantage.

Multiple cartels could also exist in this framework, with or without the knowledge of each other.  There would be strong incentives to try and identify other cartels and certainly to propose a "merger" of competing cartels if possible under all sort of arrangements.

The primary issue on a technical level would be to identify which blocks belong to cartel members and thus should be used for building the next block of the chain by cartel members.  This would likely be done "out of bandwidth" as a separate communication channel independent of the main Bitcoin communications network, although an "in bandwidth" scheme could also be set up.

The net harm to Bitcoin as a whole is that the block chain would ultimately be weaker as a result of this kind of attack, since CPU cycles "spent" by "independent miners" would not be recognized or used for difficulty adjustments on the network.  This is also something that a government could use to "capture" Bitcoin if they were patient and were willing to work outside of legal attacks.  Still, I see this mostly being done by self-interested participants who already have some substantial CPU resources and are simply being greedy.  Transactions themselves would not be harmed and those with Bitcoins already in some form or another can arguably even be supported by such an "attack" as the miners are doing some of the "dirty work" involved with running the network... something cartel members would assert anyway as a sort of "public service".

Is this something to even worry about?  I don't see an "easy" way to stop this sort of "attack" either, although there certainly are plenty of historical examples of similar kinds of "conspiracies" to restrain activity like this.  Just look at DeBeers in South Africa if you need some examples to look at.

[btchris]

Here's how I'm interpreting your attack, can you let me know if I got it right?

The mining cartel could follow this rule: If the most recently generated block was generated by the cartel, mine normally. Otherwise, fork the chain, ignoring the most recent block, and begin mining from the previous block instead.

So if the most recent block, say #100, wasn't generated by the cartel, we have:

"Main" chain	"Cartel" chain
Block #1	Block #1
...	...
Block #99	Block #99
Block #100	Current work block
Current work block

In order to make Block #100 "disappear" from the Main chain, the Cartel must

• Generate 2 blocks before Main network can generate 1, or
• Generate 3 blocks before Main network can generate 2, or
• Generate 4 blocks before Main network can generate 3, or
• ...

This is the only way the Cartel could create a chain longer than the Main chain and therefore "override" the Main chain, and would seem to require > 50% of the total network's CPU power to consistently succeed.

However, you're suggesting: what if the goal weren't to consistently succeed, but rather only to occasionally succeed?

Occasionally a Cartel with a sufficiently high percentage of CPU power (but still less than 50%) would succeed in this by chance. So the questions in my mind are:

• Given some percentage control of CPU power, what percent of blocks could a Cartel make disappear? Or alternatively, at what percentage control of CPU power would this attack become feasible?
• What incentive would such a Cartel have (you've already gone into this)?
• What negative affects could this have on legitimate users (again, you've talked about this already)?

By using such a method, the Cartel would not be able to generate more coin for itself (from an absolute point of view). However you point out that since it is disappearing other miners' coin, it would end up with a higher percentage of the total coin generated by the network.

However, some of the time (most of the time I think?) that the Cartel forks the chain, it will not be able to catch up to the Main chain. After a certain amount of time spent trying to catch up to the Main chain, the Main chain would be so far ahead that the Cartel must choose to give up, and return to step one (start a new fork). When it does this, all the CPU it's spent trying to catch up, and all of the BTC mined in the process, would be lost. So the last question I have is:

• Do the gains of (potentially) creating a greater % of the total BTC outweigh the losses incurred when the Cartel has to give up and start over?

Having not done (and probably being incapable of doing) any real math analysis here, I'm going to go out on a limb and say I don't think the gains are worth the losses....

Or I very well could be missing something here?

-Chris

[davout]

Yea, you're basically rediscovering a known vulnerability, that anyone having over 50% of the computing power controls the network and gets to create all the blocks.

If you have less than 50% it statistically just doesn't work (meaning its more profitable to be a honest node)

Also, by doing that you'll quickly be discovered and therefore undermine the value of your own wealth.

Even if a government was attacking bitcoin using such means, the rogue nodes could get identified by using a couple of simple heuristics and get ostracized by the rest of the network.

[davout]

Yea, you're basically rediscovering a known vulnerability, that anyone having over 50% of the computing power controls the network and gets to create all the blocks.

If you have less than 50% it statistically just doesn't work (meaning its more profitable to be a honest node)

Also, by doing that you'll quickly be discovered and therefore undermine the value of your own wealth.

Even if a government was attacking bitcoin using such means, the rogue nodes could get identified by using a couple of simple heuristics and get ostracized by the rest of the network.

You would have to have at least 50% for this type of attack to work. Otherwise, you may be able to steal a few blocks here and there by making a chain longer, but the wasted time on those forks would be worth less if they would have just mined honestly.

If you are over the 50% tipping point however, especially well over it, you very well could take control of all generation with some creative programming.

Besides being able to take over the generation, you could also not accept transactions without fees. Everyone that wanted to send coins, you could require a minimum threshold, making mining potentially even more profitable... definitely cartel style. 

Yes, that's basically what I'm saying, this vulnerability is "by design" 

[Anonymous]

Can anyone figure out what the total computing power of the bitcoin botnet is?

[da2ce7]

A computer system that could produce 100GHash/sec (what is required to attack the network) would involve having 200 ATI 5970 @ $500 + (200 computer) each, that is $140,000 dollars required to control the network... still not prohibitory expensive.

Lets try and not get attacked until attacking the network costs at least 50% of the economy. ~ $500,000 or ~ 350GHash/sec

[mpkomara]

Milestones--

-Folding@Home is, as of April 2010, sustaining over 6.2 PFLOPS
-The entire BOINC network averages about 5.1 PFLOPS as of April 21, 2010.
-As of April 2010, MilkyWay@Home computes at over 1.6 PFLOPS, with a large amount of this work coming from GPUs.
-As of April 2010, SETI@Home, which began in 1999, computes data averages more than 730 TFLOPS.
-As of April 2010, Einstein@Home is crunching more than 210 TFLOPS.
-As of April 2010, GIMPS, which began in 1996, is sustaining 44 TFLOPS.

From http://en.wikipedia.org/wiki/FLOPS.

[mtgox]

What happens when two people both transmit a different valid next block? How does the network determine which chain to keep growing?

[theymos]

What happens when two people both transmit a different valid next block? How does the network determine which chain to keep growing?

You build onto whichever one you saw first.

[RHorning]

What happens when two people both transmit a different valid next block? How does the network determine which chain to keep growing?

It is strictly based upon whatever block is picked by a particular miner, if all things are equal.  The chain splits in that case at least temporarily until the next block is found, deciding who "wins" the contest.  This can play out repeatedly where two or more "chains" can keep getting additional blocks simultaneously (more or less) and competing chains keep getting longer.  Probability will end up weeding one or the other out as one chain finally gets blocks when the other doesn't.  In theory what happens is that the block with more than 50% of the network CPU power will likely get the next block.

[appamatto]

Instead, in a "mining cartel attack", I'm proposing that a substantial number of "miners" who possess a substantial fraction of the computing power of the network, but not necessarily 50% of the network, could form into a cartel that would only recognize blocks generated by each other.  Perhaps they would let a few other blocks get past them from time to time to hide this attack, but the vast majority of the new blocks recognized by this cartel would have to be produced by cartel members.  BTW, the "letting a few other blocks past" also reduces the percentage of the network needed by this cartel to pull off this attack as those other blocks are actually contributing to the overall strength by including "independent miners".

This is interesting.  So the cartel miners could effectively possess more than 50% CPU by "allying" with some normal miners.

I think the problem is this:

Let's say the cartel has 1/3 CPU, and decides to allow 1/2 of all non-cartel blocks through.  Thus, the cartel network would consist of 2/3 CPU.  What figure should this be compared with to see if the cartel will win?

I think the answer is 100%, because the system as a whole allows both cartel blocks and non-cartel blocks.  100% CPU power for the system, 2/3 CPU for the cartel.  What's worse, the cartel's behavior will net it much fewer than the 1/3 of the blocks that it was entitled to because sometimes it will be operating on an incorrect block chain.

The cartel is trying to "ally" with some non-cartel blocks.  Amusingly, it is actually the network as a whole that reverse co-opts the cartel by accepting cartel blocks without prejudice.

[mtgox]

So depending how the network routing works it might be vulnerable to this attack when the cartel has < 50% of the network.
It could maybe work something like this:
Cartel maintains as many connections to other nodes as it can.
When the cartel finds a block it only tells the other cartel members.
When a non-cartel block is found, the cartel publishes the previously found block.
Since the cartel has many connections chances are > 50% of the network will accept the cartel block over the non-cartel block and thus the cartel block would become part of the main chain.
repeat

The cartel's advantage would be that the rest of the network would essentially be doing nothing during the time the cartel found a block till the time someone else finds a block. So the cartel would get a much larger % of blocks than it should.

So you don't have to have anywhere near 50% of the processing power. You just have to be faster to get your saved block on the chain.

[twobitcoins]

What happens when two people both transmit a different valid next block? How does the network determine which chain to keep growing?

You build onto whichever one you saw first.

Is that really true?  I thought the "longest chain" was now defined in terms of the difficulties of the specific hash values in the chain, so I would expect that once a client has seen both blocks, it will build on whichever has the smaller hash value.  Is it not working that way?  Of course until you see the second block, you build on the first one, and it may take some time to switch.

[FreeMoney]

"longest chain" does mean highest total difficulty, but the target is used not the actual hash.

[btchris]

... $140,000 dollars required to control the network... still not prohibitory expensive.

Lets try and not get attacked until attacking the network costs at least 50% of the economy. ~ $500,000 or ~ 350GHash/sec

Although this sounds disturbing, keep in mind that "controlling" the network doesn't mean you can steal BTC from people. It does mean you can probably prevent others from generating blocks, probably block any particular transaction from going through, and probably double-spend BTC (if given enough time).

So for example if you could sell 140k USD worth of your BTC, you could go back and double-spend it, and end up with a profit after the 140k expenditure required to control the network. Of course doing this in practice without anyone noticing seems just about impossible, so there's not much incentive to try... I believe it remains more profitable to just use all that hardware to mine.

Edited to add-- this ignores other practical problems, such as: (1) nobody currently has control of 140k USD worth of BTC; (2) moving any significant amount of BTC would also move the markets, such that trying to sell 500k BTC would result in considerably less USD (or whatever other currency) than the current market price; I'm sure there's more I can't think of...

[FreeMoney]

... $140,000 dollars required to control the network... still not prohibitory expensive.

Lets try and not get attacked until attacking the network costs at least 50% of the economy. ~ $500,000 or ~ 350GHash/sec

Although this sounds disturbing, keep in mind that "controlling" the network doesn't mean you can steal BTC from people. It does mean you can probably prevent others from generating blocks, probably block any particular transaction from going through, and probably double-spend BTC (if given enough time).

So for example if you could sell 140k USD worth of your BTC, you could go back and double-spend it, and end up with a profit after the 140k expenditure required to control the network. Of course doing this in practice without anyone noticing seems just about impossible, so there's not much incentive to try... I believe it remains more profitable to just use all that hardware to mine.

My favorite part is when 7 groups attack us at once, each with enough power to succeed and they all fail. 

[sturle]

Can anyone figure out what the total computing power of the bitcoin botnet is?

We are right at 100 g hash/sec right now. That's 7.2 blocks per hour at the current difficulty.


Someone mentioned that a 5970 GPU has about 5Tflops each, using those caclulations, the bitcoin network is closing in very quickly on one PetaFlop of processing power.

http://en.wikipedia.org/wiki/Tianhe-I the current fastest super computer has about 2.5 PetaFlops.

.... wow !

FLOPS are irrelevant for Bitcoins.  A Phenom II X4 is much faster than a 5970 measured in FLOPS, but a 5970 is 50 times faster than a Phenom II X4 at generating bitcoins.  Fifty!  You could count MIPS (Meaningless Indicator of Processor Speed), which is a little bit more relevant, but in reality it is all about how many SHA256 hashes the hardware can do per time unit.  The 5970 is exceptionally fast at just that.  The 2.5 Petaflop comuter may not be faster than one or two 5970s at generating Bitcoins.  It is probably optimized for double precision floating point with fast CPU interconnects, and simply not useful for simple integer calculations.

[theymos]

Is that really true?  I thought the "longest chain" was now defined in terms of the difficulties of the specific hash values in the chain, so I would expect that once a client has seen both blocks, it will build on whichever has the smaller hash value.  Is it not working that way?  Of course until you see the second block, you build on the first one, and it may take some time to switch.

Length has always been defined as "total work", but this is just the number of blocks multiplied by the difficulty of the blocks (for each 2016-block section). A smaller hash is not considered to be better than a larger hash.

[twobitcoins]

Length has always been defined as "total work", but this is just the number of blocks multiplied by the difficulty of the blocks (for each 2016-block section). A smaller hash is not considered to be better than a larger hash.

Not always -- from what I can tell, the notion of length as "total work" was introduced in r109 / v0.3.3.  Before that, length was the number of blocks.  But somehow I missed that we are computing work based on difficulties rather than actual hashes -- thanks.

[Anonymous]

Someone (I wont say who) was discussing investing $200 000  into computer hardware which would mean they would control the network for the conceivable future.

Benevolent dictator anyone?