Majority is not Enough: Bitcoin Mining is Vulnerable

[HorseRider]

This problem as I see it is non-existent. As I've talked about before Mining Block References (MBRs) can tremendously reduce latency which would squash this attack.

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

2) Now it's possible for miners to broadcast their Merkle tree as soon as they start hashing (10 minutes on average before they finish)

3) When they find a valid hash, now they only need to broadcast the block header because the rest of the network has (usually) already received and validated the Merkle tree.

4) Block header propagation is very fast and not dependent of the size of the blocks.

I feel that this post might be the solution to this 33% attack.

As a valid block must be pre-broadcasted in the step 2), earlier than a certain time period, and there is a single time system globally, the Selfish Miner's private block should not be seen as valid if it has no pre-broadcasted Merkle tree.

This precautions essentially makes everyone can announce a block no faster than a certain speed, so that we can constrain the centralization of Bitcoin mining power.

[mpfrank]

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

I thought difficulty related to the number of LEADING zeros, not trailing zeros...

[mpfrank]

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

Here, I compiled v2 of the paper from its TeX source.  There's some error producing the citations but you can still read the text.

https://dl.dropboxusercontent.com/u/3133557/Bitcoin/btcProc.pdf

[justusranvier]

I feel that this post might be the solution to this 33% attack.

I originally thought of it as a way of more efficiently scaling to very large block sizes, but it might have the added effect of making this attack more difficult too.

[HorseRider]

I feel that this post might be the solution to this 33% attack.

I originally thought of it as a way of more efficiently scaling to very large block sizes, but it might have the added effect of making this attack more difficult too.

Yes, a crucial step in this SM attack is to release two blocks one after one immediately . This kind of behavior is not normal and meaningless. If we can stop this kind of behavior, we can prevent the SM attack.

[jl2012]

This problem as I see it is non-existent. As I've talked about before Mining Block References (MBRs) can tremendously reduce latency which would squash this attack.

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

2) Now it's possible for miners to broadcast their Merkle tree as soon as they start hashing (10 minutes on average before they finish)

3) When they find a valid hash, now they only need to broadcast the block header because the rest of the network has (usually) already received and validated the Merkle tree.

4) Block header propagation is very fast and not dependent of the size of the blocks.

I feel that this post might be the solution to this 33% attack.

As a valid block must be pre-broadcasted in the step 2), earlier than a certain time period, and there is a single time system globally, the Selfish Miner's private block should not be seen as valid if it has no pre-broadcasted Merkle tree.

This precautions essentially makes everyone can announce a block no faster than a certain speed, so that we can constrain the centralization of Bitcoin mining power.

Selfish Miner can also pre-broadcast his Merkle tree.

The interesting points of this solution are to minimize the advantage of the low latency connection of the selfish miner.

[justusranvier]

The interesting points of this solution are to minimize the advantage of the low latency connection of the selfish miner.

When the part of a block that must be rapidly broadcast is reduced to less than 100 bytes (regardless of the actual size of the block), propagation times are going to be so low that selfish miner will have a more difficult time responding in time to pull off the attack.

[Peter Todd]

The interesting points of this solution are to minimize the advantage of the low latency connection of the selfish miner.

When the part of a block that must be rapidly broadcast is reduced to less than 100 bytes (regardless of the actual size of the block), propagation times are going to be so low that selfish miner will have a more difficult time responding in time to pull off the attack.

The high-frequency-trading industry begs to differ.

[justusranvier]

The high-frequency-trading industry begs to differ.

The high frequency trading industry operates within a few mile radius, because what they do is sensitive to speed-of-light delays.

That doesn't work as effectively when mining is spread out all over the globe.

[Sukrim]

Will that be always the case? I doubt anyone runs a mining pol server from home - they are probably already quite close to each other in data centers...

Anyways, Merkle Trees are NOT static for 10 minutes, they usually change every time a pool sees a new transaction and decides to add it as well in the current block it is working on. While it might be really nice to broadcast them nevertheless, you might not want that amount of "spam" unless you are another miner.

Mining seems to be more and more to be a game of hash rate AND connectivity towards other players, instead of hash rate alone. If you add in trust (with special high capacity lines between selected pools, signed merkle trees...), you move away from the initial idea that anyone can have a nearly equal chance to take part in mining - further down the road, you will likely first have to deal with the large pools around unless you want a very high orphan rate. They don't even need to attack you, they just need to work in their own best interest and decide that they will host their servers only on Amazon in SF and Ireland, so they have faster connections between each other. Whoever does not take part in this, will be orphaned more often and have worse results, just because of latency and bandwidth.

This is also maybe a bit part of the block size discussion, but it could even happen with block headers in the future after all.

[HorseRider]

I have done some financial analysis to see how fast an attacker can get benefit from this attack. Let's the total network hashing rate is stable. At the beginning of the attack, he will always loss some mining revenue as the diff is fixed and he will lose some blocks when he is trying to broadcasting his double blocks. And his attack will make the growth of blockchain slow.

If the attacker owns 30% of the network hashing power, according to the formula of on the paper ten, he will make the blockchain grows 1.8x slower than if not attacked. Assuming 50% of the block attacker broadcasts accepted,  The revenue speed of the attacker will be influenced. He will loss 40% of his revenue if he had not attack, which is to make other honest miner mine even less and more slower. If the attack continues to next diff period, the attacker start to enjoy the benefit. He will earn more than 9% if he had not attack.


The attack invest 1.8*14=25 days time and 40% of the mining revenue (3600*25*30%*40%=10800 BTC, assuming still 25 btc per block), and he can earn more than 100BTC everyday, which earns investment in 111 days, during which time the whole community finds out his naughty behavior and make a hard-fork.

So, not a very wisdom attacker.

Please check whether my logic is right or wrong by independent calculation. Assuming the total net work hashrate is stable to make analysis simpler. First the attacker has to invest time and losing mining revenue to slow down other people, however the diff is fixed during the time, he is losing money to attack the network. The chain will grow extremely slower during the attack. The attacker suffers with other honest miner together, much longer than 14 days. If he is wealth enough and willing enough, Diff lowers, and he starts to harvest the benefit.  However, the time to make his investment back is very long, and before he can earn back his investment, the community will have already make a hard-fork.

[Desolator]

I just saw this news story on Slashdot and it makes no logical sense to me.  Let's say you have 33% of all mining at your pool. You have a 1 in 3 chance of finding a valid block solution before anyone else. So, you win it and do the exploit they say.  You hold it and secretly work on a 2nd block since blocks are based on the data before them. Now you happen to find a 2nd block that works before anyone else does since you got a "head start" (only probability-wise, no progressively). Finding one valid solution is unlikely but finding two before anyone else finds one is exponentially harder. Then they expect them to find 3? It would happen less than 1% of the time.

Now the other problem is they claim "as soon as another pool is about to find a valid block, you release yours." That's impossible. As soon as another pool broadcasts that it found a solution, the others check it, and it's already too late. Work is non-progressive so you can't tell if another pool is "getting close." So then it'd be a gambling thing. If you find a solution and start working on a second one without telling anyone and claiming your 25 BTC reward, you're more likely to lose to another pool before you find a 2nd valid block value. So you'd be holding it, holding it, holding it, oops you lost it and got 0 BTC.

[Roy Badami]

Their proposed solution, which is offered without extensive analysis, is to relay all blocks, even late ones, and then choose the preferred block in ties at random. Ignoring collateral vulnerabilities which a hasty implementations of forward-all might create, I believe this proposal has a problem in that it creates a selfishness advantage even without any sybil attack at all, so long as the selfish miner has enough hashrate.

But even without their fix, and assuming gamma=0 (i.e. the selfish pool never wins a block propagation race) then if I'm reading it right the authors' result purports to show that a pool with enough hash rate (more than a third of the total hash power) still has a selfishess advantage, which gets quite substantial as the size of the pool grows larger than that.

(Not that I'm particularly supporting their change - just questioning the implication that could be drawn from your post that with the protocol as it stands today it's not possible to gain a selfishness advantage without mounting a sybil attack.)

roy

[cunicula]

This paper is game theory fail.

Fail A
1) The benefit from selfish mining comes from future reductions in difficulty.
2) Until the reduction in difficulty happens, the selfish miner (like other miners) incurs losses.
3) Once difficulty falls, the lower difficulty is open to all. Some other selfish pool could step in and reap all the benefits. Socialized gains; private losses (and socialized losses). Doesn't seem rational unless you have some reason to believe that you can beat pools that copy the strategy. If you try to do the strategy and succeed in lowering difficulty, but ultimately some other pool comes out on top, then you will take losses.

Fail B
Some pools offer PPS. As long as these pools commit to keep up their PPS scheme, miners will migrate to these pools in the event of the attack. This causes the attack to fail. Sure the PPS pools bleed coin in the beginning, but in the end they end up with more miners and the attack gets resolved. If you put this in a economic model with switching costs [i.e. people stay at a pool unless there is a significant benefit from switching], the attack is a probably a net win for the honest PPS pools.
To retain miners, the attacker would need to switch to a PPS system as well. But then he is essentially creating bad luck and insuring people against it simultaneously. This attack is a surefire way to bleed coin. Combine this with Fail A and you can see that the entire paper is fail.

Note: This doesn't mean that bitcoin mining is incentive compatible. It isn't. It's just that this paper has not identified a relevant issue.

[Peter Todd]

The high-frequency-trading industry begs to differ.

The high frequency trading industry operates within a few mile radius, because what they do is sensitive to speed-of-light delays.

That doesn't work as effectively when mining is spread out all over the globe.

Wrong: the high-frequency-trading industry is building dedicated low-latency networks all around the globe, using the minimum distance routes possible to run dedicated oceanic fiber lines for the industry. They're even making use of point-to-point microwave and laser connections because the speed of light in glass fiber is significantly slower than the speed of light in air. They're also making use of oceanic datacenters to reduce latencies when trading between two points; currently only in existing oil rigs and similar facilities, but there are plans for purpose built facilities as well.

I pointed out on IRC how anyone who already had access to such a network would be able to also use it for Bitcoin mining for little additional cost given the low overall bandwidth requirements of mining - implementing the selfish mining protocol and using it for actual mining for profit would be an excellent training exercise for a junior team that needed real world experience, with real but affordable consequences, prior to being set loose on the full-scale trading environment where mistakes can be disastrous.

[gmaxwell]

1) Make the nonce long enough that the extraNonce field is no longer needed in the coinbase transaction.
2) Now it's possible for miners to broadcast their Merkle tree as soon as they start hashing (10 minutes on average before they finish)
3) When they find a valid hash, now they only need to broadcast the block header because the rest of the network has (usually) already received and validated the Merkle tree.
4) Block header propagation is very fast and not dependent of the size of the blocks.

Changing the header is absolutely not required to pre-forward the block. You simply pre-forward it along with a pointer to where the extra nonce goes, and when you solve it you send the resulting timestamp,nonce,extra nonce for substitution— even less data than the header in the most efficient case.  P2Pool already implements block pre-forwarding (though not that aggressively: rather than deny the ability to add transactions, it preforwards transactions and then sends the Merkle tree+header+extranonce) .

However, "10 minutes on average before they finish" isn't right... the whole network produces a block in that time, not each miner. Sending data only once every block per miner, instead of incrementally, would also massively delay transactions— the delays is not something we should encourage. Preforwarding also uses a LOT of extra bandwidth, because each non-successful miner is constantly broadcasting block data too.

In any case, I think making block propagation faster is useful generally— but you don't need to change _anything_ about Bitcoin to do it. You just need to make a little fast-block-daemon which runs its own protocol to relay blocks and that could be run in parallel to the current p2p network.

It's almost a bit orthogonal though, since a better positioned miner still has a _latency_ advantage. Making the data smaller doesn't beat the speed of light.

[gmaxwell]

3) Once difficulty falls, the lower difficulty is open to all.

I believe thats missing the point. The honest miners are being orphaned much more often than the selfish one. The new difficulty isn't "open" to you when you're being disproportionally orphaned.

[Roy Badami]

Would I be right in thinking that this attack is made easier by Bitcoin's rather relaxed approach to timestamps?

What would happen if we were to:

• Use NTP-synchronized local clocks (most cryptographic protocols require this, after all)
• In the event of two new blocks received within, say, 10 seconds, prefer the block with the best timestamp (where a timestamp is better the closer it is the the local clock, except that timestamps more than, say, 2 seconds in the future are always regarded as worse than timestamps that are not)
• (Possibly) Refuse to relay blocks with a timestamp more than 2 seconds in the future

This would make it very hard for the attacker the win the race - essentially it means mining for immediate broadcast gives you an advantage in the race.

roy

ETA: Obviously the 2 and 10 are arbitrary, and not necessarily the best values.  The '2' is a future fuzz value.  Clearly you should never see anything from the future, but you want to make allowance for (small) clock errors, even if you are synchonising clocks (although NTP should synchronize within a few tens of milliseconds at worst).  The 10 second value is related to the network propagation time - it needs to be long enough that you will always have seen both blocks in the attack scenario.  But you don't want to make it too long as during this window someone can mine a new block and force you discard an existing, valid one.

[mmeijeri]

Would incorporating the lexicographical ordering of all timestamps help when choosing between chains?

[gmaxwell]

Would I be right in thinking that this attack is made easier by Bitcoin's rather relaxed approach to timestamps?

No. Timestamps don't come into this at all. (And most suggestions to tighten timestamps result in (usually minor) vulnerabilities)