Majority is not Enough: Bitcoin Mining is Vulnerable

[revans]

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

Not in the slightest.

[1713566915]

1713566915

[1713566915]

1713566915

[Roy Badami]

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)

Ok, in the general case no.... And maybe the third bullet point was ill-advised.

But favouring blocks with an accurate timestamp in the event of a near tie in block arrival time.... surely that makes premining hard - since if you're premining you don't know the time you will want to publish the block.

ETA: It's not a complete fix, of course.  It's an attempt to set gamma close to zero - meaning you can't get any advantage from selfish mining without 33% of the hash rate.

[mmeijeri]

Not in the slightest.

Why not? It penalises those who hold back blocks. I'm not saying this doesn't lead to other problems, but simply saying "not in the slightest" without elaborating isn't very helpful.

[revans]

Not in the slightest.

Why not? It penalises those who hold back blocks. I'm not saying this doesn't lead to other problems, but simply saying "not in the slightest" without elaborating isn't very helpful.

1. You solve a problem and create several others which are significantly more intractable. Bad engineering.

2. What happens if the client issued by Bitcoin's defacto central bank is supplanted by a War Mining client?

[cunicula]

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.

Harm done to others is irrelevant. Th attacker loses blocks too. They forgo blocks now to invest in lower difficulty later.

This is a dynamic game, but the authors analyze it as a static game. They lack a solid background in game theory. Otherwise they would not have made such an elementary mistake.

Whatever though. Continue to get yourselves worked up about an erroneous result.

[mmeijeri]

1. You solve a problem and create several others which are significantly more intractable. Bad engineering.

What other problems would it create and why are they more intractable?

[justusranvier]

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.

I have a reply that I'll as to the thread as son as the electricity comes back on and I'm not limited to my phone.

[revans]

1. You solve a problem and create several others which are significantly more intractable. Bad engineering.

What other problems would it create and why are they more intractable?

Because you'd harm a lot of people not War Mining, and this only works if the Bitcoin central bank's client remains the standard.

[socrates1024]

I wrote the following email to someone asking about this paper, and I feel like publishing it in this thread. I don't have any insight to add about the substance of the paper itself, but I want to suggest how to put it in context. This paper is far from unique in pointing out ways that Bitcoin is not incentive compatible. We DO need to try to find and fix these economic glitches - they are REAL problems - but they also aren't immediate life-or-death urgent, because the network at the moment consists of a large number of well meaning and responsive participants. We can expect that more problems like these are coming. The larger and more mainstream Bitcoin's userbase gets, the more important it will be to design incentives to predict and steer participation.

I was annoyed at first about the sensationalistic headlines, but I've gotten over it. We're used to these by now, from the press and everyone else. A tweet from the author convinced me that his interests are in the right place: ":-) but we're all good guys. The BTC community deserves a strong, robust currency. Identifying potential attacks is critical". This is true, and we really need more distributed systems experts and theoreticians working at this. I think the net effect of this event is that Bitcoin becomes more popular/attractive as an academic research topic, and that can only help.

Despite the overhyped headline, this paper is important. It's part of a (long past due) movement towards modeling "rational participation" in Bitcoin. We are (surprisingly?) in a blind spot here as far as theoretical foundations go (the 30+ years of research in distributed systems, game theory, etc., have not looked at anything resembling Bitcoin). We do not yet have a sound way to argue that "Bitcoin (or X variant thereof) surely works," nor any impossibility results saying "nothing resembling Bitcoin can ever work."
 
Main points:
- Bitcoin is clearly *intended* to be incentive-compatible and encourage correct behavior. However the whitepaper only gives a proof for the "51% honest" model, which is unrealistic/trivial (if we just assume everyone's honest, there's no need for rewards in the first place). Even in this easy model, Bitcoin is novel among byzantine consensus protocols. Academics *should* have worked on this twenty years ago, but missed it! (except for this 2005 tech report)
- Practically speaking, we still seem to have a while to figure this stuff out before any systemic economic collapse will manifest. Even the mining pools still run bitcoind, not RationalMiner software. For the time being, majority honest is a reasonable approximation.
- Even if a 51% majority has limited ability to profit or attack, a systematic trend towards enabling 51% attacks would be a design flaw and existential threat. So we really need to find and fix things like this.
 
This paper fits neatly into a class of papers/posts that point out a particular way in which Bitcoin is not incentive-compatible (to call it an *attack* is just cyberhype), yet a simple fix (typically just to the messaging layer) is often at hand.
- Bitcoin and Red Balloons. There's no incentive for peers to relay transactions. Solution: bribe your peer conditional on the transaction getting accepted, now it's their problem too.
- This paper: If a mining pool is confident in its ability to detect and out-propagate competing blocks, then it can profit by witholding blocks until the last minute, making everyone else waste work. Solution: relay faster so no peer can get this advantage, or use random tie-breaking so this attack can't be pulled off consistently (the following two examples are me plugging my own posts). Regardless of propagation, a miner with more than 33% of the network's hashpower can profit disproportionately by witholding one block at a time. [edited, due to author pointing out this was oversimplified].
- https://gist.github.com/amiller/cf9af3fbc23a629d3084 An anomalously large single transaction fee would encourage miners to fight over the previous block, rather than building on each other's work. Solution: remove the 100-block coinbase maturity rule, which actually prevents a simple cooperative equilibrium where you take a cut of the huge fee for yourself and leave the rest for the next miners to fight over.
- https://bitcointalk.org/index.php?topic=309073.0 Natural economies of scale mean that "outsourced hosted mining" will be more cost effective and might drive out other participants, leading to more centralized control of resources, susceptible to coercion etc. Solution: a modified puzzle using (efficient) zero-knowledge proofs would make hosted mining (and mining pools, incidentally) impractical.
 
There are other similar "attacks" along the lines of "this may be a problem when people eventually run RationalMiner rather than HonestSatoshiReferenceClient", but for which the solutions are less obvious...
- Feather forking: https://bitcointalk.org/index.php?topic=312668.0  a small cartel of miners that want to enforce a transaction black-list could easily make it so that rational participants indifferent to the blacklist would rather appease the cartel than resist it. Possible solution: Adam Back is thinking very hard about how to make miners verify the correctness of transactions without learning anything else about them.
- Kroll. et al: Following *any* of the rules is at best a *focal point*, and slight rule tweaks like inflating the 21 million limit (just by a little bit) are probably a lot more plausible and easier to pull off than most people think. Possible solution: no idea
 
But we're still just scratching the surface of incentive-alignment glitches like this. Bitcoin will overcome the problems with easy fixes. I hope (but am skeptical) that if there's a bigger fix required, we can work it out and adopt it without waiting until it's too late and having to restart from scratch.
 
Above all, I wish we had a strong theoretical model we could use to knock out entire classes of problems rather than pointing them out and patching them one at a time. By analogy, the academic cryptography community did such a great job of moving from ad hoc ciphers to "provable security" that the mainstream security mantra is "don't roll your own crypto" unless you've proved a theorem first. Maybe someday they'll say the same thing about rolling your own incentive-consensus protocols. But the work hasn't been done yet, and we're currently still in the dark ages.

[acoindr]

...
Low latency connection itself is expensive, and we can nullify its advantage by relaying unverified block headers. People will always assume a block header is valid unless it is proven otherwise, and always mine on top of the first seen header. (I think creating invalid block header is very expensive and no one is trying to do this. Any stats for this?)
...

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.

Broadcasting block headers either before or after the final set of transactions doesn't help because miners are never sure what block to mine on top of until they know the winning block. In the case of the header arriving prior to transactions, now trolling the network is easy for anyone with any size hash capacity but no worry about block reward. In the case of the header arriving after transaction information, as gmaxwell points out, large amounts of useless data eat up your bandwidth until you learn the correct header.

This issue has made me think through my concept for MBRs and I've reached interesting conclusions which I'll post about when I get time.

[gmaxwell]

Whatever though. Continue to get yourselves worked up about an erroneous result.

what part of my post indicated that I was "worked up"?

[cunicula]

Whatever though. Continue to get yourselves worked up about an erroneous result.

what part of my post indicated that I was "worked up"?

Wasn't referring to you specifically. But clearly some people somewhere are worked up about some paper that
a) isn't correct (uses improper methodology)
b) isn't novel
c) wouldn't be noteworthy even if it were correct and novel. (game theory indicates many ways that bitcoin is not incentive compatible, it is not clear why we should care if one more way is added to the list)

Maybe I'm disappointed that you were not adequately dismissive. Bitcoin has real issues. This is not one of them. These jackasses do not deserve the time of day.

[User705]

So this is more of a miners issue right?  How are orphan block rewards handled now?  What I mean is if I solve a block and get the reward and go gamble it at satoshi dice immediately does this "attack" somehow nullify that block reward afterwards and basically I succeeded at a double spend?  Or the block never hits the blockchain and the "attack" is designed for me to waste my hashing power?

[briguy37]

The paper does not consider multiple selfish mining pools fighting against one another.  For example, in Section 4.4, they say:

  "Note that the pool is only at risk when it holds exactly one block secret"

This is not true. 

For example, Selfish pool A has 2 private blocks and Selfish pool B has 3 private blocks.  When Honest pool C finds a block and publishes it, A publishes their 2 "safe" blocks, only to lose them when B publishes their 3 private blocks. 

Furthermore, if everybody was selfish then blocks would never get published.  When an honest block eventually did get published, there would be a mass publish event of all private blockchains where all but the longest selfish block-chain(s) would be worthless.  If there was a tie there would be a fork-fight to determine whose blocks were eventually kept. 

Long story short, if you DO decide to be a selfish pool, be certain that you are the biggest selfish pool in the world.  Furthermore, even if you are the biggest, know that the smaller selfish pools will cut into your "safe" profits every time they get more private blocks than you do.

[Roy Badami]

The paper does not consider multiple selfish mining pools fighting against one another.

They do say, in section 3.2:

For simplicity, and without loss of generality, we assume that miners are divided into two groups, a colluding minority pool that follows the selfish mining strategy, and a majority that follows the honest mining strategy (others).

It's not immediately obvious to me how such an analysis could be without loss of generality, though.

roy

[Luke-Jr]

It's not possible for pools to do this without miner cooperation - for example, by them using the stratum protocol. As long as miners are taking advantage of the GBT protocol, this attack is not possible since the miner finding the block will announce it to the network themselves.

For BFGMiner, you need to configure it to failover to solo mining:

Code:

bfgminer ...put your real GBT-based pools first... -o http://localhost:8332#allblocks -u username -p password

[revans]

It's not possible for pools to do this without miner cooperation - for example, by them using the stratum protocol. As long as miners are taking advantage of the GBT protocol, this attack is not possible since the miner finding the block will announce it to the network themselves.

Which is fine so long as Bitcoin's central bank's client remains the defacto standard. As other mining strategies are discovered there will be ore and more clients available running forked mining code.

[Luke-Jr]

It's not possible for pools to do this without miner cooperation - for example, by them using the stratum protocol. As long as miners are taking advantage of the GBT protocol, this attack is not possible since the miner finding the block will announce it to the network themselves.

Which is fine so long as Bitcoin's central bank's client remains the defacto standard. As other mining strategies are discovered there will be ore and more clients available running forked mining code.

Huh? You don't need any forked mining code for this...

[gmaxwell]

Which is fine so long as Bitcoin's central bank's client

Huh?

[revans]

Which is fine so long as Bitcoin's central bank's client

Huh?

You are surely aware that the organisation that controls (writes and maintains) the Bitcoin client used by the majority basically controls Bitcoin.