What is quantum computing? How is a quantum computer different from a regular computer? What relevance does this have to Bitcoin?
New Bitcoiners have been inevitably bumping into these questions and having to confront the issues they dredge up regarding Bitcoin’s exposure to what is very much an existential threat to its existence if a viable quantum computer were to be developed.
The ability to own bitcoin rests on the foundational assumption that without directly leaking a copy of it, no one but the person who possesses a private key can sign to transact with coins secured by that key. Quantum computing calls that assumption into question.
Quantum computers are not just “computers, but faster.” They function in a very fundamentally different way from a classical computer, and as such they are much more efficient than classical computers at very specific kinds of computations. Now obviously, I’m not going to actually explain how quantum computers work in minute detail within four pages, but I will give you the core intuition of how they are fundamentally different from a classical computer.
So let’s take a look at how both kinds of computers interact with things like large cryptographic keys.
Classical Computers
Everything stored in a classical computer (or just computer from here on out) is stored as a series of 1s and 0s. Each bit (1 or 0) is precisely a 1 or 0; there is no ambiguity. When a piece of data is stored, it’s 1s and 0s. When a piece of data is manipulated or modified, it is done bit by bit, step by step, on each 1 or 0.
That is how a computer works. It linearly, one step after the other, modifies the discrete unambiguous pieces of data that it is storing. It can’t skip ahead, or shortcut (in terms of the steps it’s taking, not more efficient ways to do things mathematically), it has to go through the steps of whatever computation it is doing one by one.
When you generate a private key using a computer, it acquires a random value (you inputting dice, general user input, randomness from device hardware, etc.) and stores that in memory as 1s and 0s. From there it has to multiply this value by the elliptic curve’s generator point to get a public key. This is accomplished with an algorithm, that boiled down to its most basic level, is literally instructions on what bits to take, how to modify them, what circuits to “push” them down on a physical level to accomplish that, and in the end put the new value that has been modified bit by bit back into memory.
There are other steps to arrive at an actual valid address, but for the purposes of this article those are not necessary to go into (but they are just like the above step, just step by step instructions on how to modify 1s and 0s in memory).
So what if someone wanted to use a computer to guess someone else’s private key?
There are 2256 possible private keys. That’s 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 different possible keys.
A computer would have to try every single one of those possible private keys, one after the other (or however many at a time it can do in parallel), step by step following the exact instructions above for generating keys. The more of them you try to check in parallel, the more computing power you need, with no ability to find any shortcuts around that cost.
The less computing power you want to use, the more time it will take, the less time you want it to take, the more computing power you need.
This is an impossible task to accomplish with a computer. On one side you have a computation cost that every computer on Earth is not enough to pay, and on the other side you have a cost in time that is so high every star in the universe would die before you checked them all.
To actually accomplish your goal, you need another option besides checking one by one linearly or in parallel. That’s where quantum computing comes in.
Quantum Computers
Quantum computers don’t work with discrete states. Everything is precisely a 1 or a 0. The most basic piece of information in a quantum computer is a qubit (the quantum version of a bit). Unlike a bit, a qubit is in a superposition where it is both simultaneously a 1 and a 0. It only settles into one or the other discrete states when it is observed.
This is one of the key building blocks that allow a quantum computer to compute differently. The other is entanglement. Qubits aren’t just stored in isolation, the physical atoms representing them and collapsing to a discrete state when observed are entangled together. This means when entangled atoms are observed and collapse to a single state, the entangled atoms collapse to the same state, no matter how far apart they are.
Now here’s where things get weird, and I’m going to have to get a little hand-wavy; you should still walk away with an intuitive understanding of why quantum computers are fundamentally different from a classical computer. An algorithm on a classical computer is a set of instructions to take a specific set of bits, and step by step modify them according to the algorithm’s instructions, until finishing and outputting the finished set of new bits. So the algorithm step by step takes one discrete state and turns it into another.
Qubits don’t store discrete states until they are observed and collapse to one. They store probabilities. When you have a set of qubits entangled of any given size (like in this hypothetical case 2256), each given possible state that it collapse to has a certain probability of collapsing to that given state.
Quantum algorithms, rather than being step by step instructions to operate on discrete states, are a set of instructions on how to operate on those entangled qubits in a way that alters the probabilities of different outcomes. Constructive interference is used to increase the probability of a correct outcome, and destructive interference to decrease the probability of incorrect outcomes (note that this is NOT the noise or interference that makes it difficult for physical quantum computers to function accurately, that is a different concept).
So while a classical computer would have to check each individual private key one by one to find the one matching a specific public key, a quantum computer can simply run a few times using the right algorithm and arrive at the correct answer. It does not do this by “checking all the possibilities at once.” It simply modifies the probabilities of what a superposition will collapse into.
This is why a quantum computer could break the assumptions underlying elliptic curve cryptography, and a classical computer could not (and it is also why quantum computers are only useful for certain types of computations with a massive possible space of answer candidates to check).
Don’t Panic
This fundamental difference between classical and quantum computation means, that yes, if a viable quantum computer is actually produced, that functions correctly, then the underlying assumption that secures all Bitcoiners’ individual bitcoin is broken. All of those funds are insecure.
Yes, this is a serious risk if such a device is actually manufactured, and it works, but we are not entirely unprepared. We understand the problem, we understand the exposure, and a good number of possible solutions to many different facets of the problem are coming together.
Breathe, and relax. Through the rest of this issue we are going to walk you through the whole problem.
This piece is featured in the latest Print edition of Bitcoin Magazine, The Quantum Issue. We’re sharing it here as an early look at the ideas explored throughout the full issue.
