Majority is not Enough: Bitcoin Mining is Vulnerable

[solex]

Google news is showing a number of articles which amount to FUD, and are multiplying like gremlins.
Perhaps the Bitcoin Foundation should put up a short rebuttal / press release encapsulating some of the information in this thread. While the Eyal paper has some merit - it is certainly not a situation of "'Bitcoin Is Broken' And Could Collapse"

Bitcoin flaw could let group take control of currency
CNNMoney - ‎3 hours ago‎
The flaw is due to the nature of how bitcoins are created -- people "mine" them by solving a complex puzzle with their computers. If used correctly, the system is set up so that someone guesses correctly every 10 minutes, and the winner gets 25 bitcoins.
http://money.cnn.com/2013/11/04/technology/bitcoin-flaw/

Bitcoin Researchers: You Can Game the System
Mashable - ‎10 hours ago‎
Computer science researchers at Cornell University claim to have found a way to subvert the system driving production of the digital currency Bitcoin. The researchers call their technique “selfish mining,” through which individuals or groups of Bitcoin miners ...
http://mashable.com/2013/11/04/bitcoin-cornell-researchers/

Researchers Say 'Bitcoin Is Broken' And Could Collapse
Yahoo!7 News - ‎1 hour ago‎
The problem is with how people "mine" bitcoins. Mining is how bitcoins are created. Most people don't mine bitcoins anymore. They buy them or take them as payment. But some people are in the business of mining coins with special bitcoin-mining computers ...
http://au.finance.yahoo.com/news/researchers-bitcoin-broken-could-collapse-014448102.html

Cornell Researchers Found a Way to Game Bitcoin
RYOT - ‎2 hours ago‎
It's entirely likely and understandable, despite our better efforts to bombard you with Bitcoin stories recently, that you still don't know what Bitcoin is. (To be honest, 92 articles about it later we still don't fully grasp it.) But all you need to know is that it's digital ...
Bitcoin open to takeover, researchers discover with new algorithm
http://www.ryot.org/cornell-researchers-claim-able-game-bitcoin/456361

Science Daily (press release) - ‎58 minutes ago‎
Nov. 4, 2013 — A major flaw that has gone unrealized until now leaves the $1.5 billion Bitcoin market open to manipulation and a potential takeover, according to a new study by two Cornell University computer scientists.
http://www.sciencedaily.com/releases/2013/11/131104112234.htm

[1714671268]

1714671268

[1714671268]

1714671268

[revans]

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.

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. For all the phoney idealism, allI see and hear from Bitcoin cultists is a desire to get rich quick, for easy money made riding a speculative bubble. All profess their sincere belief in Bitcoin as a currency, and yet strangely that nasty old state fiat they claim to hate is what they can;t wait to get their hands on.

In other words, your community is comprised of speculators and get rick quick wannabes, it is laughably naive to believe they won' game the system, if only because so many others will to refraim would be hugely disadvantageous.

[Peter Todd]

your blocks ends up increasing the risk that you get orphaned since nodes prefer the first block they heard.

I think this assumption of theirs is the flaw.

Successful pools do not build on the first block they hear; they build on the most difficult block they hear.

You're wrong: nobody does that and doing so puts the miner at a disadvantage because the block you hear about first is the one most likely to have propagated to a majority of the network. It is however a possible way to mitigate this attack and in an email to bitcoin-development one of the authors specifically stated they thought of that idea and left it out of their paper due to space constraints:

Here is a solution we did not put in the paper due to space constraints
that should alleviate your concern:

Instead of locally choosing a block at random, have a deterministic
pseudo-random mechanism for choosing between competing chains. E.g., take
the one whose last block hash is smaller. This way all miners choose the
same chain, and the guarantees of our solution hold.

I'm working on analyzing a stronger version of this solution that would make the choice to mine the smaller block hash be short-term economically rational for miners.

[justusranvier]

"Difficulty" and "target" are actual technical terms with precise definitions in the block protocol.

That is true.

However, since virtually everyone says "difficulty" when they really mean "target", and since the wiki uses "work" to refer to difficulty, using the most common convention will prevent a lot of confusion.

[revans]

Google news is showing a number of articles which amount to FUD, which are multiplying like gremlins.
Perhaps the Bitcoin Foundation should put up a short rebuttal / press release encapsulating some of the information in this thread. While the Eyal paper has some merit - it is certainly not a situation of "'Bitcoin Is Broken' And Could Collapse"

Bitcoin flaw could let group take control of currency
CNNMoney - ‎3 hours ago‎
The flaw is due to the nature of how bitcoins are created -- people "mine" them by solving a complex puzzle with their computers. If used correctly, the system is set up so that someone guesses correctly every 10 minutes, and the winner gets 25 bitcoins.
http://money.cnn.com/2013/11/04/technology/bitcoin-flaw/

Bitcoin Researchers: You Can Game the System
Mashable - ‎10 hours ago‎
Computer science researchers at Cornell University claim to have found a way to subvert the system driving production of the digital currency Bitcoin. The researchers call their technique “selfish mining,” through which individuals or groups of Bitcoin miners ...
http://mashable.com/2013/11/04/bitcoin-cornell-researchers/

Researchers Say 'Bitcoin Is Broken' And Could Collapse
Yahoo!7 News - ‎1 hour ago‎
The problem is with how people "mine" bitcoins. Mining is how bitcoins are created. Most people don't mine bitcoins anymore. They buy them or take them as payment. But some people are in the business of mining coins with special bitcoin-mining computers ...
http://au.finance.yahoo.com/news/researchers-bitcoin-broken-could-collapse-014448102.html

Cornell Researchers Found a Way to Game Bitcoin
RYOT - ‎2 hours ago‎
It's entirely likely and understandable, despite our better efforts to bombard you with Bitcoin stories recently, that you still don't know what Bitcoin is. (To be honest, 92 articles about it later we still don't fully grasp it.) But all you need to know is that it's digital ...
Bitcoin open to takeover, researchers discover with new algorithm
http://www.ryot.org/cornell-researchers-claim-able-game-bitcoin/456361

Science Daily (press release) - ‎58 minutes ago‎
Nov. 4, 2013 — A major flaw that has gone unrealized until now leaves the $1.5 billion Bitcoin market open to manipulation and a potential takeover, according to a new study by two Cornell University computer scientists.
http://www.sciencedaily.com/releases/2013/11/131104112234.htm

That is an accurate headline. Bitcoin is fundamentally broken per these findings, and significant exploitation of these findings (which given human nature and financial incentives is inevitable) Bitcoin will collapse. Bitcoiners can issue all the press releases attempting to debunk this reality as they like, it won't change a damn thing. The only question is how quickly this exploitation happens, and how rapidly it poisons the whole network


Fun times ahead.

[eldentyrell]

This is a statistical fallacy. Two blocks will always be equally difficult when they were mined with the same target.

This is a definitional fallacy.

What you mean to say is that clients prefer to choose the block with the least block hash.

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.

For any target, blocks with these two hashes both meet that target.  Therefore two blocks with these two hashes are of equal difficulty even though the first one has the numerically least block hash:

Code:

  0xffffffffffffffffffff0000
  0x000000000000000000000000000f0000

[Enochian]

That is an accurate headline. Bitcoin is fundamentally broken per these findings, and significant exploitation of these findings (which given human nature and financial incentives is inevitable) Bitcoin will collapse. Bitcoiners can issue all the press releases attempting to debunk this reality as they like, it won't change a damn thing. The only question is how quickly this exploitation happens, and how rapidly it poisons the whole network

Fun times ahead.

You can't seriously think that a mining pool waiting to announce its blocks until they invalidate the maximum amount of other peoples' computation is going to significantly perturb the network unless that mining pool already has a non-trivial fraction of the total hashrate.

The network is hardly in any danger of being poisoned.

 

[justusranvier]

You can't seriously think

It's just trolling and market manipulation.

[Peter Todd]

That is an accurate headline. Bitcoin is fundamentally broken per these findings, and significant exploitation of these findings (which given human nature and financial incentives is inevitable) Bitcoin will collapse. Bitcoiners can issue all the press releases attempting to debunk this reality as they like, it won't change a damn thing. The only question is how quickly this exploitation happens, and how rapidly it poisons the whole network

Your view assumes Bitcoin is a static thing; Bitcoin can be changed in response to this attack

What the Bitcoin Foundation should be doing is releasing a press release welcoming the Cornell researchers competent analysis of the flaws in the system, while pointing out that one of the strengths of Bitcoin is that flaws can be corrected if a clear majority of Bitcoin users choose to change the software they run.

[eldentyrell]

You're wrong: nobody does that

I think you mean you don't do that.

E.g., take
the one whose last block hash is smaller. This way all miners choose the
same chain, and the guarantees of our solution hold.

This is not a new idea at all.  As far as public postings, it's been on this page on the bitcoin wiki for at least six months, and there was definitely a mention of it on bitcoin-dev about a year ago (I will post the reference when I find it).  And, as I've mentioned, it's pervasive in the modified clients used by large mining operations, although those are not public so you're welcome to shout "liar liar pants on fire" all you like and I won't get upset



I think the people who wrote this paper took Satoshi's original whitepaper too literally:

Nodes always consider the longest chain to be the correct one and will keep working on extending it. If two nodes broadcast different versions of the next block simultaneously, some nodes may receive one or the other first. In that case, they work on the first one they received, but save the other branch in case it becomes longer. The tie will be broken when the next proof- of-work is found and one branch becomes longer; the nodes that were working on the other branch will then switch to the longer one.

Mining strategy has evolved and adapted, as it must in any incentive-driven system.  For example, Satoshi's whitepaper predicted that transaction fees would be a meaningful incentive, and it's pretty obvious it hasn't turned out that way.

[dree12]

This is a statistical fallacy. Two blocks will always be equally difficult when they were mined with the same target.

This is a definitional fallacy.

What you mean to say is that clients prefer to choose the block with the least block hash.

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?

Let's say I have two hashes: 0xF000 and 0xEFFF. Target is 0xFF00. Then:

• The two hashes have the same difficulty.
  
• The second hash is numerically less than the first.
  

[revans]

That is an accurate headline. Bitcoin is fundamentally broken per these findings, and significant exploitation of these findings (which given human nature and financial incentives is inevitable) Bitcoin will collapse. Bitcoiners can issue all the press releases attempting to debunk this reality as they like, it won't change a damn thing. The only question is how quickly this exploitation happens, and how rapidly it poisons the whole network

Fun times ahead.

You can't seriously think that a mining pool waiting to announce its blocks until they invalidate the maximum amount of other peoples' computation is going to significantly perturb the network unless that mining pool already has a non-trivial fraction of the total hashrate.

The network is hardly in any danger of being poisoned.

 

As things stand that is exactly what I think. Client patches can ameliorate the issue, but not fix it.

[eldentyrell]

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.

[revans]

That is an accurate headline. Bitcoin is fundamentally broken per these findings, and significant exploitation of these findings (which given human nature and financial incentives is inevitable) Bitcoin will collapse. Bitcoiners can issue all the press releases attempting to debunk this reality as they like, it won't change a damn thing. The only question is how quickly this exploitation happens, and how rapidly it poisons the whole network

Your view assumes Bitcoin is a static thing; Bitcoin can be changed in response to this attack

What the Bitcoin Foundation should be doing is releasing a press release welcoming the Cornell researchers competent analysis of the flaws in the system, while pointing out that one of the strengths of Bitcoin is that flaws can be corrected if a clear majority of Bitcoin users choose to change the software they run.

Well so far the Bitcoin community of cultists have done little but accuse the researchers of being part of a government plot to destroy Bitcoin, and some idiot has even put a Bitcoin bounty on their heads.

As to changing client software, it will ameliorate the problem, but it cannot fix it.

[jl2012]

My ELI5 explanation that I posed to bitcoin-development might help people understand the attack:

Alice is a miner with some amount of hashing power. She has the ability to detect new blocks on the network extremely effectively because she has controls a lot of nodes with low-latency, high-bandwidth connections; in short she has unusually good knowledge of the state of the network. She is also very good at publishing her blocks and getting them to the majority of hashing power in very little time; she has unusually good connectivity to all miners. (again low-latency and high bandwidth)

She's so good at this that when she finds a new block, she keeps it a secret! She can get away with this because she knows that the moment any other miner, like Bob, finds a block, she can immediately broadcast it to the rest of the network before the other block propagates. Instead of building on Bob's blocks, almost everyone builds on Alice's block, having seen it first, depriving Bob of the revenue. Gradually Alice gets more and more miners because all the other pools don't pay out as much as Alice's pool does. This eventually leads to Alice having a majority of hashing power, or if not that due to social pressure, a majority of the mining revenue.

"low-latency and high bandwidth" is not free. Unless the extra revenue can cover the cost, it is still economically prohibitive to do this

[acoindr]

Google news is showing a number of articles which amount to FUD, and are multiplying like gremlins.
Perhaps the Bitcoin Foundation should put up a short rebuttal / press release encapsulating some of the information in this thread. While the Eyal paper has some merit - it is certainly not a situation of "'Bitcoin Is Broken' And Could Collapse"
...

I agree it would be nice for Bitcoin Foundation to try and get a boot on this.

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

To conceptualize how this works imagine a group passing a glass of wine to share. It takes a while for the wine to "propagate" to each person's mouth because it's passed one by one. It would be more efficient to place the glass at front and connect several straws from it to every person. Propagation is then basically instant. All a (voluntary) MBR does is serve as a reference point for finding and informing about found blocks, which reduces latency tremendously.

[Enochian]

Well so far the Bitcoin community of cultists have done little but accuse the researchers of being part of a government plot to destroy Bitcoin, and some idiot has even put a Bitcoin bounty on their heads.

As to changing client software, it will ameliorate the problem, but it cannot fix it.

By now, the Bitcoin market has priced in this information.  Bitcoin is at $239 on Mt. Gox.  Bitcoin doesn't care, and neither should you.

[eldentyrell]

By now, the Bitcoin market has priced in this information.  Bitcoin is at $239 on Mt. Gox.

^^ best post in thread

[jl2012]

That is an accurate headline. Bitcoin is fundamentally broken per these findings, and significant exploitation of these findings (which given human nature and financial incentives is inevitable) Bitcoin will collapse. Bitcoiners can issue all the press releases attempting to debunk this reality as they like, it won't change a damn thing. The only question is how quickly this exploitation happens, and how rapidly it poisons the whole network

Your view assumes Bitcoin is a static thing; Bitcoin can be changed in response to this attack

What the Bitcoin Foundation should be doing is releasing a press release welcoming the Cornell researchers competent analysis of the flaws in the system, while pointing out that one of the strengths of Bitcoin is that flaws can be corrected if a clear majority of Bitcoin users choose to change the software they run.

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

Selfish-mining won't be successful without a low latency connection and/or Sybil attack.

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?)

On the other hand, we can make a Sybil attack expensive: non-p2p alternative block broadcasting channels, certified nodes and miners, full nodes on TPM, restricting number of peers from the same ip range or the same country

With all these optimizations, I don't think selfish-mining is profitable

[justusranvier]

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.