Bitcoin Forum

A double spend attack may be detectable after the fact, but is not likely to be stopped on time to prevent BTC theft. Pool owners with a significant hashrate are not the only persons capable of using it to their advantage. Here is an example: I am Malory, the proverbial malicious attacker, and I want to attack the Deepbit pool, managed by Tycho.

(Edit: Fixed the chain on which the BTC needs to be spent - thanks kjj/DamienBlack).
(Edit: Replaced fictional "500 BTC" amount with "10k BTC").
(Edit: Removed mentions of "50% hashrate" to emphasize that it is not required to perform a double spend.)

Step 1: I buy 10k BTC and transfer them to my wallet.

Step 2: I attack Deepbit's infrastructure to surreptitiously gain administrative control of the servers (eg. via a compromise of Tycho's workstation). Optionally, I also rob the pool of its BTC to further maximize my gains (using the pool's computational power to double spend its own money - hah!)

Step 3: I select a period of time of 2 hours during which Tycho is offline/sleeping. 2 hours is all I need because his pool, Deepbit, controls about half of the global Bitcoin network hashrate. Note that controlling exactly 50% or more is not necessary; if less than 50%, the probability of the attack being successful is simply lower.

Step 4: During these 2 hours, I send pool users work items to start forking the block chain, from the current legitimate block, but without broadcasting the forked blocks to the global Bitcoin network. The only visible effect is that the global network appears to solve ~6 blocks (instead of ~12) during these 2 hours; but no one notices because it happens all the time due to expected statistical variation. As a matter of fact, it is happening right now: in the last ~110 minutes only 6 blocks have been solved (135104-135109), and there is no reason to find this suspicious whatsoever.

Step 5: In the legitimate block chain (built by miners not in the pool), I include a transaction to transfer 10k BTC from my wallet to my TradeHill/Bitcoin7/MtGox account.

Step 6: TradeHill/Bitcoin7/MtGox detects my txfer after the legitimate block chain grows by 6 blocks (6 confirmations). I sell the 10k BTC.

Step 7: Profit! I have plenty of USD in my account. I quickly sell it on bitcoin-otc (eg. using MtGox's merchant API), or transfer it to my Dwolla account, or multiple accounts to bypass typical withdrawal limits.

Step 8: During this time, my forked chain should have grown 1 more block than the legitimate chain (if the attack was successful). I broadcast it to the network, which instantly invalidates the 10k BTC I transferred to TradeHill/Bitcoin7/MtGox. The 10k BTC automatically "reappears" in my original wallet (which I can now double-spend). The exchange is short on BTC and is screwed. An investigation later in the day reveals that Tycho's pool was compromised. Tycho's reputation is ruined. People switch to another pool, which gains 50% of the hashrate. I repeat the same attack on the other pool, and double spend again the BTC stolen from previous pools. Rinse and repeat.

Your original 500 BTC wont be much good after the price of bitcoin collapses
when the biggest pool is known to be used in a forging attack against the blockchain.

Which hacker with such skills will really ruin the entire economy for a few thousand bucks?

No problem. I also quickly resell this remaining 500 BTC right after my attack.

Why would the hacker not divert the legit blocks being mined with 5000ghash/s to himself instead?
You have zero risk

(no initial purchase of 500BTC or need to fork the blockchain, people are still being shown they get paid so they continue mining, and you get about 6-10 solved blocks worth of BTC within 2 hours)

After the attack you have BTC from the 'normal' blockchain and you can launder them & sell for cash. Much less effort

What if the hacker is ben bernanke and doesn't give a crap about bitcoins and just wants to see them fail.

You get right on that then. I'll be waiting.

Remember, if deepbit is 50% of the network, you'd only have about a 50% chance of this attack working (you making a longer chain than the rest of the network. Otherwise you'll probably be found out with no harm done. And this attack could work even if deepbit had 49% or 48% of 40%... the odds just start tilting against you.

Then he could much around for a few hours until people leave the pool. Then everything is ok (with maybe a minor blockchain rollback).

Well, many (most?) pool users automatically withdraw their BTC balance to their wallet. If the attacker diverted the blocks to keep the BTC he would not be able to honor these withdrawals and would be noticed very quickly, perhaps after mining only a few hundred BTC.

Whereas my attack works with any amount of BTC (I should have picked a few thousand BTC as an example). The only limit is your budget to purchase the initial amount. And withdrawal restrictions on the exchanges. But there are ways to bypass them (register multiple accounts, sell your USD balance on bitcoin-otc, etc).

If you hacked the site so thoroughly, you would probably have access to the pool's wallet, the one that makes payouts. I'm sure there is 10s of thousands. Take that and be done with it.

DamienBlack: I wrote this as a counter-example to your comment in another thread that a 50% attack would be statistically noticed in the global hashrate.

I doubt Tycho keeps tens of thousands of BTC on his online infrastructure. His pool profits (~3% fee) only amount to ~100 BTC per day. But my counter example was also to illustrate that Deepbit, with its size, is now a valuable target to any attacker out there. The fact a pool owns ~50% of the hashrate is bad not only for Bitcoin, but also because it concentrates risk. My advice to users is to not keep any significant amounts of BTC in their Deepbit account.

How easy is it to look at what you are mining? Won't people see that they are working on a different block number than the current one? And shouldn't some people notice that they found blocks that don't show?

Yes you have a point. You are correct. A double spend attack could be done quickly. Quickly enough that no one would notice. But honestly, I don't think a double spent is that big a deal, and it can happen below 50%, there is no magic number there. Other people pointed out that at > 50% you can begin moving backward through the whole block chain with statistical confidence. That is true, and a more dire attack. But a pool wouldn't be able to pull that off because people would leave the poll in a day or two, and you wouldn't be able to get that far back in that time since you also have to keep up with the rest of the network while moving backward.

The block data is actually pre-hashed when given to miners in a pool. We have no idea what we are working on. This is the main problem, and various solution have been floated / are being worked on.

You could check your successful blocks, but I don't think many people do. I don't even know of any mining programs that inform you.

This step won't work for two reasons.

First, if the exchange sees your chain as legitimate, you need to assume that every miner also sees it that way.  They will be working on the next block to extend your chain, not the old reverted chain.  Your 500 BTC spend to the exchange will not be overturned on those grounds.

Second, if you manage to somehow time your chain transmission so that it forces a race and gives the other chain a chance to get back on top, if it does take back over, every node on the network will instantly put your 500 BTC spend in their transaction list.  Your recovery attempt will be seen as a double spend.

So, you've spent 2 hours to get an instant transfer into an exchange when you could have just waited an hour.

He has the order backwards, but it could still be done. You would spend on the "legit" original chain, and create a longer chain without that spend, then everyone works on that. It is two hours because that is how long it would take half the network to make six blocks, that is how long the attack would take, done correctly.

You can never move backwards through the chain.  The best you can do is pick a spot in the past and try to catch up.

Yes, you are correct. My mistake. Thank you for pointing out that misconception.

Correct. The 500 BTC txfer to the exchange would need to be in the "legit" chain. I fixed my original post.

It is still a double spend, and it is even more obvious if you spend on the main chain first and then try to reverse it.  Check your debug log.  The node already flags chain reversions and double spends.  Sites that wait for multiple confirmations can (should) be watching.

I wonder what exchange would allow for such a mass transaction of funds to cash if it were sourced from this way, it would cause the exchanges to no longer exist, I don't think there would be a person to give the cash over for this Bitcoin.  Whoever controlled it would have to make sure it has value.

Yes, but deepbit mines about 3,600 a day total, all of which has to be available if his users withdraw. I bet at least some uses don't withdraw everyday (although I do). It could easily have 5,000 in it.

Yes, but the evil pool would not release the "bad" block chain until the first spend already had 6 confirmations, got sold, and sent to dwolla. Then the new block chain would roll it all back.

Look guys, you are thinking about this all wrong.  Security is about how to protect yourself.  The best way to protect yourself is to find that part of your protection that is most at risk and fix it.  

Arguments such as "why would anyone want to break bitcoin", or "you still only have 50/50 chance of double spending" are meaningless in this debate.  These are not factors to what your weakest vector of attack is.  

This is only a simple example, but what if a state actor wished to see the devaluation of bitcoin?  What would they do?  The easiest thing I can think of is a rubber hose attack against the operators of the top n pools.  Now with control of 75% or more of the hash rate the design of bitcoin IS COMPROMISED.  Creative people *will* figure out what the best way to take advantage of that compromise is.  Double spend, ruin the credibility of bitcoin, buy WMD, whatever is the most value to that actor.  Never argue "why would...", "how" is the only argument and if there is a how you ARE vulnerable in that direction.

POOLS ARE BAD!  They make a system that has demonstrable cryptographic security into a "I don't think that guy is cheating, why would he" security.  FAIL!

STOP USING POOLS, or use one of the systems that make pools safe.  If you argue that pools are safe then you are uninformed, or an NSA/CIA/North Korean/Al Qaeda/mobster shill.

If you truly want bitcoin to succeed, then this is a fundamental issue that should be addressed. Risk factors of bitcoin should be evaluated analytically and solved, not justified.

I agree with you on many points, but I can't stop using a pool. Statistically, I'm never going to hit a block (assuming continued 30% difficulty increases). A pool is the only way I get paid. As difficulty continues to increase, this will be true for more and more people.

The solution is: fix the way pools work so that this attack doesn't exist. People are working on that.

See this thread for more info:

http://forum.bitcoin.org/index.php?topic=9137.0;topicseen

What is worse is the pool within the pool things going on.  I think people will see there is no benefit for themselves to keep mining in a pool overall.  I mean, I can only understand if you think in short term goals with Bitcoin, and especially if you don't give a crap about the other benefits of this specific digital currency.

No. The probability of outpacing the legitimate chain with exactly 50% of the hashrate is 50%.

No. The probability of outpacing the legitimate chain after N blocks, no matter what N is, is always 50%.

Think about it. You don't need to outpace every single block. Only the last one matters.

Be creative: you could double your gains by robbing the pool and performing a double spend on this money!

I don't think that you have 2 hours before anybody notices. The blocks will be generated at half the speed after you split off. And the miners themselves will see that their blocks are not in the legit chain.

You have to make sure that the miners know the illegitimate blockchain only, that's way harder than getting 50 % of mining power. This is the internet. Everybody connects to anybody.

But even if it worked, it looks like way too costly for the risk. Besides the risk of detection there is the thing that MtGox will know that your address with the 10k BTC has reverted a transaction. They won't take any more coins associated with that address.

In that case:

You don't have to maintain the forgery sequentially.

You misunderstand the math that explains why this specific number of confirmations was chosen by some exchanges/merchants.

Read the original Bitcoin whitepaper http://bitcoin.org/bitcoin.pdf (section 11). If an attacker possesses 10% of the global hashrate (q = 0.1), in order to reduce the probability of a double spend to less than 0.1%, you should wait for 6 confirmation, ie. force the attacker to fork the chains from 5 blocks behind, that's the z=5 quoted in this section. These are the design parameters that the 6 confirmations are supposed to protect against.

If an attacker has 50% of the hashrate (q = 0.5), then the math is completely off. No amount of confirmations is going to protect you against that.

As a side node, I think there is an approximation error, or rounding error when running the sample code with q = 0.5, because it shows the attacker would have a 100% success rate (it should be 50%).

No, you won't notice a reduced hashrate that lasts for as little as 2h. I showed in the example that it happens all the time, eg. today. Did you find this suspicious? No. Did anyone else? No.

Also, as pointed out by DamienBlack, no pool miner checks that their blocks are in the legit block chain. No one verifies the 80-byte block header they are hashing.

The OP set up his attack wrong. But it is still possible in a slightly different way, and he has since updated the original post to reflect the correct attack. This attack _would_ work, make no mistake. It is possible that the miners would all get together and roll back to the "original" chain, and then you wouldn't have any gains. But this would probably involve a lot of pain and suffering and could take days to get sorted, all the while the bitcoin network would be essentially down. There might be a whole lot of confusion over which transfers are real and which aren't and so on... Most likely, to avoid all of that, we would be forced to continue on the compromised block chain.

And I really doubt anyone would notice in only two hours. Sometimes deepbit doesn't hit a block for a full hour and a half. And their stats are delayed by an hour to prevent pay-per-share manipulation. No one checks the shares they produce to see if they have a block. I don't even know of a mining application that tells you. Two hours is well within the time-frame for an attack. If Tycho doesn't notice, no one will.

But still, I find it unlikely that anyone would be able to pull this off. It is more complex then just robbing the pool, for less gain. I don't feel threatened by the possibility. But let me make it clear, it is a possibility. And the odds are 50%, you don't need 6 consecutive blocks, because you are just holding all your block, waiting to release them later. It they are longer than the other chain, then all clients will accept them. That is a bitcoin rule. The longest blockchain is the "real" blockchain.

Well, each additional confirmation buys you more time. It would take years (edit, only months, because of earlier difficulty) for someone with 51% to undo a transaction with 1000 confirmations.

No. Run the math. Run the sample Poisson code provided in the whitepaper. An increasing number of confirmations only protect Bitcoin for q < 0.5.
For q >= 0.5, no amount of confirmations can protect anything.

Again, it doesn't protect you, it just buys you time, because the attacker has to start that far back in the chain and build a longer chain. But the attacker will succeed (given enough time).

But in my attack, the attacker doesn't have to start "far back" in the chain. He starts forking it from the last known legitimate block... (sorry for my multiple edits, this is complicated)

Please answer to my posting: Your attack still assumes that you can split the internet. That you can dictate what blockchain each miner can see.

No need to "split the internet". The attacker simply withholds the forked blocks, on the pool's server, that are being solved by the miners. Remember that these miners are not connected to the Bitcoin peer-to-peer network. There is no need to isolate them.

This whole attack is possible but is not undetectable. The pool miners will know they are not working on the main chain. However, most of the miners will have no idea and the miner programs will not print it automatically.

The hash of the previous block is contained in the getwork data returned to the miners. If the miner program does the getwork to the local copy of the bitcoin daemon, it can compare the hashes and print warning. It happens occasionally though (some accidental chain forks), however if it happens twice in a row (chain fork differs by two blocks), it is very unlikely by accident and very likely by an attack. It does not seem to be very difficult to program into the miners as an option to print warning and better yet to switch to another pool if it is happening. If large enough number of pool miners switched, the attack would be prevented.
 

Well in that case, the attack would have to be ongoing for as much time as the number of confirmations. In the two hour attack, you can go undo 6 confirmations, in a two month attack, you could undo 600 confirmations (or whatever). Confirmations is still linked to time somehow.


All the clients use the longest rule-following blockchain. If you can provide a longer one then the current one, everyone will use it.

When you are in a pool, you only get pre-hashed data. You can't see anything you are working on. This is the main problem with pools.

But you have to distribute the block in the whole mining pool to generate the next one.

No you don't. The pool pre-hashes all the data. The pool miners have no idea what they are working on, nor do they need to generate it themselves.

Another detail is that with the half mining power you only get 3 blocks per hour because of the difficulty.
So you need 2 hours in the first place to get a confirmation that MtGox accepts.

Then the problem is insecure pool design.

OK, I have not used pools for a long time but if they return a valid getwork (and they should), then getwork returns the block header. The hash of the previous block is there.
https://en.bitcoin.it/wiki/Block_hashing_algorithm

Pools only need to manipulate the target hash so the miners submit all the hashes of difficult 1 and above
The attacker may try to spoof the data block, but then the hash of the data would differ from the midstate.

I'm sorry.  Have I somehow missed what this entire thread is about?

Pools reduce the security of bitcoin.  End of line.

j

Of course they do. That's trivial. But you cannot enforce that people don't do pools. So you have to discuss how pools could be more secure.



EDIT: Btw. deepbit gets huge at the moment. :D

http://chart.googleapis.com/chart?chs=350x200&chd=t:0.78,49.60,3.74,22.54,5.85,0.00,2.64,6.88,0.23,6.50,1.04,0.19&cht=p&chf=bg,s,00000000&chl=ars|deepbit|BitcoinPool|slush|bitcoins.lc|btcguild|MtRed|other|bitpit|btcmine|bitclockers|swepool

Right. Got you.

Personally, I would urge exchange owners to require 144 or 288 confirmations (nominally 24 or 48 hours).

Yes, but listen. IT IS FIXABLE. And smart minds are working on it. It is only the current manifestation of the pool system that allow these pool attacks to work.

http://forum.bitcoin.org/index.php?topic=9137.0

It is possible to have pools work with zero pool attack risk. It is being worked on by smart people. The new system will probably be adopted soon (within 6 months).

That's correct, and what I said from the beginning: the whole attack can be performed in 2h.

6 blocks in a row that require twice the time are not statistically insignificant.

The hash of the "previous block" in the getwork reply is actually completely opaque data to a pool miner, who cannot verifies whether it is legitimate or not. One reason being that it varies based on unpredictable data that is known by no one else but the pool owner (eg. the 50 BTC generation fee transaction).

The only way to prevent the pool vulnerability I described is, as pointed out by DamienBlack, a significant rework of the getwork & pool interface: http://forum.bitcoin.org/index.php?topic=9137.0

Yes it is. It happens many times every single week. Check the timestamps on blockexplorer.com. Also:

6 times in a row? Show me a single example!

The whole point of the 6-blocks-makes-a-confirmation rule is that the probability falls exponentially, and that with 6 blocks in a row it is practically impossible to happen.

I already gave it to you. Multiple times. "In the last ~110 minutes only 6 blocks have been solved (135104-135109)"

Getwork returns data (essentially block header) and midstate. Midstate can be created from data. Data contains block header which MUST contain previous block hash. Block header contains also merkle root which is unpredictable but everything else must be consistent.

Hash is unpredictable but the data to be hashed must be valid. Otherwise the block will not be accepted by the network.

You are right, sorry. At least the average meets your requirement.

You could ignore that, you don't have to accept transactions anyway.

Yes I know thank you.  Let's hope the entire bitcoin enterprise isn't compromised in the next six months.  

I love playing with risk like this.  It's like smoking, the best possible outcome is nothing at all, worst outcome you die a painful death.  It's not like you win billions of dollars for the risk you take on, nope just nothing or death.  In some universes that's a game not worth playing, apparently not so much here.

j

Couldn't help but grab that one. Thank god for smart people! ;p

Yes, if it were in my hands... heaven help us.

Right. In theory it should be possible to modify miners to check this previous hash. For some reason I only remembered the merkle root was here.

It is definitely too draconian. Imagine there is a sudden jump in BTC value and you want to cash out. Sorry, 24 hour waiting.

The exchanges can, however, instate a 24 hours waiting period for cashing out. Essentially, you could withdraw balance that was there 24 hours ago. If there is a BTC reversal, the perpetrator would have a negative BTC balance in the exchange account. The USD balance that is hold for 24 hours could cover the loss then.

That thread hasn't been touched in the past month.  Who, exactly, is working on this?

The fact that this shit is still going on, combined with the ridiculously pollyannaish mentality of most bitcoin users, is seriously alarming.

Maybe the best way is to create a open source mining software solution that is good enough to be adapted by mining pools.

Everything else is doomed to fail, nobody can enforce mining pools to take care about security.

I would say the same ones who hacked into MtGox, cracked so many strong passwords (http://forum.bitcoin.org/index.php?topic=24727.msg317542#msg317542) that no one has a clue how they did it, crashed the market to $0.01/BTC (http://blog.zorinaq.com/?e=55), and ended up stealing a miserable 2000 BTC.  ::)

Exponential (http://forum.bitcoin.org/index.php?topic=11464.0) difficulty (http://forum.bitcoin.org/index.php?topic=20171.msg273411#msg273411) could kill this type of attack.  And it would take a lot less coding effort than changing every node, pool, proxy and miner.