Majority is not Enough: Bitcoin Mining is Vulnerable

[chriswilmer]

Hey guys,

Could one of you be so nice as to test my understanding of a nuance of the Selfish-Miner attack?

I THINK I understand how, if information about blocks isn't stifled, then the selfish mining strategy wouldn't work (because you couldn't reveal your privately found block quickly enough to orphan the block found by honest miners). However, and I am just asking out of intellectual curiosity... if you have already found TWO blocks privately (for whatever reason)... then it would ALWAYS be better to continue mining in private, right? Because as soon as the network finds one block, you can reveal your two... and if you find three, then you can keep going and only reveal your hand when the network finds n-1 blocks. Am I thinking correctly?

[dree12]

What you mean is the most difficulty, which is not the same as the numerical block hash.  The natural numbers less than 2^256 are a total order, but difficulty is a partial order on block hashes.

What are you talking about?

You deleted my example; that may be the source of your confusion…

Here, look at it in fixed-width font, with some emphasis:


  0xffffffffffffffffffffffffffff0000
  0x000000000000000000000000000f0000


See how they have the same number of trailing zeroes?  For any target you choose, either both will match it or neither will.  Yet these two numbers are not equal.  Therefore difficulty is creates a partial order on block hashes.  On the other hand "less than" is a total order on block hashes.

Your example would be easier to understand if you wrote it in big endian, but now I see your point.

[Peter Todd]

We only need a majority of miners to change. Any fix would be completely transparent to users.

Maybe, maybe not.

One of the fixes I'm looking into would require a hard-fork, but it may prove to be a more effective fix than any solution.

We'll see.

[jl2012]

1) Make the nonce long enough that the extraNonce field is no longer needed in the coinbase transaction.

All ASIC will be broken so basically no one will follow this hardfork.

This could be accomplished by the aux-block softfork I proposed earlier: https://bitcointalk.org/index.php?topic=283746.0

[justusranvier]

All ASIC will be broken so basically no one will follow this hardfork.

All ASICs get replaced after a few months anyway, so it would be no problem to define it 6-12 months in the future before implementing it.

[jl2012]

All ASIC will be broken so basically no one will follow this hardfork.

All ASICs get replaced after a few months anyway, so it would be no problem to define it 6-12 months in the future before implementing it.

The arm-race won't last indefinitely and it will eventually slow down. I don't see any chance to change the format of the 80bytes header unless absolutely needed, e.g. SHA256 weakened or timestamp overflow in the far future

[dree12]

All ASIC will be broken so basically no one will follow this hardfork.

All ASICs get replaced after a few months anyway, so it would be no problem to define it 6-12 months in the future before implementing it.

The arm-race won't last indefinitely and it will eventually slow down. I don't see any chance to change the format of the 80bytes header unless absolutely needed, e.g. SHA256 weakened or timestamp overflow in the far future

A better solution is to allow both types of blocks for the next year, then force the new type of block. No ASIC is going to last a year.

[niniyo]

if you have already found TWO blocks privately (for whatever reason)... then it would ALWAYS be better to continue mining in private, right? Because as soon as the network finds one block, you can reveal your two... and if you find three, then you can keep going and only reveal your hand when the network finds n-1 blocks. Am I thinking correctly?

That's right, which is included in the paper.  The problem of course is that to get 2 blocks ahead you have to first withhold your first block, and if you are a minority miner then you're going to get orphaned far more often than you would find 2 blocks in a row.  So the result is you end up losing a huge majority of your revenue trying to hit these streaks, and since you rarely hit these streaks, it has minimal impact on the rest of the miners.

The selfish strategy just simply does not work unless you can win these orphan contests nearly every time.  Even if the selfish miner becomes amazingly connected and has super low latency to many nodes in the network, what's to stop another miner doing the same?  So its a big stretch to just assume that a selfish miner can always win these races.  It needs to be demonstrated in practice for this to be a serious threat.

[Enochian]

Umm, well apart from the fact that the cost for any rogue government or bank to bring down Bitcoin has now decreased dramatically, I think you are naive to think that selfish mining won't become the norm.

Rogue governments and banks have deep pockets.  They could simply pay a small premium to their pool members, and get people to join their pool that way.  They hardly need to use the complicated strategy disclosed in the paper to improve their payout.

This probably won't happen.  If it did, it wouldn't happen overnight, and the developers would have ample time to make some new rules about maximum pool size and forking and push them out to everyone, before the evil pool reached any sort of critical mass.

So 99.9% chance the paper is forgotten in a week, and no one cares enough to implement it.  0.1% chance someone decides to run with it, it is instantly noticed, sticks out like a sore thumb, and in the unlikely event large numbers of people start climbing on, we probably have months to make a tweek before it becomes any sort of problem.

The blockchain fork between different versions of the client was a 100 times worse malfunction than this thing ever could be, and that was dealt with successfully in short order.

[gmaxwell]

I think this assumption of theirs is the flaw.

Sorry for confusing you there. Obviously any node prefers the highest total work— the protocol isn't convergent otherwise. This is about blocks which have equal work. Nodes prefer the first heard among those with otherwise equal work. The obvious alternative policies create issues like... incentives for large miners to delay their announcements.

[justusranvier]

Nodes prefer the first heard among those with otherwise equal work.

How often does it happen that two miners simultaneously find a block with exactly equal work values?

[dree12]

Nodes prefer the first heard among those with otherwise equal work.

How often does it happen that two miners simultaneously find a block with exactly equal work values?

The issue here is the definition of work. Work is based on the target, and not based on the block hash itself. It is a statistical fallacy to claim that a block with a lower hash required more work than another block mined with the same target.

When two blocks have the same target, the earliest-received is preferred.

[oakpacific]

The problem with this paper, I think, is that it uses a much stronger assumption than Satoshi's, that it's a strictly one malicious miner vs a bunch of honest/profit maximize miners scenario, implying the malicious miner miraculously knows every other miner to be honest, profit-maximizing, yet they know hardly anything about him, while in Satoshi's assumption, you basically mine against a number of peers which are unknown to you.

This makes a big difference from the game theory perspective: how can the malicious miner be sure that no one else is going to copy his strategy, forming a even bigger mining coalition, and force him to become his own strategy's victim and lose everything? He will have to think hard to devise a way to guarantee his success, so that nobody can defeat him in his own game, and work out the amount of hashing power he needs to acquire for such guarantee, after several days of work, he is finally done! And congratulations, he has just rediscovered the old and true "51% attack".

[overc]

Ok, what about that problem:

Some guy with deep pocket (government?) establish a very stable mining pool with the best
protection agaisnt ddos and with the lowest network latency possible and welcomes everybody to mine with 0% (or even negative) fee.

So, eventually he will get 51% of hashing power, will not he?
And he even do not need to exploit the problem discussed in this thread, he can just be the honest mining pool.

[User705]

This is economically irrelevant to the total bitcoin and that's why markets didn't seem to care.  No extra bitcoins are created here.  It's more of an issue of one group trying to "steal" mining revenue.  But they already do that.  That's what the competition in solving and publishing blocks is all about.  If a pool holds back a solved block isn't it true that individual miners can see that they found a solution but it hasn't been published?  Couldn't they then hop to another pool and claim the reward there as well or perhaps try to publish directly themselves solo?  Basically I find out this "evil" pool exists and game it.  I mine in pps format and if I find a block I know this pool will hold it back and not publish so then I simply grab that solution and try to publish elsewhere and if I succeed then don't I get paid twice?

[trout]

a slightly different question:

how would we detect if such an attack is taking place?

As far as I understand, the attacking miner would have a slightly higher
ratio of blocks broadcast in pairs. That is, normally if his block rate  is alpha
then  rate for pairs should be alpha^2,  but if he is running the attack this value would
be slightly but significantly higher, and depends on gamma (how successful he is with
his sybil attack). It'd take a long time to detect though

[BitThink]

Ok, what about that problem:

Some guy with deep pocket (government?) establish a very stable mining pool with the best
protection agaisnt ddos and with the lowest network latency possible and welcomes everybody to mine with 0% (or even negative) fee.

So, eventually he will get 51% of hashing power, will not he?
And he even do not need to exploit the problem discussed in this thread, he can just be the honest mining pool.

It only becomes a problem if this pool owner (eg. some governments) wants to destroy the bitcoin. Otherwise, they will voluntarily reduce the hash rate (just as BTCGuild already did) to avoid being close to 51%. They have to do this, because their business is based on the validity of BTC and once their hash rate is close to 51%, the market will crash and so does their business.

[BitThink]

a slightly different question:

how would we detect if such an attack is taking place?

As far as I understand, the attacking miner would have a slightly higher
ratio of blocks broadcast in pairs. That is, normally if his block rate  is alpha
then  rate for pairs should be alpha^2,  but if he is running the attack this value would
be slightly but significantly higher, and depends on gamma (how successful he is with
his sybil attack). It'd take a long time to detect though

If many (or even most) blocks mined by this pool have corresponding orphan blocks, then we have enough reason to put it in the alert list.

[Skybuck]

Umm WTF are you talking about? Try reading it again, only this time whilst not high on Bitcrack. Maths + human nature= a selfish mining future and the end of Cultcoin. In a sense the popularity you so longed Bitcoin to have has destroyed it as peer review is demonstrating just how architecturally boken Bitcoin is.

Do you have a specific criticism?

You are welcome to set up a selfish mining rig and prove me wrong.  Unless you have sufficient hash power to be mining blocks very frequently, no one is even going to notice you exist.

This is an academic exercise with very tiny practical implications, and in any case, a very small threat on the long list of threats.

One problem with this logic of yours is that it does not include the possibility of an entire existing mining pool to switch software over to the new selfish-mining algorithm.

This will quickly change the bitcoin game

However perhaps this is mosterd after the meal, perhaps it already happened a few years ago. What ever happened to deepbit mining pool ? Did it merge or did it disappear ? or rename ? Or was it eclisped by other mining pools, perhaps people left that pool and flocked to others

[Skybuck]

Currently the first block that arrives is picked by miners so the "secretives" have incencitive to "delay public blocks", an incentive to listen in on other mining pools "detect early public block announcement to quick react to it" and to try and inject/publish their secretive block as fast as possible towards other miners that have not yet received a new block.

Your analysis is pretty incomplete. Their success at winning that "fast as possible" race, along with their total hashrate, is essential. Otherwise a delay is a pure loss.

It's indeed a bit more complex than the article (who's link is now broken, apperently the pdf converter crashed... update: v1 seems to still be available, v1 is from 1 november, v2 seems to have crashed, v2 is from 4 november) seems to make out, at least from the algorithm, but later it examines the revenues at page 9, which is basically what my posting below is about, however their algorithm does not include my refinement below, I don't think their algorithm includes spreading/delaying techniques, sometimes sabotaging the enemy or sometimes helping the enemy when it's beneficial, ofcourse this needs to be formulated in code/extra lines but it shouldn't be too hard, my posting examines the friction between calculation speed versus spread speed and could help to make more clear decisions of what to do in certain cases:

Let's denote the attackers as the secretives: S
Let's denote the public as the publics: P

Working on blocks now has a few possibilities:

PSS
PSP
PPS
PPP

Both start working on the previous public block indicated by the first P.

PS   (Group S works on next block S based on block P)
PP   (Group P works on next block P based on block P)

Both find their block at the same time.

S wants to keep it secret to continue work on the next S.
P wants to publish their P.

Here it's clear that S wants to delay P as long as possible, so here a delay of the enemy/P is beneficial towards S, you agree with this so far ?

Now suppose P was late.

(the first P of the three letters is now ignored so:
SS
SP
PS
PP
are the possibilities)

S can now comfortable work on their next S.
P catches up and publishes their first P.

S now has to publish their first S and does so and hopes to win from P. Again here S has a incentive/benefit to delaying P.

However let's assume S is not too successfull at delaying the spread of block P.

And now both blocks arrive at miners, both blocks are now candidates to be included into the block chain.

Now a situation occurs where S has a benefit to help P spread their next block P as fast as possible but only if next block P was based/calculated on block S.

Otherwise again S has a benefit at delaying next block P. If next block P was not based on block S then block S loses their block and instead block P becomes the main chain followed by next block P.

Therefore for this selfish mining algorithm to work well blocks have to be analyzed.

Sometimes it's beneficial for S to sabotage/delay P and sometimes it's beneficial for S to help/speed up spread of P.

However this assumes that S cannot quickly enough calculate next block S, if they instead could then it would still not be wise to help P.

However it's more likely that next block P will spread before they can calculate next block S based on previous block S so it's seems clear to take the money and run... be statisfied with what you got so far.

However it's clear that there is some friction here.

Calculation speed of next block S based on block S versus spread of next block P based on block S.

S now has a choice:

1. Delay spread of next block P based on block S and thereby undermining it's own block S in the hopes of calculating next block S based on block S itself and thus getting a double reward.

versus

2. Acceptance of spread of next block P based on block S and thereby at least embedding block S into the main blockchain and throwing away calculations on next block S and starting over based on next block P and thus getting a single reward.

As long as calculation speed of next block S based on block S is slower than spread of next block P based on block S it seems to make sense to choose option 2.

In other words, the algorithm will need to be adaptive and determine if the spreading block of the opponent was based on a previous block from S or a previous block from P and take a decision on that and do what it thinks is best based on speeds, calculation speed versus spreading speed. Spreading speed seems to be in a few seconds, while calculation speed can be 10 minutes.

However other factors may influence this, denial of service attacks, network attacks, crashes etc.

(Also this posting only looks at S versus P, it does not include S versus S versus P )