Quantum Computing and Satoshi's Sunken Treasure

Can you ever recover lost keys or can your private keys be hacked through some amazing and secretive advance in computing power?  If you’ve been learning about cryptocurrencies for a while, you’ve probably ended up somewhere in the blast radius of such a discussion.  Unfortunately, the talk of key security was probably an incomprehensible spray of the expert and esoteric language of things like elliptic curve cryptography, lost private keys, the Satoshi wallet, and - weirdest of all - quantum computing.  Compounding this is the fact that it's seldom the case that expert language is being used by experts.  I would like to explain some of the salient parts of these issues, especially the question of whether and when you should be worried about your own keys being hacked or whether you should invest in a quantum computer designed to recover Satoshi’s wallet, or maybe even invest in a quantum-resistant cryptocurrency.  First, I will start with a parable about an actual historical shipwreck that turns out to be much more relevant than it might initially seem.

On September 9th, 1857 the S. S. Central America, an 85 meter long steamship bound for New York City was caught in a hurricane off the coast of the Carolinas.  As the ship was battered by wind and waves, the boilers and bilge pumps that kept the vessel afloat and pointed safely into the swells failed.  In the heaving seas, the crew and passengers formed bucket-brigades in an attempt to bail out the floundering ship but their efforts were ultimately unsuccessful.  At about 8pm on September 12th the Central America sank.  Of the 578 passengers and crew only 153, mostly women and children, survived.  

At the time, the sinking of the S. S. Central America was the largest and most sensational maritime disaster in American history.  This was in large part because of another one of the ship’s occupants that was also lost to the deep ocean.  The steamer carried a huge cargo, 14,000 kilograms, of gold that was being transported from the gold fields of California.  The impact of this loss - what would be hundreds of millions of dollars in today's prices - was so great that a financial panic ensued when news of the sinking made it to land.

In the middle of the 19th century, the idea of finding, let alone recovering, the treasure of the Central America would have sounded like the plot of a Jules Verne novel, not a serious discussion.  As well as the vastness and treachery of the North Atlantic Ocean, there was the size and weight of the gold (some of it in large bars, some in sacks of gold dust).  In addition, the wreck occurred out beyond the continental shelf, where the seafloor plummets to depths of thousands of meters below the surface.  For reference, recreational scuba divers usually stay above depths of 20 meters and the deepest scuba dive ever successfully performed was 332 meters.  Setting this record required modern equipment and medicine as well as years of training and dozens of support personnel.  Many such attempts to reach record depths result in death.  Despite all this, however, coins and gold bars recovered from the wreckage of the Central America have been found and pulled up starting in 1988 and can now even be found in high-end coin shops, expos, and exhibits open to the public.  

You can probably fill in a lot of the story about this remarkable recovery yourself; the technological advances in robotics and deep-sea submersibles provided the eyes and arms capable of surviving the crushing weight of over 2,000 meters of seawater.  There are, however, a few more interesting aspects to the search and recovery.  The search for the wreck was enabled by modern statistical methods that drastically increased the odds of finding the wreck in the swirling vastness of the ocean.  The $13 million funding for the search was made through the formation of a company whose (fortunate) investors were sufficiently convinced by the plausibility of the fund-raising pitch.  Finally, the recovery was punctuated by a legal battle in which the discoverer, Tommy Gregory Thompson, had to defend his and his investors’ claim to the gold from dozens of insurance companies who had made payouts to policy-holders back in 1857 and therefore staked a claim to the treasure over 120 years later.  In short, finding sunken treasure ain’t easy, but one generation’s science fiction might be a later generation’s lived reality.

While the near-million bitcoins mined and untouched by Satoshi Nakamoto are the most famous example of a “dead” wallet, it’s estimated that over three million of the total 21 million supply of bitcoin are frozen and unreachable by virtue of the wallet's private keys being lost.  Everyone has probably heard or read stories of hapless unfortunates who threw out old hard drives or lost paper wallets.  Part of the thing that makes these stories so captivating is just how lost a lost private key truly is.  Just like the gold resting in the vast, deep, and dark ocean floor must have seemed unreachable to a prospective treasure hunter in the 19th century, the idea of searching for a private key in the elliptic curve used by the Bitcoin protocol is squarely in the realm of science fiction.  In order to even just describe the amount of possible values for a private key, one resorts to the same sort of bizarre analogies that astrophysicists use to describe things like the density of a neutron star or the number of planets in the visible universe.  In the case of Bitcoin’s secp256k1 elliptic curve, imagine all the grains of sand on Earth.  Now imagine that each one of those grains of sand is an entire Earth.  Now imagine all the grains of sand on all of those Earths collectively.  That number, the number of grains of sand on all the copies of Earth, is about the number of guesses that you have to have to try out before you’re assured of finding the private key associated with a public address.

Despite this, you will occasionally hear people talking about how quantum computing will be able to crack this and other computation problems, rendering Bitcoin insecure.  Some cryptocurrency projects even tout their “quantum computing resistant” protocol.  It’s worth looking into even if only to defuse the FUD.

There’s no shortage of good primers on quantum computing out there, so here’s the short, short, short version.  Quantum computing differs at the fundamental level from classical computing because of its probabilistic nature.  While a classical bit is in one of two states, it is either in the state 0 or the state 1, a quantum bit, or “qubit” can be in what’s called a superposition of 0 and 1.  Don’t worry about the weird bracket notation, it really just means “this is a quantum thingie.”

|qubit> = a|0> + b|1>

Here, a and b are numbers that tell you how likely you would be to measure the qubit in state 0 and how likely it would be for you to measure it in state 1.  The main point being that, just like Schrodinger’s simultaneously-dead-and-alive cat (|cat> =  c|dead> + d|alive>), the qubit is both 0 and 1 simultaneously.  Now, say we do a simple operation that flips the bits.  The flipped qubit would look like this, notice that the 1 and 0 changed place:

flip(|qubit>) = a|1> + b|0>.

So what?  Well, notice that we needed to just do this once to see what happens when we bit-flip both a 1 and a 0, whereas we’d need to do twice as much work on the classical bits - flipping first the 0, recording the answer then flipping the 1 separately.  

This is the magic of the quantum computer, instead of slowly working through individual inputs one after the other as you would on a classical computer, you can use this “Principle of Superposition” to load all the possible input states in a single register and do computations on them all at once.  Likewise if you want to test the properties of dead and live cats in your lab, you need two classical cats, one dead and one alive, but you only need one Schrodinger’s cat.

Specifically, for the relevant math of Bitcoin addresses, instead of guessing each of the possible 2^256 (crazy grains of sand number) ways to connect a public and private key one after the other which would take way longer than the age of the universe itself, a fancy quantum computer could load all of the guesses at once in a superposition state and do it in a single computation.  Scared?  Don’t be.

Just as the recovery of the S. S. Central America’s treasure took over a century of theoretical and technological advances to come to fruition, quantum computing is about as far along in its development as robotic submersible technology was in 1857.  Further, just as the robotic sub wasn’t the only thing required to find the sunken gold, a successful attempt at cracking Bitcoin’s key system will require a number of elements beyond just the quantum hardware.

First, there’s the theory.  You need a method, or algorithm, which can actually do the quantum computation.  Don’t let the fancy word bother you, you know what algorithms are and you know plenty of them.  In elementary school you were taught algorithms for things like multiplying large numbers and doing long division.  You might have been taught the Sieve of Eratosthenes, an algorithm for finding prime numbers by first crossing out all the multiples of two, then the multiples of three, and so on.  

If you do some programming, you might think this isn’t really a problem.  Algorithms can be efficient or inefficient, but there always seems to be a way to do something.  In fact, one of the joys of programming is that there are many, many ways of writing code to accomplish a given task.  However, if you know some computer science, you might remember that Turing’s theorem on the Halting Problem provides at least one example of something that’s uncomputable.  That is to say, Alan Turing provided us a proof that, for at least one particular problem, no algorithm can possibly exist.  It’s unsettling, but true: Certain things are uncomputable.  In fact, it’s even a bit trickier for quantum algorithms because of something we just glossed over, the fact that quantum mechanical objects are probabilistic.  Probabilistic means that when you measure your qubit, a|0> + b|1>,  to see what the output of the calculation is, you don’t get 1 and 0, you randomly get either 1 or 0 with probabilities based on the size of the numbers represented by a and b. Likewise, when you peek into the chamber you don’t see a dead-and-alive cat, your observation chooses, and measures, the state and you see just one of those two possibilities.

There are a few known algorithms for quantum computers.  The most important was published in 1994 by the American mathematician Peter Schor.  Schor devised an algorithm which can efficiently factor large numbers with a quantum computer.  Since the difficulty of factoring large numbers is the basis of the RSA encryption scheme, this was and is considered quite a triumph for theoretical progress in quantum computing.

At present, no one has actually implemented a quantum algorithm for finding private keys from public keys in an elliptic curve algorithm.  However, there seems to be good progress in extending Shor's algorithm to elliptic curves and every indication that it should be possible.

An additional complication exists in the fact that the public address is not the public key itself.  In fact, the public address is made from the elliptic curve’s public key by passing the latter through two different hashing algorithms; the ubiquitous SHA-256 and another one, called RIPEMD-160.  These steps weren’t intended for adding quantum resistance, rather they help make the public addresses more user-friendly.  As an unintended consequence, however, their use does mean that if all you know is a public address, you would also need to reverse-engineer the public key from the public address before even starting to look for the private key.  Getting the input of each of these hashing functions given their output is not easy.  In fact, finding the pre-image of a hashing function is an even more difficult calculation than finding the private key from a public key.  No classical computer could ever hope to do it efficiently and quantum computers using what's known as "Grover's Algorithm" aren't tremendously more efficient than their classical counterparts.  All told then, you need quantum algorithms to find the SHA-256 input given its output, another one to find the RIPEMD-160 input, and the quantum algorithm to reverse the secp256k1 elliptic curve calculation itself.  It should be noted that if you send a transaction, you do disclose the public key (not just the address), so once you send bitcoin from an address your private key loses two layers of its quantum resistance.  Spoiler alert: Do not lose sleep over this.

That’s the theory, or lack thereof.  Next we need to ask how the technology is progressing, or how are actual quantum computers in actual labs doing right now?  At present, quantum computers are performing their ghostly computations in rooms at all of the incumbent tech giants (IBM, Google, Intel, Microsoft) and a variety of startups too numerous to name here.  The number of qubits these machines have is measured in dozens compared to the trillions of bits that the RAM of an off-the-shelf personal computer might come standard with.  As a practical meter stick for their performance, the best quantum computers that can execute Shor’s algorithm might be able to compete with a clever middle-schooler in factoring integers.

Further, the stability of these machines and preparation of the initial states are plagued by interaction with the environment in a constant battle against entanglement (introduction of correlations you don’t want) and decoherence (loss of correlations and superpositions you do want) of the qubits.  These effects are really the boogeyman of the entire quantum computing enterprise and threaten to undermine the entire industry.  Quantum physicists do not fully understand the mechanisms of entanglement and decoherence which set the ultimate limits of how stable these systems are and determine when the environment destroys your carefully-prepared superposition or warps it in unknown ways to throw off your calculations.   Decoherence (as well as the humane society) is why there has never actually been a real Schrodinger’s cat.  The universe, in the form of the air and thermal photons and walls and cosmic rays, are constantly interacting with the cat, softly measuring it, and never allow it to cleanly split into the alive and dead branches of the superposition.  Very simple systems of tens of thousands of atoms, called “quantum-condensed gasses,” have been kept in quantum superpositions for about a second, but the information encoded and retrieved from them is very crude, certainly not a 256-bit number.  Maybe we’ll discover that it’s impossible to make quantum computer with the number of qubits and number of manipulations possible to do “real size” cryptographic calculations.

Finally, lets take a moment to consider the weird questions of the legal and social ramifications of cracking Satoshi’s (or any other “dead” wallet’s) keys.  Imagine, for a moment, that you are the one to do this.  The quantum computer you built in your lab, a jungle canopy of wires and piping, billowing heavy white clouds from the liquid nitrogen coolant, reports a 256-bit number.  You probably don’t believe it even after you check on a laptop that this private key does in fact get you to Satoshi’s public address.  Imagine the uproar.  Would a financial panic and crash ensue when it’s feared that the circulating supply of bitcoin might increase more than any time in its history, an unintentional Goldfinger attack?  Would the exchanges, or anyone really, accept any of the Satoshi coins for fiat or goods, fearing that they’re marked?  Just like the team that recovered the treasure of the S. S. Central America was blindsided by the legal claims on their find, from parties undeterred by the fact that over a century had passed, what lies in store for you?  Will an insolvent Japanese government claim that they nationalized the Satoshi treasure?  Does the cybernetic head of a 20th century Australian grifter floating in a jar of Cabernet sue you for the hoarde claiming it’s his?  Do you have the resources to defend your claim?  Does controlling a stupefying amount of wealth with a number sitting on your computer make you feel comfortable?  Or safe?

First, no matter how fast the techology progresses, it's unlikely is that anything but the abandoned wallets will be affected.  If the power of any sort of computing, quantum or other, starts to come near the threshold of breaking 256-bit elliptic curve cryptography, the Bitcoin protocol is not doomed.  Just as SegWit addresses were added to the protocol, and Schnorr signatures are being considered, Bitcoin can change to a new digital signature scheme that isn’t threatened.  The simplest way to do this would just be to increase the number of bits in the current signature scheme.  That having been said, every time this happens, users need to move their bitcoins to the new address format, so the stuck funds in these old abandoned wallets will remain vulnerable.

When might any of this happen?  I don’t know.  There’s no “Moore’s Law” heuristic for how fast quantum computing resources advance.  Further, there’s no guarantee that getting private keys from public addresses can even be done efficiently on quantum computers.  Finally, the only consistently-correct prediction about codebreaking is that every prediction is wrong (including my own).  A famous example comes from a 1977 issue of Scientific American magazine, which proposed an integer-factoring puzzle (essentially the puzzle was to decode an RSA-encrypted note).   At the time, it was believed that the puzzle would take “40 quadrillion years” to solve.  Somewhat ahead of schedule, it was solved 17 years later, in 1994, due to the widespread adoption of personal computers.  Back in 1977, the idea that hundreds of people could have thousands of processors each capable of millions of computations per second, and available so cheaply that they were willing to throw processor power to the factoring problem for fun was basically inconceivable. (Note: there was a prize of $100, about 15 cents per person, awarded for this amazing codebreaking accomplishment).  Who knows, maybe in a few years we’ll all have quantum chips in our computers designed to generate secure passwords and make the non-player characters in our video games act extra-unpredictable.  Maybe these chips can be leveraged to blow away all of our currently-secure technology.

In summary, Bitcoin wallets with lost private keys are unrecoverable for now and probably for decades to come.  For the same reasons, you shouldn’t fear “quantum computers” revealing your private keys any time soon.  Anyone going on about their quantum resistant blockchain is almost certainly a fool or scammer.  That having been said, just as Jules Verne’s fantastic vision of man prowling the uncharted depths ocean depths described in “Twenty Thousand Leagues Under the Sea” slowly came to life over the course of a century, there is a roadmap for both the theory and the technology of how one might use quantum computers to break into the millions of “stranded” bitcoin that exist even today.  While it won’t happen soon, if Bitcoin, or other cryptocurrencies continue their current pathway to widespread adoption, these lost wallets will become our treasure ships, incentivizing technological innovation and stoking the imaginations of the explorers of a virtual world of quantum bits and elliptic curves.