Mining cartel attack

[Anonymous]

http://bitcointalk.org/index.php?topic=431.0

This thread reminds me of this character.

[theymos]

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?

I trust ArtForz even more than Satoshi. If he did that, it would be a great benefit to the network.

[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?

I trust ArtForz even more than Satoshi. If he did that, it would be a great benefit to the network.

Hence the benevolent part. 

[kiba]

What if somebody confiscate ArtForz's mining rig? 

[btchris]

...
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.
...

I think this is really clever, and assuming you could get the required network connectivity to enough of the network, I can't see any reason this wouldn't work.

I just spent longer than I'd like to admit trying to figure out how much of an advantage the cartel would receive, given ideal network connectivity. Apparently my math skills are not what they used to be... so I wrote a quick simulator instead.

The only rule oddity in the simulator is: when the Network (all those who are not the cartel) solves a hash, it is not credited a mined block if the preceding block was mined by the cartel. (In this case, the cartel would use its superior network connectivity to "override" the network's newly mined block with the cartel's previously mined block). So in other words, I have something like:

Code:

if (rand() < $p) {  # if the cartel solves the next hash
  $cartel++;  # cartel gets credit for mining this block
  $last = 'c';
} else {
  $network++ unless $last eq 'c';  # network gets credit unless the cartel has "overridden" it
  $last = 'n';
}

After running through 10M iterations of the above using different values of $p (the cartel's share of CPU power), I ended up with (assuming network conditions ideal to the cartel):

Cartel's CPU control: Cartel's take of mined blocks
5%: 5.3%
10%: 11.0%
15%: 17.2%
20%: 23.8%
25%: 30.8%
30%: 38.0%
35%: 45.3%
40%: 52.6%
45%: 59.8%

Of course, this was assuming that the cartel never fails in its attempt to "override" a block. What if the cartel fails to "override" say 15% of the blocks it potentially could have overridden (losing those blocks to the Network)? If I run this through a modified simulator the numbers look like:

-- 15% "override" failure rate --
Cartel's CPU control: Cartel's take of mined blocks
5%: 4.5%
10%: 9.5%
15%: 15.0%
20%: 21.0%
25%: 27.3%
30%: 34.0%
35%: 40.9%
40%: 47.9%
45%: 54.9%

After trying other failure rates, it turns out it's beneficial for the cartel to attempt this cheat as long as it controls a larger percent of the total CPU power than its predicted "override" failure rate (so at least 15% control in the example above).

The numbers don't look too alarming to me personally, but I think there may be a simple fix (well, maybe not simple to code, I don't know...). We could use a heuristic in the client along the lines of:

If multiple solved blocks arrive within say 15 seconds of each other (for the same block number in the chain), instead of ignoring all but the first:

• Use the block with the most accurate timestamp, and
• flood them all out to the network (so other clients can make their own decisions based on their own internal clocks).

The cartel can't predict how long it would need to delay releasing its block, and so it can't predict what timestamp to add. It also can't change the timestamp after solving the block (I'm pretty sure the timestamp is part of the hash, is that true?).

So... (wow this post turned out longer than I thought...) any thoughts?

-Chris

[ByteCoin]

The mining cartel problem is real. The basic implementation outlined by RHorning is well understood but the more effective version outlined by mtgox is a serious problem. I have an obvious improvement to mtgox's improvement as follows:
Cartel miners only communicate their new generated blocks to other cartel miners.
The cartel miners then try to find new blocks based on the previously found but unpublished block.
The cartel miners have a certain probability of being one or more blocks in advance of the rest of the network.
When a non-cartel miner finds a block then the cartel miners attempt to punish them by publishing up to 2 of their precomputed blocks.
If the cartel miners were 1 block ahead then the non-cartel miner stands a fair chance of winning. Obviously the cartel miners will be busy using their block as the base to build the next block.
If the cartel miners were 2 blocks or more ahead then their chain is longer and the non-cartel miner is punished.

People thinking that being a cartel member is suboptimal because honest miners supposedly make more money are neglecting the value to the cartel of punishing non-cartel miners.

ByteCoin

[RHorning]

The mining cartel problem is real. The basic implementation outlined by RHorning is well understood but the more effective version outlined by mtgox is a serious problem. I have an obvious improvement to mtgox's improvement as follows:

If a cartel could somehow, by luck or circumstances, get "ahead" of the rest of the network for awhile, this sort of "attack" could certainly happen.  "Saving" up blocks "in reserve" is certainly a way to get ahead for at least a short duration, releasing block into the network on an as-needed basis.   Since the cartel would be ahead of the rest of the network, they would also be making hashes off of the latest block in the cartel, not the latest in the network.

The trick would be to decide when to "cut losses" if the cartel somehow ends up on the losing chain for a bit.

The whole point is that the cartel is "forcing" the rest of the network to "waste" their CPU cycles on blocks that aren't going to be accepted.  Any CPU cycles not spent on the longest block are clearly beneficial to the cartel.

There isn't much lost if the cartel simply abandons a chain if they are one block behind.  That is essentially what happens anyway if you are not in a cartel.  You build upon the last block of the longer chain and move on.  If you have a block in reserve, flush the block out to the network to compete as a split chain, but if you get behind simply try again.

BTW, are the "timestamps" on blocks put into the hash?  I'm thinking more along the lines of trying to figure out how to detect if such an attack may be happening.  Nothing conclusive, but I think you could "build a case" at least from a number of clues that such an attack may be underway from a series of "strange" things happening in the network.  An unusually large number of "competing" chains and block timestamps that seem to be regularly out of order might be a clue.  It would take some solid detective work including gathering data from "ignored chains", but I think such an attack could be identified if it was a persistent attack.  It wouldn't be easily detected and a simple algorithm may not be sufficient in terms of blocking a particular node from submitting a block due to being in that cartel, but broadly speaking I think it could be detected as happening and possibly identifying which blocks "belong" to the cartel as more data comes in... unfortunately after the block has been firmly established into the chain.

This kind of "intel" could also be useful even for a cartel, as they might be able to detect if a second cartel is active.  Tracing blocks and money spent might be useful to identify who could be in the cartel.  Again, a single transaction might not be traced, but several transactions over a period of time tend to lose anonymity and certainly give some information not found with a single transaction.

[Gavin Andresen]

The only rule oddity in the simulator is: when the Network (all those who are not the cartel) solves a hash, it is not credited a mined block if the preceding block was mined by the cartel. (In this case, the cartel would use its superior network connectivity to "override" the network's newly mined block with the cartel's previously mined block).

Did you simulate network connectivity at all?  Bitcoin is a semi-randomly connected network, where most of the connections are (I would guess) outbound connections from non-generating nodes who are sitting behind firewalls.  With a typical node having 8 random connections, to different /16 networks, it seems to me it would be pretty tough to get tight-enough control over enough network connections to consistently win the "announce a new block" race.

Anybody know how to estimate what percentage of connections the cartel would have to control to only lose the announce-a-block race 15% of the time?  It'll be way more than 15%....

[ByteCoin]

I did a simulation of two cartel strategies along the lines of my previous post. I have assumed that the cartel does not have any superior ability to propagate its blocks across the network. If the cartel and the non-cartel miners publish a block at the same time I have assumed that they have an equal chance of being accepted by non-cartel miners. This therefore is a lower bound on the cartel attack effectiveness.

When the network generates a block, if the cartel has just one unpublished block then the best strategy seems to be to immediately publish the stored block and let the two race across the network.

Neglecting the benefit to the cartel of punishing non-cartel members, the cartel starts to pay off when its fraction of the generating power exceeds about 41% of the total.

ByteCoin

The raw percentages are as follows:
Cartel power Cartel block fraction
0%   0.00%
1%   0.46%
2%   0.92%
3%   1.41%
4%   1.89%
5%   2.50%
6%   2.96%
7%   3.50%
8%   3.97%
9%   4.56%
10%   5.17%
11%   5.68%
12%   6.52%
13%   7.10%
14%   7.85%
15%   8.42%
16%   9.37%
17%   10.02%
18%   10.76%
19%   11.91%
20%   12.53%
21%   13.51%
22%   14.49%
23%   15.29%
24%   16.25%
25%   17.42%
26%   18.59%
27%   19.53%
28%   20.90%
29%   22.01%
30%   23.27%
31%   24.80%
32%   25.94%
33%   27.28%
34%   28.96%
35%   30.49%
36%   31.56%
37%   33.86%
38%   35.82%
39%   37.23%
40%   39.13%
41%   41.19%
42%   43.12%
43%   44.39%
44%   47.07%
45%   49.41%
46%   51.29%
47%   53.41%
48%   54.98%
49%   56.91%
50%   59.86%

[Gavin Andresen]

I did a simulation of two cartel strategies along the lines of my previous post.
Cartel power Cartel block fraction
......
50%   59.86%

There is something wrong with your simulation.  Proof:

Imagine a bitcoin world with two Cartels, each with 50% of the power, each following the strategy you outline.

It is obvious that they cannot BOTH get 59% of the blocks.

[ByteCoin]

There is something wrong with your simulation.  Proof:

Imagine a bitcoin world with two Cartels, each with 50% of the power, each following the strategy you outline.

It is obvious that they cannot BOTH get 59% of the blocks.

I meant that I simulated a number (now 6) of different cartel strategies operating in the normal network to see which was most effective. I did not simulate two competing cartels operating at the same time.

I recently simulated the case where the cartel is three times more likely to get the non-cartel members to accept the cartel block when a non-cartel block and a cartel block are published at the same time. In this case the cartel generates more than its fair share of the blocks when it has 34% of the generating power.

ByteCoin

[Gavin Andresen]

If you're simulating, be sure you're not overlooking the 'opportunity cost' of working on the next-valid-block when you're 'holding back' blocks.

Example:

Cartel finds block N.  Instead of releasing it right away, Cartel holds it and starts working on block N+1 (trying to get a head start).

Before Cartel finds block N+1, somebody else finds an alternate block N and announces it.

IF Cartel loses the race to announce, then Cartel has wasted time looking for a block N+1 that will not be accepted.

If they simply announce block N right away, they'll never waste time trying to find a block N+1 that has only a 50% chance  of being accepted.

Unless the Cartel can propagate their blocks across the network faster than the whole rest of the network, there is never an advantage to holding back blocks.

[btchris]

Did you simulate network connectivity at all?  Bitcoin is a semi-randomly connected network, where most of the

Not really, the sim was very simple. During a race between a cartel-generated block and a Network-generated block, the second sim I ran assumed that the network as a whole received the cartel block 85% of the time, and it received the network block the other 15%. This loss had a negative affect on the cartel, but not a huge one.

I also assumed that the cartel only kept one solved block hidden from the network. As mentioned by ByteCoin and RHorning, the cartel could do better by keeping additional blocks hidden, and only releasing them when required to maintain control of the network's chain as much as possible, further improving the cartel's performance.

[RHorning]

The numbers don't look too alarming to me personally, but I think there may be a simple fix (well, maybe not simple to code, I don't know...). We could use a heuristic in the client along the lines of:

If multiple solved blocks arrive within say 15 seconds of each other (for the same block number in the chain), instead of ignoring all but the first:

• Use the block with the most accurate timestamp, and
• flood them all out to the network (so other clients can make their own decisions based on their own internal clocks).

The cartel can't predict how long it would need to delay releasing its block, and so it can't predict what timestamp to add. It also can't change the timestamp after solving the block (I'm pretty sure the timestamp is part of the hash, is that true?).

So... (wow this post turned out longer than I thought...) any thoughts?

-Chris

This is more interesting to think of a way to stop this kind of attack through accurate time stampping.  So far, the assumption is that coming up with an accurate authority for chronological accuracy (aka a "trusted" time authority) is an intractable problem for a peer to peer network.  Bitcoin bypasses that entirely and at the moment mostly ignores the time stamp other than as a general "guide", and there have been some blocks already in the block chain created with timestamps that are before the previous block that it is supposedly following and hashed from.

If there could be an accurate chronometer (within a 10 second or so accuracy) to verify a block and thus reject blocks "made" in the future or to reject sub-chains that include blocks with negative time differences, it would certainly help to stop or significantly restrict a cartel attack.  The trick is to establish such a time stamping authority that could be recognized by a peer to peer network.

[btchris]

I did a simulation of two cartel strategies along the lines of my previous post. I have assumed that the cartel does not have any superior ability to propagate its blocks across the network. If the cartel and the non-cartel miners publish a block at the same time I have assumed that they have an equal chance of being accepted by non-cartel miners. This therefore is a lower bound on the cartel attack effectiveness.

When the network generates a block, if the cartel has just one unpublished block then the best strategy seems to be to immediately publish the stored block and let the two race across the network.

If the cartel doesn't have any superior network connectivity, I'd think it would on average lose any race where it has just one unpublished block. By the time it knows it should try to publish it's one unpublished block, it along with some of the rest of the network will have already seen the Network's competing next block.

I'm thinking having superior network connectivity is important for this type of attack to be lucrative...

[btchris]

If multiple solved blocks arrive within say 15 seconds of each other (for the same block number in the chain), instead of ignoring all but the first:

• Use the block with the most accurate timestamp, and
• flood them all out to the network (so other clients can make their own decisions based on their own internal clocks).

This is more interesting to think of a way to stop this kind of attack through accurate time stampping.  So far, the assumption is that coming up with an accurate authority for chronological accuracy (aka a "trusted" time authority) is an intractable problem for a peer to peer network.  Bitcoin bypasses that entirely and at the moment mostly ignores the time stamp other than as a general "guide", and there have been some blocks already in the block chain created with timestamps that are before the previous block that it is supposedly following and hashed from.

If there could be an accurate chronometer (within a 10 second or so accuracy) to verify a block and thus reject blocks "made" in the future or to reject sub-chains that include blocks with negative time differences, it would certainly help to stop or significantly restrict a cartel attack.  The trick is to establish such a time stamping authority that could be recognized by a peer to peer network.

Actually I was thinking that just using the local time on each client would be good enough, I wasn't assuming the existence of an accurate chronometer (although having such a source might be better).

If all clients flood all competing blocks, than all clients will be able to make their own decision on which block is best (and they would build the chain off the best block, even as they continue to flood the competing blocks). Eventually, the network will converge on a decision that should include the block with the most "accurate" timestamp in the network's opinion. So as long as enough of the nodes have somewhat accurate clocks, the network as a whole can often make the correct choice.

I have no idea how to actually test this theory though.... It might be interesting to monitor the network for new blocks, and compare the block-received time to the block timestamp, maybe this would result in some idea of how accurate or inaccurate the network machines are?

[ByteCoin]

Gavin, I believe my simulation is accurate. I will post a longer explanation when I have read davidonpda's pending article.

I posted a huge reply to a previous post explaining exactly this...

Showing that the cartel attack only works with greater than 50% and nothing less...

I also mentioned an attack that hasn't been discussed. If my post was deleted could a mod explain why? And/or let other people know about the attack so it could be discussed as necessary?

I saw a post from you which was just a complete quote of my post with the numbers. I followed up to it saying "content?" and that post has disappeared too.

Please try to re-do your post. I'd love to read how a cartel attack works with 50% and nothing less as my simulations and some noddy maths seem to disagree.

If anyone on the forum can easily compute a steady state from a simple infinite Markov chain then we can put this discussion on a rigorous footing.

I believe that either gavinandresen, btchris and davidonpda are all spectacularly wrong or I'm wrong which would be embarassing.

I would like to revise my previous statistics and state that a cartel with no preferential network access can be profitable with 33% of the generating power. If it can get its blocks accepted three times more frequently in the event that two blocks are published at the same time then it's profitable at about 20% of the generating power and at lower powers only suffers a very modest degredation in its performance for it's cartel enforcement activities.

ByteCoin

[RHorning]

Actually I was thinking that just using the local time on each client would be good enough, I wasn't assuming the existence of an accurate chronometer (although having such a source might be better).

The current method employed within the "official client" is to ask essentially "what time is it?" from the other neighboring nodes and come up with an approximate average, operating on the assumption that most of the nodes are being honest or at least trying to.  It is something that can be manipulated if an attack is being done though.  Using this method can identify and exclude significant outliers (somebody sets their clock to last year or worse to 1970, so will be excluded) but you may have a standard deviation on the order of a few minutes and perhaps longer.  Outliers would be several standard deviations from the current mean, with a simplified algorithm simply excluding the largest and smallest values collected in this manner.

The time is transmitted with the version message between nodes when the node first connects.  As I said, it is already a part of the protocol.  Its only use at the moment is to set up a "delta time adjustment factor" when time stamping blocks being mined by that client.

That may be sufficient, and to "keep honest nodes honest" perhaps include a warning message to a computer user if their clock is significantly different than the clock mean of its neighbors, noting this could be a security enhancement if they set their computer's clocks to the correct time.

While any node can reject any block for any reason, rejecting blocks because of temporal anomalies certainly could make a huge difference here in stopping a cartel attack like this.  If you can get the clock more accurate, it will help shorten the window of opportunity that a cartel could use to engage in an attack of this nature.  The more inaccuracy in time stamping that exists, the more of a window of opportunity also exists to manipulate that time inaccuracy to an advantage for a group wanting to skew block creation to their own ends.

[Gavin Andresen]

I posted a huge reply to a previous post explaining exactly this...
I also mentioned an attack that hasn't been discussed. If my post was deleted could a mod explain why? And/or let other people know about the attack so it could be discussed as necessary?

I deleted two posts-- one from you that was a quote of ByteCoin's simulation results (and nothing else).

And a second from ByteCoin (if I recall correctly), saying essentially "what's up with the empty post?"

[nanotube]

haven't read the whole thread... but here's the framework as i see it, back to basics.

with 30 percent of total cpu capacity, a party has 30% chance of generating any given block, and "the rest of the network" has 70% chance.

to run the "reject other blocks" attack, as i understand it, i'll generate a block but keep it to myself, while continuing to work on generating a block that builds on top of my hidden block.

so, let's say that I generated a block. now, i have two choices. choice one - i release it to the network, and claim my 50btc, and start working on my second block, which i then later also release and claim my next 50 btc.

choice two - i keep it hidden, and work on generating another block building on top of my secret block, all the while the rest of the network is still toiling away on the first block. in order for me to make the network 'waste power', in other words, in order to be able to trash the rest-of-network's block, i need to be able to generate another block after the rest-of-network generates one block, but before the rest of the network generates two blocks.

the probability that the network will generate 2 blocks while i'm working on the next block is .7*.7 = .49.  so /given that i have generated one block/, i have a 51percent chance of making the network lose a block, and a 49% chance of losing my own block.

what's the expected value of this proposition? 51% chance of keeping 100btc for my two blocks, costing the network 1 block... and 49% chance of losing both blocks and having nothing to show for it.

in all, a losing proposition, if i ever saw one.

now, if my goal is simply to make the network slower - i can see this working. if my goal is to somehow make a profit... i don't see how.