Bitcoin Lied, Confirmed Transactions Died

Is there a lesson to be learned from the March 11th hard fork?

Bitcoin as a new technological and financial innovation might not have reached its current level of success had it not been able to make one specific promise: “Confirmed” transactions will never be reversed.

This isn’t an actual promise that is written anywhere but it is the widely followed practice of treating Bitcoin transactions that have reached the threshold of six block confirmations as being transactions that have attained this confirmed status.  Once reaching this status the transaction is relied upon as being finalized and that the status can never change at any time in the future.

However last month, that presumption was false.
 

A customer of the payments company OKPay took specific, deliberate measures to effectively cancel a Bitcoin transaction after it had already confirmed.  This transaction had a value worth over $10,000 USD at the time it was made. The transaction had confirmed with six confirmations and upon reaching that status OKPay then had delivered away, per the customer’s instruction, a $10,000 USD payment using another form of non-reversible funds.

Fortunately, in this instance, the customer did end up voluntarily returning the bitcoins and OKPay didn’t suffer much financial loss as a result but this illustrates the exposure to a risk that exists for those who accept Bitcoin for payment.

This risk that merchants, exchanges and individuals are exposed to is the double spending attack that comes as the result of either of two attack methods:

• Brute force from a fractional amount of Bitcoin mining capacity combined with a bit of luck, or,
• The overpowering force attained by matching or exceeding the entire sum of all existing Bitcoin mining capacity.

The latter is called the 51% attack because the attacker’s computational strength, once brought online, represents more than 50% of the total mining capacity network-wide.

These attacks can be successful because of Bitcoin’s decentralized architecture.  A simplified way to describe Bitcoin is to equate it to being a ledger of value assignments.

A savings account at a bank might be described as being a ledger in the same manner where the ledger holds a record of all deposit and withdrawal transactions.   However, with a bank account there are methods for the bank to reverse or cancel a transaction.

For example, if a check is deposited into a savings account but then the check bounces the bank would then later reverse the deposit transaction and might even instantiate a new transaction to assess a fee.

The Bitcoin ledger is designed to provide neither of these two capabilities to anyone, anywhere.

Bitcoin does this by using math to assess a relatively enormous cost for attempting to change the past record of the ledger transaction history.

When a transaction is included in a block in Bitcoin’s blockchain, and then additional blocks are built atop that block, only through the expenditure of a great amount of computational effort (and/or a significant amount of luck) can that historical record be rewritten.  With each additional block extending the chain further, the amount of computational effort necessary to change the history becomes so extreme that any attempt to do so gets prohibitively expensive.  Without an economically viable use case for performing such an attack, it is generally accepted that the threshold of six confirmations is sufficient to recognize a payment transaction as being settled.

Tens of millions of dollars worth of value are transferred daily now in which the recipients extend their trust based on the presumption that a confirmed transaction with six or more confirmations has reached its final, permanent status.

The March 11th Hard Fork

On that day at about 10:39 pm UTC a previously overlooked limitation in the Bitcoin client reared its head.  Following that event some exchanges, merchants, and individuals were processing payment transactions unaware that part of the Bitcoin network wasn’t able to accept the historical record being produced.  The Bitcoin blockchain had forked with one side after the split advancing relatively normally but the other side, using client software with the limitation, was following a different path of the blockchain and was advancing at a snail’s pace.

The fork was the result of new software — the version 0.8 Bitcoin-Qt/bitcoind client that had been released just a couple weeks earlier.  The v0.8 client uses a different database engine and thus it was ignorant of the limitation imposed by a configuration setting used with all prior versions of the Bitcoin client.  The new v0.8 client allowed a block to be built that prior versions of the client (pre-v0.8) couldn’t process.

Only a small fraction of the Bitcoin mining capacity was still using the pre-v0.8 client software however most merchants and exchanges had not yet switched over to v0.8.  Many releases prior to v0.8 are still supported so a solution that wouldn’t exclude those users was needed.

Those using the v0.8 client were seeing transactions reported as having confirmed (with six or more confirmations) and at the time that was an accurate status.  However unknown at the time was that this incident would be resolved through having a vast majority of mining capacity abandon the v0.8 client and then revert to a prior release (or to use an emergency patch hastily made available for v0.8 miners).  This action would cause the confirmed status for those transactions to be meaningless — giving those exchanges, merchants, and individuals a false sense of security.

The defection by the miners was essentially a 51% attack as it was a conscious effort made to direct mining work to a forked branch that was not the blockchain tip that had the greatest height. However this was not done with malicious intent nor was it an attempt to defraud.  

In the short term, much mining capacity is controlled and directed by a handful of mining pool operators.   It took about ninety minutes before individual reports of trouble led to the realization that Bitcoin’s network had split.  From there the Bitcoin-Qt/bitcoind development team began notifying some pool operators and exchanges as to the situation and others in the community delivered the alert through various informal communications channels including other IRC channels, Twitter, the BitcoinTalk forum and more.

Within a very short time frame some pool operators, including the largest — BTC Guild, concluded that the economic majority would not object to the pools abandoning the blockchain that was longest at the time in order for them to instead support the pre-v0.8 fork.  The aim for this support was to cause that pre-v0.8 fork to gain a vast majority of mining capacity sufficient to quickly converge the chains causing that pre-v0.8 fork to become the new longest chain.

The presumption was that transactions that had become confirmed in the v0.8 side would also soon be included in the pre-v0.8 fork.  But that would not be instantaneous nor was there a guarantee that it would occur for each and every transaction.

For about eight hours many transactions that had already confirmed on the v0.8 blockchain would not yet be included in blocks on the pre-v0.8 fork.

BitconTalk forum user “macbook-air” reported that after discovering this delay he created and broadcast an intentional double-spend transaction against OKPay to “void” his pior payment to them. That double spend transaction attempt made its way into a block, eventually, causing the original Bitcoin transaction (worth about $10K) to become forever invalid on the pre-v0.8 fork.

When the chains converged, the transaction that OKPay received and had seen as confirmed essentially then died.  OKPay’s v0.8 client would then show the transaction with a 0/unconfirmed status and eventually the transaction would be purged.  It would then appear as if the confirmed Bitcoin transaction worth over $10K USD had never occurred.

This was the first fork involving a confirmed transaction since an August 2010 incident — an event that had occurred before Bitcoin was being relied on for transactions of any significant economic value.

The Successful $10K USD Double Spend Attack

With Bitcoin using a peer-to-peer architecture, transactions made by a client node are communicated to only the peers that node happens to be connected to.  Those peers each first verify the transaction is valid and then relay the transaction to the other peer connections.  Within seconds most every Bitcoin client node in the world is aware of that spend transaction.

An attempt to broadcast a transaction that spends funds that have already been spent will not get relayed by that node’s peers because they will reject the transaction as a double spend.  At least that’s the general design.

When a client node gets started or restarted it is ignorant of any transactions except those confirmed transactions in the blockchain it already knows about.  When that node receives a transaction, it has no way of knowing if that transaction is being rejected elsewhere as a double spend and gladly adds that transaction to its memory pool for eventual inclusion in a block.  With the Bitcoin-Qt client that transaction will be displayed as a 0/unconfirmed transaction.  Normally this causes little problem because until a transaction has reached confirmed status, any merchants accepting payment on 0/unconfirmed (or anything less than 6 confirmations) are generally aware to not presume that the unconfirmed transaction is final.

A client node will hold a list of the transactions that have not yet confirmed but those transactions consume memory.  This list of transactions are stored in what is called the node’s memory pool.

The tens of thousands of client nodes around the world are being run on computing hardware that ranges from enterprise-level server systems to the lowest end of the old spare laptops.  To accommodate that range, the Bitcoin client purges unconfirmed transactions when valid newly arriving transactions would overflow the memory pool.    This makes a node receptive to receiving, verifying, storing and relaying a double spend transaction that it previously might have rejected as being invalid.

Because nodes generally have only a few connections a particular node’s absent mindedness isn’t very harmful because that node’s peers will generally still know about the original valid transaction and will continue to reject the double spend.

When the mining pools and solo miners downgraded to pre-v0.8 clients or restarted with the emergency v0.8 patch, a large number of nodes started up around the same time and each started with a clean memory pool.  This was a dangerous time for merchants and a forum post by a core member of the development team recommended that merchants stop processing transactions.  For merchants and exchanges like OKPay that had already delivered value based on confirmed payment status, that message came too late.

The bitcoin client follows a protocol to protect against a number of denial-of-service attacks.  Because of this, transactions propagate first with an initial transaction broadcast, and then only sporadically when the sending node realizes that some time has passed and the transaction has not yet been included in a block.

This gives a double spend attacker plenty of opportunities to repeatedly broadcast the alternate transaction in hopes that a transaction will reach a miner who will see the transaction as valid and then include it in a block.  And that is exactly the approach macbook-air took — spewing the double spend transaction every ten seconds until either the original transaction or the double spend got included in a block.   Within minutes of first trying, Macbook-air’s double spend was successful.  The transaction that OKPay had seen as confirmed with six transactions was now invalid.  The bitcoins OKPay had received were now gone.

Where’s The Flaw?

The bitcoin client evolves to protect against existing or anticipated threats.  This unplanned hard fork scenario was not something impossible to envision however with the limited resources of a mostly all-volunteer development team, the risks and remedies for successful double spending in this type of situation might not have been given the proper attention deserved.

Even if this had been carefully thought through at one point in time, Bitcoin network activity changes over time.  Recent scalability issues including both how blocks are now becoming full in increasing number as well as how transactions are being purged from each node’s limited memory pool sooner now are items that might not have been given proper weighting in any earlier studies of unplanned hard fork scenarios.

Should this same type of event occur today, some recommendations might be considered:

• On startup of a node, allow the memory pool to be initialized first from a set of transactions.  A set of transactions could have been prepared and made available to miners (or created by miners themselves) that included all transactions that existed in the soon-to-be-orphaned blocks, from where the fork began.
  This is an emergency mode protection but since pool miners knew they were abandoning a chain in which merchants had already received transactions showing confirmed status this courtesy would have caused macbook-air’s later transaction to be seen as an invalid double spend.
• Aggressively re-broadcast transactions from the abandoned chain, including those from that side’s memory pool.  Essentially Macbook-air was more aggressive at broadcasting double spend transactions and won the “race” as a result.
  It has not been publicly disclosed (and possibly something not even studied) why several hours after mining with the v0.7 client the miner that included Macbook-air’s transaction (again, BTC Guild) didn’t yet know of the previous transaction that OKPay had seen as confirmed on its blockchain, or if instead that transaction had been seen but later purged from the node’s memory pool.
  The larger exchanges, merchant processors, and others might have the means and incentive to perform this added service to make sure transactions involving them get aggressively rebroadcast but that leaves vulnerable the individual merchants and traders.  Perhaps a commercial service could provide this.
• Re-evaluate whether six confirmations is enough.  At the time the first alert was received on v0.8 clients, transactions in the soon-to-be-orphaned blocks had over a dozen confirmations.  Perhaps merchants who deal in larger transactions and have no recourse against losses might wish to impose a confirmation threshold that has less risk.  Requiring two dozen confirmations is something that could cause recognition of payments to be delayed for about four hours, but if OKPay had that policy they would likely have been alerted as to the problem long before sending out the USD funds that its customer had requested.
  Lead developer Gavin Andresen was quoted as saying 24 hours (120+ blocks) is the threshold to be “100% safe”.

One thing to realize is that it doesn’t necessarily even take a software bug for a confirmed transaction to eventually become invalidated.  In his paper Analysis of hashrate-based double-spending, Meni Rosenfeld describes how with just 10% of the hashing capacity of the Bitcoin network, one out of a thousand trials would cause a blockchain reorg for six blocks in which double spending of transactions with a confirmed status could be the result.  With even greater hashing capacity, the number of trials needed decreases significantly.

Every party that accepts Bitcoin for payment has some degree of exposure to these double spending risks.  The question about the risk isn’t being asked perhaps because no other payment systems are decentralized and the concepts of a “51% attack” and “race attack” are foreign and not easily explained.

It might be easy to dismiss the risk as with this very rare event there there were maybe only a few hundred transactions that were at risk anyway.  And of those, there was just one successful double spend reported.   This was the extent of the damage over several dozen months of continuous operation.  But instead this might just have piqued the interest of those seeing for the first time a new attack vector and should this type of scenario ever play out again, the outcome could be losses that are much, much steeper.

Previous Posts - Twitter: @BitcoinMoney