The Threat to Bitcoin from Quantum Computing

– May 28, 2018 Reading Time: 4 minutes

At nearly every lecture I’ve given on blockchain technology, and its most famous use case in Bitcoin, someone stands to ask about quantum computing. What exactly do I propose to do about this terrible threat?

My answer has been that I propose nothing personally but the very core of innovation in this sector is about problem solving. If there is a known problem, there are people working on solutions, with tremendous professional awards accruing to the winner. Governance models are designed to implement solutions. It’s this adaptivity that makes this technology so much superior to central planning over money and ledgers.

That’s a fine answer but it still leaves the question: just how real is this threat?

This week, it was my pleasure to sit on a panel with Gavin Brennen of Macquarie University in Sydney, Australia, a physicist and one of the world experts on this topic. He presented a very nice paper that examined this question in some detail. He began with his frustration over the headlines that swept the tech world last October and November. They were as alarmist as they were misleading. He set the record straight.

You can read his paper in full for the details.

Proof of Work

At the root is the remarkable speed of quantum computing, which is far more efficient than classical computing at performing key functions that make the blockchain work, namely hashing operations and proof of work. The proof of work standard can be met with far less energy and time which could potentially hack existing mining operations and centralize the network. In addition, quantum computing could pose a threat to standard cryptography by cracking keys in a way that could pose security risks, at least in theory.

Gavin and his coauthors set out to examine the likelihood and timeframe when this threat becomes real. The results are far more boring that you might expect. Their simulation models show the following:

The extreme speed of current specialized ASIC hardware for performing the hashcash PoW, coupled with much slower projected gate speeds for current quantum architectures, essentially negates this quadratic speedup, at the current difficulty level, giving quantum computers no advantage. Future improvements to quantum technology allowing gate speeds up to 100GHz could allow quantum computers to solve the PoW about 100 times faster than current technology. However, such a development is unlikely in the next decade, at which point classical hardware may be much faster, and quantum technology might be so widespread that no single quantum enabled agent could dominate the PoW problem.

The paper presents a graph comparing the efficiency of current hashing strategies with eventual quantumization. The results show that the problem cannot become an issue for another 10 years but even following, there is no real threat to the existing Bitcoin network.

The Signature Threat

What about the second threat to cryptography posed by better signature-cracking technology. Here the threat is more real but not without solutions. The problem as they state it is that “the signature scheme can be broken in less than 10 minutes…as early as 2027.” The most serious problem concerns the following scenario:

After a transaction has been broadcast to the network, but before it is placed on the blockchain it is at risk from a quantum attack. If the secret key can be derived from the broadcast public key before the transaction is placed on the blockchain, then an attacker could use this secret key to broadcast a new transaction from the same address to his own address. If the attacker then ensures that this new transaction is placed on the blockchain first, then he can effectively steal all the bitcoin behind the original address.

What can be done? Gavin presented a number of post-quantum signature schemes that would protect against such a scenario. He points out that there are at least four classes of known solutions to the problem and alternatives within each, all within reach of programmers today. Moreover, there are ten years of lead time to get there and adapt them to the protocol.

All of which is to say: this quantum threat to Bitcoin is mostly a red-herring, not entirely false but a fixable issue, especially given the robust network behind cryptocurrency and the strong incentive to provide the best security possible.

Problems and Solutions

As I listened to the paper, and his proposed solutions, it struck me how precise and intense is the brain trust behind this technology as compared with, for example, the Federal Reserve, the banking system, and existing fiat currency. The problems in the fiat status quo are enormous enough to fill whole libraries (starting with certain obvious problems: no one knows how much money the system produces, or how much crisis risk is present at any time, not even the people charged with managing the system). The problems revealed themselves in 2008. The system has not been repaired in a way that can prevent a repeat of that experience.

Political economy is not about generating perfect solutions but rather choosing among options to find the best one while supporting adaptive institutions that deal with real threats with real solutions. The brilliance of cryptocurrency is that it rallies around truth, and never stops improving to reveal ever more of it.