No, Bitcoin isn’t broken

November 7, 2013

(Antana)

"Bitcoin Is Broken," proclaimed Ittay Eyal and Emin Gun Sirer, two Cornell computer scientists. In Bitcoin's peer-to-peer process for processing transactions, computers called "miners" compete to solve a difficult mathematical problem, with the winner earning a reward. The researchers analyzed the rules of this process and concluded that it allows a minority of miners to collude and gain more than their fair share of the rewards. In the long run, they suggest, this colluding minority could seize control of the Bitcoin network, negating the benefits of its decentralized peer-to-peer architecture.

This is a clever analysis, but it falls far short of proving that the decentralized cryptocurrency is fatally flawed. In reality, the attack they outline is a relatively minor concern for Bitcoin miners, and shouldn't affect ordinary Bitcoin users at all.

Bitcoin's transaction clearing process operates like a virtual lottery. Each miner makes a list of recent transactions, called a "block," and then tries to solve a difficult mathematical problem that takes that block as an input. A correct solution works like a lottery ticket — it's hard to find but easy to verify once it's been found. The first miner to find a solution announces it to the rest of the miners to claim the prize. Within a few seconds, the other miners verify the ticket is valid, and then the process starts over, with miners creating a new block and trying to solve a new round of the puzzle.

In the Cornell researchers' attack, a minority of of evil miners collude in hopes of gaining an unfair advantage over everyone else. Their strategy works like this: When an evil miner finds a winning lottery ticket, it shares it with the other evil miners but not with the rest of the network. The evil miners abandon the current round and start working on the next one. Meanwhile, the rest of the miners continue looking for a solution to the block the evil miners have solved. That gives the evil miners an unfair head start on the new round of the game.

Eventually, one of the honest nodes will find a lottery ticket of its own and present it to the rest of the network for validation. The moment that happens, an evil node will present its own winning ticket to the network.

Who gets the reward? It's complicated, but in a nutshell the winning ticket will most likely be the one that the majority of other miners see first. If two miners release tickets nearly simultaneously, then some miners will hear about the honest miner's ticket first and others will hear about the evil miner's ticket instead, making the outcome a tossup.

To ensure that most nodes hear about the evil nodes' ticket, Eyal and Sirer propose that the evil nodes set up a large number of fake miners whose only job is to listen for honest miners announcing their own tickets and then quickly disseminating the evil miners' preferred ticket instead. In theory, a large enough network of fake miners should be able to ensure that the evil miners' lottery ticket gets accepted close to 100 percent of the time. And even without that kind of trickery, the researchers calculate that the colluding miners may be able to get their ticket recognized frequently enough that the strategy earns the colluding miners an unfair profit at the expense of other miners.

The upshot is that the honest miners waste a lot of their time trying to solve a problem that's already been solved. So the evil miners will win more than their share of the rewards. The researchers argue that honest miners will have a strong incentive to join the conspiracy. Over time, they say, the conspiracy will grow until it has gained a majority of the network's computing power. And at that point, it will gain the de facto power to block and even reverse transactions submitted to the network.

"I think it's been overblown by the media a lot," says Bitcoin developer Mike Hearn of the paper. He says that Eyal and Sirer "hand-wave away" many of the potential difficulties in carrying out their proposed attack. For example, he says, it would be hard to add a huge number of fake miners to the network without people noticing.

Indeed, the biggest problems with their attack are social more than technological. Many Bitcoin miners have organized themselves into "pools" that combine their computing power and share the proceeds. The leaders of the major mining pools know each other. And if some miners started trying to corrupt the mining process, they would notice.

It's not hard for honest nodes to take countermeasures if they figure out what's going on and which miners are part of the conspiracy. If an evil miner and an honest miner both announce a lottery ticket around the same time, the honest nodes can always pick the ticket announced by the honest miner over the evil miner's ticket.

And the Cornell attack would be easy for honest miners to detect. Right now, it's rare for two miners to announce solutions within seconds of each other. If that started to happen on a regular basis, it would be strong evidence that something fishy was going on. The more often it happened, the more data they'd have to help them identify who was honest and who was participating in the conspiracy. Honest mining pools could publish lists of their members to help flush out the impostors.

"People have been coming up with complicated game theory attacks on the blockchain for quite a long time," Hearn says. "This one is interesting but it's not the biggest problem Bitcoin faces by any means."

SECTION: {section=business/technology, subsection=null}!!!
INITIAL commentConfig: {includereply=true, canvas_permalink_id=washpost.com/8bvh5zpd9k, allow_comments=true, commentmaxlength=2000, includeshare=true, display_comments=true, canvas_permalink_app_instance=m6yzjj840m, display_more=true, moderationrequired=false, includefeaturenotification=true, defaultsort=reverseChronological, canvas_allcomments_id=washpost.com/km4ey0dajm, comments_period=14, includevoteofftopic=false, allow_videos=false, includesorts=true, markerdisplay=post_commenter:Post Commenter|staff:Post Writer|top_commenter:Post Forum|top_local:Washingtologist|top_sports:SuperFan|fact_checker:Fact Checker|post_recommended:Post Recommended|world_watcher:World Watcher|cultuer_connoisseur:Culture Connoisseur|weather_watcher:Capital Weather Watcher|post_contributor:Post Contributor, childrenitemsperpage=3, includeheader=true, includeverifiedcommenters=true, defaulttab=all, includerecommend=true, includereport=true, maxitemstop=2, source=washpost.com, allow_photos=false, maxitems=7, display_ugc_photos=false, includepause=true, canvas_allcomments_app_instance=6634zxcgfd, includepermalink=false}!!!

UGC FROM ARTICLE: !!!

FINAL commentConfig: {includereply=true, canvas_permalink_id=washpost.com/8bvh5zpd9k, allow_comments=true, commentmaxlength=2000, includeshare=true, display_comments=true, canvas_permalink_app_instance=m6yzjj840m, display_more=true, moderationrequired=false, includefeaturenotification=true, defaultsort=reverseChronological, canvas_allcomments_id=washpost.com/km4ey0dajm, comments_period=14, includevoteofftopic=false, allow_videos=false, includesorts=true, markerdisplay=post_commenter:Post Commenter|staff:Post Writer|top_commenter:Post Forum|top_local:Washingtologist|top_sports:SuperFan|fact_checker:Fact Checker|post_recommended:Post Recommended|world_watcher:World Watcher|cultuer_connoisseur:Culture Connoisseur|weather_watcher:Capital Weather Watcher|post_contributor:Post Contributor, childrenitemsperpage=3, includeheader=true, includeverifiedcommenters=true, defaulttab=all, includerecommend=true, includereport=true, maxitemstop=2, source=washpost.com, allow_photos=false, maxitems=7, display_ugc_photos=false, includepause=true, canvas_allcomments_app_instance=6634zxcgfd, includepermalink=false}!!
Comments
SECTION: {section=business/technology, subsection=null}!!!
INITIAL commentConfig: {includereply=true, canvas_permalink_id=washpost.com/8bvh5zpd9k, allow_comments=true, commentmaxlength=2000, includeshare=true, display_comments=true, canvas_permalink_app_instance=m6yzjj840m, display_more=true, moderationrequired=false, includefeaturenotification=true, defaultsort=reverseChronological, canvas_allcomments_id=washpost.com/km4ey0dajm, comments_period=14, includevoteofftopic=false, allow_videos=false, includesorts=true, markerdisplay=post_commenter:Post Commenter|staff:Post Writer|top_commenter:Post Forum|top_local:Washingtologist|top_sports:SuperFan|fact_checker:Fact Checker|post_recommended:Post Recommended|world_watcher:World Watcher|cultuer_connoisseur:Culture Connoisseur|weather_watcher:Capital Weather Watcher|post_contributor:Post Contributor, childrenitemsperpage=3, includeheader=true, includeverifiedcommenters=true, defaulttab=all, includerecommend=true, includereport=true, maxitemstop=2, source=washpost.com, allow_photos=false, maxitems=7, display_ugc_photos=false, includepause=true, canvas_allcomments_app_instance=6634zxcgfd, includepermalink=false}!!!

UGC FROM ARTICLE: !!!

FINAL commentConfig: {includereply=true, canvas_permalink_id=washpost.com/8bvh5zpd9k, allow_comments=true, commentmaxlength=2000, includeshare=true, display_comments=true, canvas_permalink_app_instance=m6yzjj840m, display_more=true, moderationrequired=false, includefeaturenotification=true, defaultsort=reverseChronological, canvas_allcomments_id=washpost.com/km4ey0dajm, comments_period=14, includevoteofftopic=false, allow_videos=false, includesorts=true, markerdisplay=post_commenter:Post Commenter|staff:Post Writer|top_commenter:Post Forum|top_local:Washingtologist|top_sports:SuperFan|fact_checker:Fact Checker|post_recommended:Post Recommended|world_watcher:World Watcher|cultuer_connoisseur:Culture Connoisseur|weather_watcher:Capital Weather Watcher|post_contributor:Post Contributor, childrenitemsperpage=3, includeheader=true, includeverifiedcommenters=true, defaulttab=all, includerecommend=true, includereport=true, maxitemstop=2, source=washpost.com, allow_photos=false, maxitems=7, display_ugc_photos=false, includepause=true, canvas_allcomments_app_instance=6634zxcgfd, includepermalink=false}!!
Show Comments
Next Story
Andrea Peterson | November 7, 2013