What Quantum Computers Mean For Bitcoin

Image 1: Photograph of a chip constructed by D-Wave Systems Inc., mounted and wire-bonded in a sample holder. The D-Wave processor is designed to use 128 superconducting logic elements that exhibit controllable and tunable coupling to perform operations.

Quantum computers are making an increasingly rapid transition from chalkboard fantasy to commercial reality. A few months ago, we discovered from the Snowden leaks that the NSA is attempting to construct the world’s first useful quantum computer. D-Wave, a company interested in developing quantum computer hardware for commercial use, has sold several prototypes, one to Google, of a quantum-machine that, while not a full computer, may be capable of solving certain classes of problems much faster than conventional computer hardware.

In order to understand why this is significant, you have to understand what a quantum computer is. These machines, only a few very trivial prototypes of which have ever been built, are systems that allow certain kinds of mathematical problems to be solved enormously faster than regular computers.

Image 2: The Bloch sphere is a representation of a qubit, the fundamental building block of quantum computers.

In computer science, there’s a critically important idea called “computational complexity.” The key insight of computational complexity is that, if you have a computer solving a problem, doubling the speed of a computer doesn’t allow you to solve problems that are twice as hard in the same amount of time. Some problems become more complicated with additional data points, at a rate greater than 1:1. Some problems, in fact, become exponentially more complex as you increase the size of the data set you’re working on (an example is the problem of finding the shortest route among a set of points on a map, which becomes intractable with only a few hundred points). Quantum computers, by exploiting the ability of subatomic particles to be in more than one state simultaneously, can investigate multiple possible solutions at one, making some previously intractable problems solvable.

This has profound implications for cryptographic algorithms, which rely on the fact that the mathematical problems that need to be solved to break them would take billions of years to solve using conventional computers. Many of the cryptographic algorithms currently in use (including staples like RSA) have known quantum algorithms that quickly crack them. We don’t have computers capable of running those algorithms yet, but once we do, anyone still using those cryptographic schemes will find themselves vulnerable.

For a long time, it was believed that elliptic curve cryptography, the cryptosystem that provides digital signatures for Bitcoin, might be immune to quantum attacks. Unfortunately, we now know that this is not the case: a quantum algorithm has been found that allows private keys to be quickly computed from known public keys.

At first glance, this might appear to be a death blow for Bitcoin — as soon as your public key is known, any attacker with a quantum computer could deduce your private key, and transfer your Bitcoins to themselves. However, the situation is not quite as grim as it might first appear:

When you send a transaction to the Bitcoin network, the recipient of a transaction is concealed behind a hash: only the hash of their public key is actually disclosed to the network. This is because cryptographic hash functions are immune to quantum attacks. This means that attackers can’t simply go sniffing around robbing every wallet that Bitcoins are ever sent to. They have to wait for a transaction to be made from a wallet (an operation that discloses the public key in full). That means that wallets are still secure, provided they’re one-time-use-only. As soon as you spend money from your Bitcoin wallet, you would have to immediately also transfer the remainder to a new, secret wallet, and repeat for each subsequent transaction. This process could be automated (and brain wallets could still be used, by generating your key pairs by hashing together your passphrase with a nonce that increments with each transaction to generate a new one-time-wallet). This is, however, at least a little inconvenient. Any publicly posted Bitcoin wallet would have to be updated each time the user tried to empty it, and the idea of an offline Bitcoin addressbook becomes impossible. Still, under these conditions, Bitcoin would probably remain useable.

There may be other solutions, as well. We are aware of several cryptographic schemes that are probably not vulnerable to quantum attacks, and if we had sufficient warning that Bitcoin was about to become vulnerable, we can imagine creating a “Bitcoin 2” using a mature version of one of these schemes, and using proof-of-burn to transfer Bitcoin holdings into the new money. However, this is a ways off, and may not be practical at all, depending on the details of how quantum computers hit the market.

If we’re fortunate, we will have enough warning for people to switch over to one-time-use wallet software, and generally prepare for the quantum apocalypse well enough to avoid major economic fallout. If we’re unlucky, quantum computers will arrive in a small number of malicious hands before we’ve really had enough time to properly evaluate the threat, and the resulting panic selling will crash the market, causing great wailing and gnashing of teeth. Time will tell which scenario is more likely, but it’s probably worthwhile for the Bitcoin developer community to begin creating the tools we’ll need sooner, rather than later.

Photo Credits:

Image 1: © D-Wave Systems, Inc.  (License)

Image 2: Glosser.ca