Bitcoin Forum

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.

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

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.

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

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

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

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.

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.

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.

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.

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.

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.

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

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

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

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.

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.

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?

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

This thread reminds me of this character.

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

Hence the benevolent part.  :)

What if somebody confiscate ArtForz's mining rig?  :(

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:


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

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

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.

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

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%

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

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.

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.

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.

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

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?

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


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

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.

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

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.

I feel that ByteCoin is right.  However, a counterattack:

If the network suspects a cartel, there are several strategies to make life harder for the cartel.  here is my idea.

At the expense of some unlucky honest block generators, impose a time restriction of, say, 20 seconds before any two blocks can be accepted by a node.

Cartel finds block 1 and 2 before the rest of the network does.  Say an honest generator finds block 1 and immediately transmits the message to the rest of the network.  The cartel matches by sending block 1, but the cartel now has to wait 20 seconds before they can transmit block 2.  If an honest generator finds block 2 in that 20 seconds, they too will wait until the 20 seconds is up.  I'm not sure that 20 seconds is the right number, but it at least forces the cartel into more races.  The cartel will necessarily have a lower fraction of blocks if the network adopts this strategy.

There's a solution to a participant withholding blocks that is used by Hashcash (http://en.wikipedia.org/wiki/Hashcash):

So part of the computed input to the hash is a rounded version of the current time. If Bitcoin had something like this (and I'm sure there's some messy mechanics involved), it would allow us to reject blocks that have been stored for longer than a day (in this example). I suppose a cartel could precompute blocks in the future and hold them till they become valid / useful, but if the range for this were say, 4 hours?

There already is a timestamp, and you already will reject blocks too far in the past or future.

In order to make the network 'waste power', you only need two things:

• Keep at least one solved block to yourself for any amount of time, and
• somehow do you best to later get that block into the chain, even though you're not releasing it right away.

If you can accomplish both of these goals (the second goal being the difficult one), you slow down the rest of the network without slowing down your own processing power, and so you end up with relatively more processing power compared to the rest of the network.

The attacks being discussed, as I understand them, ask the questions:

• What if you release your hidden block as soon as the rest of the network releases its next block? There will be a race which you might be able to win, but how often and is it worth it?
• Same question, but is it possible to find a way (e.g. lots of connections to lots of other clients) to increase the chances that your just released block will get into the chain, and the competing block will not?
• If you happen by chance to get additional blocks ahead of the network (which is likely to happen on occasion), can you use this to further your advantage?

I'm not sure if question #2 has been answered, but if it is possible for a cartel to give itself a networking advantage, it appears to gain a mining advantage even if it's a not-so-big cartel. Even if #2 is not possible, ByteCoin has a simulation where #3 is regardless a problem (although you have to be a pretty big cartel to pull it off).

In my opinion, the timestamp of a block doesn't give any information on whether the block was generated and released immediately to the rest of the network or not.

Consider the following case:

• The current block chain has N blocks at time T0.
• The "cartel" finds a new block "N+1", let's call it block X, at a certain time T1 and decides not to publish it right away.
• Some time later at T2, somebody not inside the cartel finds also a block "N+1" (call it block Y) and releases it immediately to the rest of the network.
• Once one of the cartel nodes see this block Y, the whole cartel releases block X (and doesn't transmit block Y to other nodes).

What does an honest node see at time T3 (seconds later then T2): it gets (at best) two new solutions X and Y and it has to decide which one is "the best" to start working on. If it would rely on the timestamp T1 and T2 of the blocks, block X will win each time, as it was created (well) before block Y !
As the difficulty is adjusted so that blocks are generated in average every 10 minutes, T1 and T2 won't be hours apart either (but probably between 0 to 30 minutes).

So the cartel has two advantages: it is already working for the time T2-T1 on block N+2 (and if it has already been found, it can destroy block Y instantly by publishing block N+2 too) and it can prevent transmitting "non-cartel" blocks to other nodes to a certain degree.

You might be able to leverage this technique to gain an advantage over the network with less than 50% of total processor power under certain ideal conditions; but you will still need something very close to 50% even if your attack conditions are perfect.  It's also an attack vector that is unsustainable, as the first non-cartel block to get accepted by the network breaks any prior computational advantage and renders the cartel's prior work towards the next block based upon their delayed block worthless.  In the end, I would say that the conditions required to make this work would be nearly as difficult for any group as simply aquiring the resources to take 50% of the network.  Either way it's at a nation-state level already, and we are not a particularly large network.

http://inertia.posterous.com/bitcoin-mining-cartels-a-total-non-threat

I believe you hit the nail on the head here.  I believe this could be happening right now.
Look real closely at some of the stats @ nullvoid, http://nullvoid.org/bitcoin/statistix.php?showallblocks

Several blocks are found in less than 1-2 minute, some even have been found in negative time (like block 100557 found in -19 seconds).  Today it seemed like many of the blocks are being found well underneath the average time.

I also noticed that when the mining pool @ bitcoin.cz got a block, my windows Bitcoin client didn't get notified of the block update for 6 minutes! 
That means the Pool got a 6 minute head start of everyone else @ 5.5 Bhash/s ... that's a good head start.  I'm not sure what caused this behavior, but it was interesting to watch happen before your eyes.  Go figure, the bitcoin pool got several blocks after that too, then didn't get any for several hours.

I'm also curious if the bitcoin pools are being messed with by said "cartels", as slush said his server came under a DDoS attack last week....hrm...

I doubt that there is anything untoward happening here.  The timestamps in the blocks are based off of the generating machine's clocktime, which can vary considerably.  Even if it's being attempted by someone, it's not detrimental to the network.

I'm not talking about the blocks time stamps.  I saying I sat in front of my PC, watched the pool get a block, noted the time on MY desktop, and 6 minutes later (again on my desktop) my bitcoin client updated it's block count by 1.

To be clear, my windows client is just being used to monitor when blocks go up or when I generate coins.
My Linux box has the GPUs in it, and is contributing to the pool.

When the bitcoin.cz pool got a block, it was 6 minutes before my windows client saw the update.  WHY???

Explain how a 6 minute delay occurs before my bitcoin client on my windows box sees the block count get updated after it was solved on my other PC (yes, I found the block for the bitcoin pooled mining).

Just started to search a thread to put about the same question to the BTC community.  ???

Can you plz link to that thread?
Thx

I can't answer this one.

No, I didn't create a thread, I just said that I was searching a thread to ask the same question. Sorry for my English, I was misunderstood.


I doubt that somebody can.

More interesting examples from http://nullvoid.org/bitcoin/statistix.php?showallblocks:
-383 seconds to find block 100597
-54 seconds to find block 100671
-58 seconds to find block 100697

278 seconds to find block 100810
9 seconds to find block 100809
52 seconds to find block 100808
88 seconds to find block 100807
342 seconds to find block 100806

Are the cartels onto something here or is this an anomaly?

Found something that can check SW state of large HPCs.

InstantCheck: Checking the Determinism of Parallel Programs Using On-the-fly Incremental Hashing
http://www.upcrc.illinois.edu/media/publications.html
This could graph changes to SW or running programs by comparing previous hashes of software runs (Deterministic replay).
It might be useful to see who is monkeying with codebase and trying to game the system.
Simple change to isStandard() would allow reporting to all generators and cartels... but this is future stuff not needed for beta :-\

"Determinism is generally defined as producing observationally equivalent outputs on
all executions starting from observationally equivalent inputs"
https://researcher.ibm.com/researcher/files/us-mtvechev/SAS%202010%20-%20Determinism.pdf

isStandard() detects scout tx
creates test tx and watches IO then creates hash (worker) that reports to generators nodes (hives)
compares to previous hash for inconsistencies, cool!

I would like to see the java on this but I don't think it is FOSS.

Stop this conspiracy. DDoSed was completely another service, not pool itself. And I already know who was the attacker - it was my colleague (tester), playing with new version of performance testing tool. Yes, he was so dumb that he pointed testing tool @ 100mbit line to my poor personal VPS :-/.

Well, people are suspicious when pool find blocks too fast, they are suspicious when pool find blocks too slow; You probably need block exactly every 3-4 hours, right? :-)
I found two block in a row with single 5970, so numbers above for 5ghash pool are not so exciting for me. It is only kind of luck.

Edit: Oh, sorry, now I see those blocks are not generated by pool. I was confused because FreddyFender submitted this comment also to pool thread.

This article is being spread around facebook and co
http://hackingdistributed.com/2013/11/04/bitcoin-is-broken/

Before this kind of attack gets interessting to any one party that could afford to do it right now, it would be too expensive.
Say they pump a million USD into mining gear and get a significant amount of the network. Imagine half of every other miner out there plugging in an extra bitfury because they see their rewards have dropped.
The whole chunk they just bought for a million dollar would be useless again.

The cynical assumption the article makes is not that any one party could afford to do it, but rather that huge masses of existing equipment people overpaid for would willingly jump to a pool offering this strategy in order to recoup costs.