user11277: I would think that amending the bitcoin protocol to require a supermajority, say 60% or 75%, to verify proof of work help reduce the risk of a 51% attack. If this is so, what are the major obstacles or things I'm not contemplating? 
The only thing that immediately came to mind was that it would increase the time horizon on which most transactions are verified, which could be significantly detrimental to the ecosystem. What else?

user18266: 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:
Strategy 1
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.)
Strategy 2
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.
Mathematical analysis
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.
Conclusion
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).

user8717: I think you should state exactly what you mean by "51% attack". If by attack you mean double-spending, the original Bitcoin paper by Satoshi outlines that it brings more reward to mine all the blocks for yourself and obtain 100% of the rewards rather than attempt a re-org for the double-sending, which might lose you the rewards and therefore the miners (which would be leaving your pool during your rewardless attempt to re-org the history). From the paper:

If a greedy attacker is able to  assemble more CPU power than all the
  honest nodes, he would have to choose between using it  to defraud
  people by stealing back his payments, or using it to generate new
  coins. He ought to  find it more profitable to play by the rules, such
  rules that favour him with more new coins than  everyone else
  combined, than to undermine the system and the validity of his own
  wealth.


user5757: David Schwartz has a good answer. 
But to explore a little further, you can roughly think of Bitcoin's proof-of-work system, in the long run, as an election to decide which is the "true" block chain, and hence, which transactions are recognized as having occurred. As it stands, each miner gets voting power in this election proportional to their hash power (one hash, one vote), and the outcome is determined by plurality. So a miner who controls more than half of the hash power can always win the election, and as such is effectively a dictator: she gets to decide which transactions are recognized and which are not. This makes it very easy for her to defraud people, since she can make a transaction, collect the goods, and later declare that the transaction never happened and she still has her money.
Suppose that we could come up with some way to change the election from a plurality to a supermajority (although it isn't immediately clear to me how that could be accomplished). Let's say a 75% supermajority was required. This would have the benefit that an attacker with, say, 70% of the hash power could no longer become a dictator.
But it would have the serious problem that an attacker with only 30% of the hash power could mount a denial of service attack simply by voting in some contrary way. He thus prevents a supermajority from being achieved, no transactions can be confirmed, and the whole currency system comes to a screeching halt.
I suppose this problem is inherent to any political system that uses a supermajority (see for instance the US Senate). Bitcoin is a little  different in that the questions being voted on are not supposed to be controversial: every honest voter should vote the same way. So by design,  the minority should have no voice. And under the current system, they have no voice at all. But with a supermajority, the minority can obstruct the majority, and we don't want that.

user85: The 51% attack is emergent behavior of the system. It's not because there's a "50%" buried somewhere in the protocol that can just be changed to 60% or 75%. Someone with more hashing power than everyone else combined can, given enough time, always build a longer chain than everyone else.

11277: <p>I would think that amending the bitcoin protocol to require a supermajority, say 60% or 75%, to verify proof of work help reduce the risk of a 51% attack. If this is so, what are the major obstacles or things I'm not contemplating? </p>

<p>The only thing that immediately came to mind was that it would increase the time horizon on which most transactions are verified, which could be significantly detrimental to the ecosystem. What else?</p>
 18266: <p>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.</p>

<hr>

<p>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:</p>

<ol>
<li>You can withdraw all your computing power from the uncorrupted blockchain, and dedicate it to your attack.</li>
<li>You can continue to apparently participate in normal hashing, and try to reach a situation which you can exploit.</li>
</ol>

<p>Let us first discuss the mechanics of these, and then look at the mathematics:</p>

<h1>Strategy 1</h1>

<p>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).</p>

<p>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).</p>

<h2>1.a - Strategy 1 with publishing</h2>

<p>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.)</p>

<p>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 <em>any</em> 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.) </p>

<p>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).</p>

<h2>1.b - Strategy 1 in secret</h2>

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

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

<p>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.)</p>

<h2>Strategy 2</h2>

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

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

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

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

<p>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, <em>provided</em> 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. </p>

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

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

<h1>Mathematical analysis</h1>

<p>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 <em>eventually</em> - the O(N^2) time it will take you (which comes from the Central Limit Theorem) should mean that your attack is usually prevented.</p>

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

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

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

<h1>Conclusion</h1>

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

<p>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).</p>
 8717: <p>I think you should state exactly what you mean by "51% attack". If by attack you mean double-spending, the original Bitcoin paper by Satoshi outlines that it brings more reward to mine all the blocks for yourself and obtain 100% of the rewards rather than attempt a re-org for the double-sending, which might lose you the rewards and therefore the miners (which would be leaving your pool during your rewardless attempt to re-org the history). From the paper:</p>

<blockquote>
  <p>If a greedy attacker is able to  assemble more CPU power than all the
  honest nodes, he would have to choose between using it  to defraud
  people by stealing back his payments, or using it to generate new
  coins. He ought to  find it more profitable to play by the rules, such
  rules that favour him with more new coins than  everyone else
  combined, than to undermine the system and the validity of his own
  wealth.</p>
</blockquote>
 5757: <p>David Schwartz has a good answer. </p>

<p>But to explore a little further, you can roughly think of Bitcoin's proof-of-work system, in the long run, as an election to decide which is the "true" block chain, and hence, which transactions are recognized as having occurred. As it stands, each miner gets voting power in this election proportional to their hash power (one hash, one vote), and the outcome is determined by plurality. So a miner who controls more than half of the hash power can always win the election, and as such is effectively a dictator: she gets to decide which transactions are recognized and which are not. This makes it very easy for her to defraud people, since she can make a transaction, collect the goods, and later declare that the transaction never happened and she still has her money.</p>

<p>Suppose that we could come up with some way to change the election from a plurality to a supermajority (although it isn't immediately clear to me how that could be accomplished). Let's say a 75% supermajority was required. This would have the benefit that an attacker with, say, 70% of the hash power could no longer become a dictator.</p>

<p>But it would have the serious problem that an attacker with only 30% of the hash power could mount a denial of service attack simply by voting in some contrary way. He thus prevents a supermajority from being achieved, no transactions can be confirmed, and the whole currency system comes to a screeching halt.</p>

<p>I suppose this problem is inherent to any political system that uses a supermajority (see for instance the US Senate). Bitcoin is a little  different in that the questions being voted on are not supposed to be controversial: every honest voter should vote the same way. So by design,  the minority should have no voice. And under the current system, they have no voice at all. But with a supermajority, the minority can obstruct the majority, and we don't want that.</p>
 85: <p>The 51% attack is emergent behavior of the system. It's not because there's a "50%" buried somewhere in the protocol that can just be changed to 60% or 75%. Someone with more hashing power than everyone else combined can, given enough time, always build a longer chain than everyone else.</p>
