I have tried to quantify under what circumstances a 51% attack can and can't be done in the comments to a sister answer, and a couple of people pulled me up on the mathematical ins and outs. So I thought I would write this down exactly, at best I will answer the question slightly more precisely than has been done, and at worst I will make it easier for someone to point out to me exactly where I am going wrong.
Suppose that you control around half of the computing power on the network, and that you want to attack the network. There are essentially two ways you can go about this:
- You can withdraw all your computing power from the uncorrupted blockchain, and dedicate it to your attack.
- You can continue to apparently participate in normal hashing, and try to reach a situation which you can exploit.
Let us first discuss the mechanics of these, and then look at the mathematics:
Suppose that there is some transaction(s) which you can profit by removing from or adding to the blockchain, and you don't care whether anyone notices that you are preparing an attack. To make life easy, say it's a single transaction with a counterparty called Bob, and that you want to remove it. Let's assume that the transaction has to be confirmed N times on the legitimate chain before you are ready to attack (for example, you had to wait for N confirmations before being paid fiat in exchange for a coin transfer).
To create an alternative chain, which will be accepted as the longest chain, you have to go back N blocks, add a new block with your modification, and then add blocks to the forked chain, until it is longer than the legit chain. It will take you O(N^2) blocks to do this. While you are doing this, you either publish each block of the forked chain, thereby making the whole network aware of the fork (call it case 1.a), or you stop publishing any blocks at all, letting everyone know that you have withdrawn your resources from hashing (call it case 1.b).
1.a - Strategy 1 with publishing
As soon as you have done this, you lay yourself open to countermeasures - before you get to the right number of blocks. In case 1.a, the fork will be studied by other actors on the network. People will try and resolve the fork as quickly as possible if it is unintentional, and to detect which side is malicious if it is not. (Short unintentional forks have been resolved in the past by agreement between the major pools.)
Now, Bob is obviously going to point to the (probably large) transaction which isn't in your chain, and of course you can equally point to it as a fraudulent transaction inserted by Bob and his evil cohorts. However, he has the fact that it featured in N transactions seen before anyone was aware of any fork on his side. It will hard for you to explain why it doesn't appear in any block on your chain - a lot of the network must have seen it, and since the fork is O(N^2) blocks long, the excuse that it hadn't yet reached you won't wash. (A less sophisticated attack whose object is to destroy Bitcoin, where you for instance pay yourself everyone's money, using this strategy, will completely fail at this point.)
Once enough people recognize your side of the fork as the corrupt one, they simply 'checkpoint' a block on the other side, maybe the one which first includes the transaction with Bob. This means that that block will be treated as the root of the chain. This is already done occasionally when client software is updated, to reduce the amount of checking a client needs to do. The effect will be that Bitcoin itself forks, with people who accept your chain using a different ledger from those who reject your chain regardless of length. This can be done essentially immediately for pools, and pretty quickly for other clients, although they might suffer downtime until it's resolved. As long as everyone quickly moves over to rejecting your chain, you have control of a worthless currency Bitcoin A, while Bitcoin B keeps its value by still being accepted among the rest of the community (in theory - in practice many of them might be put off by the general uncertainty and start using some other currency).
1.b - Strategy 1 in secret
What if you adopt strategy 1.b, and keep your fork secret until it's long enough to beat the 'correct' chain? Presumably, lots of people notice that your hashing power isn't around anymore. This is probably going to worry them, and they will try to do something about it. The most straightforward response is again, to 'checkpoint' a block. Depending on what N could reasonably be expected to be, they will have some idea of N^2, and how long it will take you to catch up. They need to checkpoint blocks which everyone (except you) is happy with, frequently enough to keep foiling your presumed attack. If you want to keep on attacking, you have to generate a new transaction and start from square one every time they do this.
Ideally, the community wants to checkpoint blocks which are a bit more than N blocks old, so that everyone has time to make sure they agree with the transactions in that block, and definitely doesn't want to wait until close to N^2 blocks; in case you get a winning chain and start publishing it before the checkpoint. Since N^2 is a lot bigger than N, there is a lot of scope for doing this.
Note that the failure of this strategy relies on you being missed from the mining. If some attacker has a secret mining pool which no-one is aware of and which is roughly equal in size to all existing mining, they can succeed with this attack. (Call it a 101% attack.)
In strategy 2., you attack the chain, but try to 'keep up appearances' of being non-malicious until your attack has succeeded. The way you do this is to try and overtake the legitimate chain, before anyone has noticed your absence. If you have (roughly) half the power, every other new block on average will be yours, but there could be long runs of only your blocks or only ones which aren't yours.
What you do is, once you have published yours and Bob's transaction, you try to create N+1 blocks, in the same time that the rest of the network creates N. You keep all these secret until the other miners have mined N blocks, and Bob has handed over the cocaine or the Leonardo cartoon or whatever, and then you publish all N+1 of them, making your chain the longest.
If you don't manage to get to N+1 before the rest of the network gets to N, you throw your attempt away, and go back to hashing the proper chain. You wait a while, then arrange another transaction with Bob, and try again. The amount of time you have to wait depends on how unlikely it is that N blocks in a row should be mined, none of them by you.
A couple of points about this method. First of all, whereas in 1.a you would have had to justify your forked blocks to the rest of the network, and therefore you had an incentive to make your changes as plausible as possible, here you can do any changes you like - even paying yourself all the Bitcoin which exist. No-one will see the bogus transactions until it's too late.
What this really means is that you don't need a dupe Bob, who is happy to keep handing over non-Bitcoin assets after a small number of confirmations, provided you are happy to get paid in Bitcoin. If you want to sabotage the currency, you can do so, and are in fact free to pick N as any number small enough that you won't arouse suspicion that you are doing strategy 1.b. If you only want the Bitcoin to buy fiat or to pay a ransom, you have to stick to Bob's N.
Secondly, there is a trade-off between how suspicious your behavior is and how many times you have to try. If you have far more than 50%, long sequences of blocks without any mined by you will be more suspicious, and you might have to hash a couple of blocks on the regular chain to keep things looking normal. If you have close to 50%, it will seem less suspicious, but it will be harder for you to win the race to N+1. Of course making N bigger helps prevent this attack in either case.
Thirdly, here too having lots of secret power could help you, by winning you the race, while making it less obvious that you are hashing on your fork rather than the correct chain. You might try and judge how worthwhile it is to keep secret hashing capacity around ready to attack, rather than use it to get paid honestly.
I accept what some people have said, that having just over or just under 50% makes the different between definitely succeeding eventually with 1.a or 1.b, and only succeeding ever with a small probability. This follows not from the weak Law of Large Numbers, but from the recurrence property of 1-d random walks (a difference between the two is that the latter is applicable even if you had exactly a constant 50%). However, I believe I have argued that it is not good enough to succeed eventually - the O(N^2) time it will take you (which comes from the Central Limit Theorem) should mean that your attack is usually prevented.
On the other hand, providing that you have close to 50%, you should be able to succeed with strategy 2., regardless of whether you have just over or just under. Of course higher proportions and lower N will help you, but the effects are now smaller - if you have 1/2 - h, for h small and positive, your chances will be 1/2 - O(h / sqrt(N)). The Central Limit Theorem works in the opposite direction - even with a coin slightly biased against you, it's not unlikely that you should win a short race by a single toss.
You could also be doing various simple things like only starting an attack if you get the first block before the rest of the miners, or only if you get the first two blocks, etc. Whether this is a good idea, and how exactly to tune this attack depends on how suspicious people are and/or how obliging Bob is.
If you are out for destruction, you can optimize N to your own capacity - if you have under 50%, you are much better at winning short races than long ones.
First of all you should be using as many confirmations as you can afford to, if you think your transaction might be the one that incentivizes GHash.io to go rogue. Secondly there need to be people out there looking for unusual patterns of mining activity, especially big miners disappearing from the network.
However, be warned that wanton destruction of Bitcoin is already very possible below 50% concentration, and that any kind of attack could easily happen if someone has large and secret reserves of power (this applies to many altcoins if their proof-of-work can be done efficiently on Bitcoin hardware).