Take the 2-minute tour ×
Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It's 100% free, no registration required.

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?

share|improve this question
1  
Can you explain in more detail how the modified protocol would work? The 51% attack comes from the principle that the longest branch of the block chain is considered the valid branch. I don't see how you would amend that to get a different number. –  Nate Eldredge Jun 16 at 16:07
    
It probably helps to understand what the attack does, and this answer seems to explain it well: bitcoin.stackexchange.com/a/660/18253 –  Brendan Long Jun 16 at 21:54

4 Answers 4

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.

share|improve this answer
3  
Note that although people often talk about '51% attacks', there is no magic threshold at 50%. You could do a 51% attack with 49% of the hashing power, it would just be slightly harder. –  jwg Jun 17 at 11:40
4  
@jwg Well, the 50% point is important. With over 50% hash power, given enough time you are guaranteed to create a blockchain longer than anyone else. Of cause, as you point out, it is still possible with sheer luck to create a longer chain with less than 50% hash power, just not probable. –  Svante Jun 17 at 13:02
2  
@jwg What matters here is the probability that an attacker will eventually exceed the main chain if he starts from $N$ blocks back. There is a 'magic threshold' at 50% in the sense that at 50% hashpower, this probability is 100% regardless of $N$. You're correct that for every $N$, the probability approaches 100% as hashpower approaches 50%, so an attacker with even 40% of hashpower is extremely dangerous. But below 50%, the probability drops off exponentially with $N$, so in the presence of a sub-50%-attacker you can be safe by simply requiring many (perhaps tens of thousands) confirmations. –  Andrew Poelstra Jun 17 at 15:07
2  
@jwg: At the level of mathematics, your statement is not correct. In the long run, an attacker with 51% of the hash power is overwhelmingly more likely to create the longest chain than an attacker with 49%. Indeed, given enough time, the 51% attacker is nearly guaranteed to get the longest chain, and the 49% attacker is nearly guaranteed not to. This is the law of large numbers, a fundamental theorem of probability. –  Nate Eldredge Jun 17 at 15:44
1  
@jwg: I'm afraid I don't understand your point, then. If I have 51% of the hash power, I can (eventually) create more blocks than anyone else, and if I so choose, I can link them all to each other so they are all consecutive. Eventually I have a chain, consisting (from whatever I took as my starting height) entirely of my own blocks, longer than any other chain. Once I release it, people can tack their own blocks onto the end if they want, but if I want, I can eventually supersede their blocks with a longer chain of my own. –  Nate Eldredge Jun 17 at 16:25

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.

share|improve this answer
    
That statement by Satoshi is at best dubious. It pre-supposes that an attacker is only interested in accumulation (rather than say, vandalism), and that having a large proportion of newly mined blocks is comparably desirable to having a large proportion of all coin in existence. As already existing coin builds up and mining rewards decrease, this gets further and further from the truth. –  jwg Jun 17 at 11:42

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.

share|improve this answer
1  
It's not clear to me if this analogy really works for Bitcoin. The "withholding votes" in particular doesn't make much sense, but I guess that follows from the fact that "requiring a supermajority" doesn't make sense in Bitcoin either. –  Brendan Long Jun 16 at 21:32
1  
@BrendanLong: I may not have phrased it very well. I meant that the attacker can refuse to vote for the "right" chain (by instead voting for some "wrong" chain). Then no chain gets a supermajority and the system quits working. I agree that a system where this actually made sense would look rather different from Bitcoin. –  Nate Eldredge Jun 16 at 21:37
    
Wow, you are an excellent teacher. –  David Jun 17 at 15:06

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:

  1. You can withdraw all your computing power from the uncorrupted blockchain, and dedicate it to your attack.
  2. 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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.