Skip to main content



Bitcoin and the Double-Spending Problem

Many digital currencies face the problem of double-spending: the risk that a person could concurrently send a single unit of currency to two different sources. This moral hazard arises due to the trivial reproducibility of digital information, and the information asymmetry that can result from this. Double-spending occurs when an agent can easily conceal or misrepresent information about the recipients of a particular currency unit, and can thus spend currency twice with a low chance of facing the risk posed by the action. The action causes the value of a currency unit to be misplaced among two indistinguishable copies, and can be considered a market failure. A currency system in which value comes apart from the currency itself is useless.

With traditional physical currency, the double-spending problem is dramatically less likely to occur. This is because everyone involved in an exchange has immediate visual access to the original physical currency involved. There can be no information asymmetry unless the spending party goes through unusual measures to photocopy their currency or make a deal with multiple parties based on the promise of a single unit of currency, so it is usually not wise to risk double-spending physical currency. Information about a physical currency’s true location is much harder to misrepresent, as physical objects are not trivially reproducible. When physical currency is exchanged, the entire unit is moved to the other party by default, and not copied.

When digital currency is exchanged, there is a very real possibility that the currency could be copied over to the recipient, with the ‘original’ still intact in the owner’s possession. In this case, a currency-holder would be much more likely to take the risk of spending a unit of currency twice, because it is less likely that they will be caught and made to face the consequences of the deceitful exchange. In the absence of a mechanism to ensure double-spending does not occur, one of the recipients of the double-spent currency will more likely bear the burden of the currency duplication.

Bitcoins are a decentralized, open-source digital currency, which have become the most widely used alternative currency since being introduced in 2009. With no central agency to verify that the currency is spent only once per possession, some were initially skeptical of its safety against market failure. Satoshi Nakamoto, the designer of the bitcoin protocol, had anticipated this problem, and built in a mechanism to verify each transaction that a bitcoin goes through.

The bitcoin uses a mechanism based on transaction logs to prevent double-spending. Each bitcoin has a log of digital signatures attached to it, denoting the true path of its exchanges. This log is open for anyone to view, so anyone can verify the correct exchange path. Exchanges are recorded by ‘bitcoin miners’, who carry out the computationally intensive task of cracking a SHA256 hash function given to them dependent on the rate at which mining is currently being done. The only known method to accomplish this is to randomly test different prime number pairs in brute force fashion. In this way, a chain (called the block chain) of verified transactions is built up, which is very hard to falsify due to the great computational power that goes into the computation of the whole chain. This verification is a type of proof-of-work protocol, which makes the generation of new blocks difficult, and verification (done by the bitcoin peer-to-peer network) relatively easy. The block chain is viewable by anyone in the bitcoin network, making it harder to distort transaction information.

In return for carrying out these difficult proof-of-work computations, bitcoin miners are compensated with new bitcoins generated after each transaction. The first block in every new chain is given to the agent who mined it. This provides incentive for the users to put in the computation required to verify the transactions chain, and gives a mechanism for releasing new currency into the network. New bitcoins are distributed at a relatively stable rate by mining, as the difficulty increases proportionally to current hashing rates.

Although this method has worked well from a general perspective, it is by no means perfect. People have attempted a number of different workarounds of the verification system, which have been successful in some instances. Most are related to out-computing the block chain security mechanism, or timing the exchange so that once a mistake has been detected, the transaction has already been completed. Most thefts that have occurred so far were not due to double-spending, but to insecure sites for storing and selling bitcoins.

One possible (but unlikely) attack results from the way bitcoins handle conflicts in the block chain. When a fork develops in a block chain, and there are two conflicting block paths, the miners decide which chain is valid by continuing to add blocks to it. The longest block chain is viewed as the valid block chain, because the majority of the network computation is assumed not to come from malicious users. If a user controls the majority of computational power in the mining network, they can manipulate this to their advantage by creating two diverging chains: one in which the money goes right back into their own wallet, and another sending money to a seller. In the “>50% attack”, one would invalidate the chain sending bitcoins to the seller, while keeping both the cost and income of that transaction. This attack is infeasible for any single user (unless they’re in possession of multiple supercomputers), as it would require enormous power to recompute the hashes of all the previous blocks in a chain. With a powerful botnet engaged in bitcoin mining, this attack becomes more likely, but this has not yet been a problem.

In March 2013, a problematic fork became apparent in the block chain. It developed due to a conflict between two different versions of bitcoin, and not due to any single malicious user. The logs of two different bitcoin versions diverged, allowing currency in each chain to be double-spent. This caused bitcoin prices to rapidly drop off. The fork was resolved by telling users to revert to the chain reported by the earlier version, and prices soon returned to levels close to pre-fork levels. As the valid chain is determined by the majority, the chain in the earlier version quickly became re-established as the primary chain.

Another double-spending attack is known as the ‘race attack’. In transactions that take place in a short length of time, it is hard to confirm verification. The proof-of-work system takes time to complete verification, so an exchange might be completed before a block is verified. In a race attack, one attempts to send two transaction logs simultaneously: a fraudulent one to a seller, and another to the rest of the bitcoin network, where the currency goes back to its original owner. By the time the seller realizes he has received an invalid fork of the block chain, the transaction may have already been carried out. Karame, Androulaki, and Capkun found that these types of attacks are quite feasible without extraordinary measures, but that changes could be made to the bitcoin protocol protecting against them.

So far, the Bitcoin has successfully mitigated the incentive for attempting to double-spend by making the information about its transaction history public, and hard to misrepresent, but some detection faults threaten to allow for the development of dangerously large information asymmetries.

Sources

http://bitcoin.org/bitcoin.pdf

http://arstechnica.com/tech-policy/2011/06/bitcoin-inside-the-encrypted-peer-to-peer-currency/

http://codinginmysleep.com/bitcoin-attacks-in-plain-english

http://eprint.iacr.org/2012/248.pdf

http://arstechnica.com/business/2013/03/major-glitch-in-bitcoin-network-sparks-sell-off-price-temporarily-falls-23/

By Erik Bonadonna

Comments

Leave a Reply

You must be logged in to post a comment.