'Devastating' protocol flaw could paralyze Bitcoin system

Computer scientists say they've identified a fundamental flaw in the Bitcoin electronic currency system that could eventually stunt its development unless developers change the way users are rewarded for their participation.

With about 7.5 million Bitcoins in circulation, the highly decentralized system relies on public-key cryptography and a peer-to-peer network to record who is the rightful owner of each individual piece of currency. When Alice wants to pay Bob 50 coins, she signs the transaction with her private key and broadcasts the details to other nodes. Other participants then receive a small fee in return for verifying the payment, which is done by inverting the cryptographic hashes generated by in the transaction record.

As the currency grows into maturity and an ancillary scheme that allows Bitcoins to be created out of thin air is phased out, the verification of other transactions will be Bitcoin's sole reward scheme. And therein lies the flaw that could represent a chief stumbling block.

With each participant rewarded only for verifying a proposed transaction, there will be little incentive for participants to broadcast transactions to others. Instead, they will want to keep the deals secret so they don't have to share the rewards with others.

“The consequences of such behavior may be devastating,” the researchers wrote in a paper (PDF) that they recently submitted to a peer-reviewed conference. “As only a single node in the network works to authorize each transaction, authorization is expected to take a very long time.”

Shahar Dobzinski, one of the paper's authors, told The Register the security of Bitcoin isn't likely to suffer as a result of the flaw. The use of private encryption keys ensures that each transaction is authorized only by the entity everyone else already agrees is the rightful owner of a given Bitcoin. That helps prevents theft and also keeps a user from spending a unique coin more than once.

The system also doesn't consider a transaction to be fully approved until nodes controlling the majority of the network's CPU power have accepted it, rather than a majority of the nodes themselves. This largely forecloses the likelihood of “Sybil” attacks, in which large numbers of fraudulent identities are used to subvert reputation-based systems.

“This is different problem,” Dobzinski, who is a computer scientist at Cornell University, said of the flaw his paper identifies. “We're afraid the majority of the CPUs might not be able to know about the transaction.”

The paper goes on to propose a modified reward scheme that shares a small portion of the verification fee with participants who forward it to other nodes in the network. Attached to each transaction would be a chain of its forwarding nodes. When a participant solves a discreet block of the transaction, all nodes in the chain that would receive a cut. To prevent additional Sybil attacks in which a single participant forwards himself the same transaction multiple times, the paper proposes canceling rewards when the number of links in the chain reach a certain threshold.

Besides Dobzinski, the researchers included fellow Cornell University computer scientist Sigal Oren and Microsoft researchers Moshe Babaioff and Aviv Zohar. They compared their solution to the winning entry in the 2009 DARPA Network Challenge, in which participants competed to locate 10 red weather balloons that were dispersed across the United States. A team from the Massachusetts Institute of Technology collected the $40,000 prize using a rewards system that created incentives for individuals not involved in the competition to help.

Hunters who found a balloon received $2,000 per discovery, while those who directly recruited a successful hunter received $1,000. A recruiter of a direct recruiter received $500, and so on. The Register's coverage of the competition is here.

Nils Schneider, a developer who works on the Bitcoin project, said the transaction propagation problem described in the paper isn't considered a problem now. In an email to The Register he wrote:

“The paper describes a very interesting theoretical problem but I doubt there will be any need to implement their solutions anytime soon.” ®