Bitcoin Magazine

Show Menu

Bitcoin Is Not Quantum-Safe, And How We Can Fix It When Needed

In the past year or so, it has come to be a known fact in Bitcoin technical circles that Bitcoin, in its current form, is partially quantum-safe. The claim is that “used” Bitcoin addresses – that is, addresses which have both received and sent bitcoins, have their corresponding public key exposed on the blockchain, allowing quantum-enabled adversaries to break Bitcoin’s elliptic curve cryptography, whereas “unused” Bitcoin addresses, which may have received bitcoins but have never been spent from, do not have their public keys exposed, allowing them to benefit from the much stronger cryptographic guarantees of SHA256 and RIPEMD-160. As long as the first transaction spending from any Bitcoin address empties out all of the funds stored in that address to new addresses as change, the theory goes, Bitcoin should remain just as secure as before. In fact, since most wallets already try not to reuse addresses to increase privacy, for most users only minor software changes would be needed to satisfy the more stringent security condition, so adapting to quantum computing would be a breeze. This argument has been made by many people in the Bitcoin community, notably including myself. In reality, however, the argument has a fatal flaw.

Hashes and Curves

First, the technical background. In a Bitcoin user’s wallet, each of that user’s own Bitcoin addresses is represented by three distinct numbers: a private key, a public key and the address itself. The public key is derived from the private key by elliptic curve multiplication, and, given only classical computers like those that exist today, recovering the private key from a public key is essentially impossible. The address is derived from the public key by a series of three steps: applying the SHA256 hash function to the public key, applying the RIPEMD-160 hash function to that and finally adding a value called a checksum for error correction purposes (so that if you accidentally mistype a single character when sending to a Bitcoin address your money does not disappear into a black hole). The point of hash functions is that, just like elliptic curve multiplication, they are computationally infeasible to reverse; given an address, there is no way, aside from the brute force approach of trying all possible public keys, to find the public key that the address is derived from.

Quantum computers have two major tools that make them superior to classical computers in breaking cryptography: Shor’s algorithm and Grover’s algorithm. Shor’s algorithm is mainly useful for factoring numbers – for example, given the number 1728499, figuring out that the number is composed of the factors 1129 * 1531. With seven-digit numbers, the problem can even be solved on paper with enough patience, but if the numbers are hundreds of digits long quantum computers are required. In fact, the difficulty of factoring very long numbers is the basis of RSA, the oldest public key encryption algorithm and one still in use today. Grover’s algorithm is far more generic – given a list of numbers and a mathematical property, it can figure out which one of those numbers satisfies the property. A modified version of Shor’s algorithm can crack elliptic curve cryptography as well, and Grover’s algorithm attacks basically anything, including SHA256 and RIPEMD-160.

However, the two algorithms differ drastically in just how efficient they are. Shor’s algorithm reduces the runtime of cracking elliptic curve cryptography from O(2k/2) to O(k3) – that is to say, since Bitcoin private keys are 256 bits long, the number of computational steps needed to crack them goes down from 340 trillion trillion trillion to a few hundred million at most. Grover’s algorithm, on the other hand, does not offer anything close to so drastic a speedup. Rather, it simply provides a modest reduction from O(2k) to O(2k/2). In the case of RIPEMD-160, the weaker of the two hashes used to create a Bitcoin address, this means that the number of steps needed to recover a public key from an address goes down from 1.4 trillion trillion trillion trillion to … 1.2 trillion trillion. Somewhat easier, but still thankfully impractical. As described above, “used” Bitcoin addresses from have an exposed public key, so it is the easy challenge of cracking elliptic curve cryptography with Shor’s algorithm that is the bottleneck. “Unused” Bitcoin addresses, on the other hand, expose only the address itself, so it is the RIPEMD-160 Grover problem that poses the weakened, but still insurmountable, challenge.

So What’s the Problem?

Here is where the above logic goes wrong. Everything about quantum computers in the above two paragraphs is, given public knowledge, is essentially correct, and if a Bitcoin address is truly unused, then indeed, even given quantum computers, any bitcoins lying inside are fine. However, the challenge is, how do you actually spend the funds? In order to release the bitcoins sent to that address, it is necessary to create a Bitcoin transaction, and that transaction must include a signature and a public key to verify that it was the owner of the private key that signed it. However, here lies the problem. By making that transaction, you have just released all of the information that anyone with a quantum computer needs to fully impersonate you, right on the spot. Without quantum computing, this is impossible, as Bitcoin’s elliptic curve signatures only have enough information to recover the public key, not the private key. With quantum computing, elliptic curve signatures are as flimsy as a digital sheet of paper.

If you send a transaction spending all 100 BTC in address 13ign, with 10 BTC going to 1v1tal to pay for goods and 90 BTC change going back to your new address at 1mcqmmnx, the first node that you send the transaction to can replace the change address with whatever they want, recover the private key from your public key, and forge your signature. The only way to get around the problem is essentially to send the transaction directly to a mining pool, like BTCGuild or Slush, and hope that the mining pool will be honest and place the transaction directly into the blockchain. Even then, however, you are vulnerable to a Finney attack – a dishonest miner can forge your signature, create a valid block containing his forged transaction continuing the blockchain from one before the most recent block (the one containing your transaction), and, since the lengths of the old and new blockchains would then be equal, the attacker would have a 50% chance of his block taking precedence. Thus, safe transactions are essentially impossible.

Lamport Signatures: A Solution

Basically, the purpose of hash functions is to provide us with the mathematical equivalent of a lock. Publishing the hash of a value is similar to putting out a lock in public, and releasing the original value is like opening the lock. However, once the lock is open, it cannot be closed again. The problem is, however, that locks by themselves cannot make a secure digital signature scheme. What elliptic curve cryptography provides, and SHA256 and RIPEMD-160 do not, is a way of proving that you have the secret value behind a mathematical lock, and attaching this proof to a specific message, without revealing the original value or even making the proof valid for any other message than the one you attached. In Bitcoin, the message in question is a transaction. When your Bitcoin client sends a transaction to the network, what it is really doing is sending a mathematical proof of the following fact: this transaction, which states that I am sending this amount of money to this address, was constructed by someone in possession of the private key behind the Bitcoin address I’m sending from. This is the basis for the transactional side of Bitcoin’s security.

However, there is a construction that enables us to solve this problem without RSA, elliptic curves or any other traditional public-key cryptographic system: Lamport signatures. A Lamport signature is a one-time signature that gets around the lockbox problem in the following way: there are multiple locks, and it is the content of the message (or rather, the hash of the message) that determines which locks need to be opened. If someone tries to forge your message, it is almost certain (read: the sun will run out of hydrogen before the other scenario happens) that the Lamport signature scheme will require them to open at least one lock that you did not open already – which they, lacking the unreleased secret values, will not be able to do.

How Lamport Signatures Work, In Detail

Lamport signatures may seem technically complex, but because they only have one ingredient – the hash function (in this case, we’ll use RIPEMD-160) they are actually one of the most accessible cryptographic protocols for the average person to understand. The algorithm works as follows:

  1. Generate 160 pairs of 160-bit random numbers (you can make them all from a single seed with RIPEMD-160: RIPEMD-160(seed+”1″), RIPEMD-160(seed+”2″), etc). These values, or in some implementation the seed used to generate them, are your private key.
  2. Hash all of the random numbers (eg. with RIPEMD-160), and publish all 160 pairs of hashes. These are your public key, and will be needed by the network to later verify your signature.
  3. To sign a message, calculate the RIPEMD-160 hash of the message, and then depending on each bit of the hash release the secret number behind the first or second hash in each pair. If the bit is zero, open the first hash, and if the bit is one open the second hash.

Under this scheme, a Bitcoin address will still be the SHA256+RIPEMD-160 hash of the public key; the only difference is that the public key will consist of 320 hashes rather than an elliptic curve point. A transaction will include the public key and the signature, just like today, and, once again just like today, verifiers will check that the public key matches the address and the signature matches the message and the public key. The signatures are unforgeable; even with Grover’s algorithm, it will take 280 steps for an adversary to construct a fraudulent transaction that requires them to reveal the exact same 160 secret numbers that you already revealed, or an adversary can take 280 * 80 steps to simply crack all the hashes. Both numbers are in the trillions of trillions of computations.

The only change in behavior that will be needed is for people to start using addresses only once; after two uses, the security of the Lamport scheme drops to 240, a value which might still be safe against quantum computers at first, but only barely, and after three uses it’s as weak as elliptic curve cryptography. Theoretically, however, even this can be partially overcome; the Merkle signature scheme builds off of Lamport’s idea to create signatures which can be used tens or hundreds, or potentially even thousands, of times before the private key needs to be retired. The only limit to the maximum number of transactions per address is basically a question of limiting blockchain bloat.

Given what is currently public knowledge, quantum computers are still far away; the most powerful quantum computer to date managed to use Shor’s algorithm to factor the number 21. However, sudden advances are always possible, and we always need to have a plan of what we can do if Edward Snowden decides to leak out that the NSA has fully functional quantum computers hiding in a secret data center. We probably cannot handle such a sudden event, but we certainly can handle cases where we get even a month of advance warning. The solution is this: as soon as a quantum pre-emergency is declared, everyone should move their wealth into a 1-of-2 multisignature transaction between an unused, old-style, Bitcoin address, and an address generated with the new Lamport scheme. Then, developers should quickly create the Lamport patch for as many Bitcoin clients as possible and push for everyone to upgrade. If the whole process is done within weeks, then by the time quantum computers become a threat the bulk of people’s bitcoins will be in new-style Lamport addresses and will be safe. For those who still have their wealth in old-style addresses by then (unused old-style addresses that is; by that point coins in used old-style addresses could trivially be stolen), a few established organizations will agree to serve as trusted nodes, using the Merkle signature scheme to add an additional signature to transactions sending from old-style addresses to new-style addresses. To prevent network fraud and Finney attacks, the new Bitcoin rules would require all transactions from old to new after a certain point to be signed by these authorities. The authority system will introduce centralization, but it will only be a temporary emergency measure, and after a few years the system can be retired entirely. From there, we lick our wounds, pick up our losses and move on to enjoy some of the more wonderful things that quantum computing has to offer.

Get Top Stories Weekly

We respect your email privacy

  • Jaymaxx

    Firstly, I am really pleased this stuff is being seriously considered already. Quantum computing is the elephant in the bitcoin vault.

    Secondly, this should be two articles – there’s a part in the middle there, that goes to the math of the actual proposed solution, that really should have been stripped out to a link or something. (I’m NOT saying the techy quantum background stuff should be removed, just consider your audience, which is presumably relatively brainy folk who aren’t cryptographic math experts – I would suggest the targeted folk as those who know that ellipses math provide some sort of one-way encryption, but thats about it)

    Thirdly, The article is a bit confusing in the early parts, because the article uses the idea of a bitcoin address being ‘used’ to mean ‘paid out from’ (thus revealing the full public key) – whereas language and common usage would suggest that a BTC address is ‘used’ the moment you tell someone (or your own wallet software tells itself) to use a BTC address to RECEIVE coins. [I suggest a quick edit to replace ‘use’ with ‘use to send’ as appropriate]

    But mainly, thank you Vitalik – a really excellent piece – and (somewhat oddly – it’s obvious in hindsight) I now understand why BTC addresses are hashes, and not just the wallet public key.

    [EDIT to note: clicking on the author name at the article foot, UNLIKE at the article head, take one to a list of articles by the same author, discovering this has rendered my suggestion below a bit presumptuous and meaningless]

    BitCoinMag, you should get this guy (plus an editor) to write some more technical crypto BTC articles!

    • Vitalik Buterin

      Thank you for your comment! I clarified the meaning of “used” and moved out the techy Lamport explanation.

      Also, there is another reason why BTC addresses are hashes, and a mundane one: to save space. Back when Satoshi first created Bitcoin, he did not know about compressed public keys (basically, the y coordinate of an elliptic curve point can be inferred from the x coordinate with one extra bit), so instead of pubkeys being 257 bits long as new ones generated by bitcoind are today pubkeys were 512 bits long – 256 bits for the x coordinate and 256 bits for the y coordinate. 512 bits is 87 base-58 characters, and 87-character Bitcoin addresses are a bit too unwieldy. But then again, Satoshi did lots of things “just in case” – for example, using SHA256 + RIPEMD-160 and double-SHA256 instead of just SHA256 as the hash algorithm.

  • Or

    Great article. Thanks!

  • Seth

    Why not just implement this now just in case? Is there any reason not to switch as soon as possible?

    • Vitalik Buterin

      1. Addresses would become finite-use, as opposed to infinite-use as they are now
      2. A Lamport signature takes up 160 * 2 * 160 = 51200 bits = 6.4k bytes. I’ve come up with a way to reduce the Lamport signature to 3.2k, and the fact that I came up with such an improvement in my head suggests that really smart _actual cryptographers_ have probably gone much lower by now, but even a 1k signature constitutes an immense amount of blockchain bloat.

      • Seth

        I just hope that it gets implemented well before we get near quantum computing capability. I think 4 weeks advance would be like playing Russian Roulette. Better 4 years advance or more, in my opinion.

      • milancio

        There are already proposed quantum-resistant public key cryptosystems with much shorter keys – e.g. this one:, which is based on “supersingulare elliptic curve isogenies” with keys up to 1024 bits. The math there is not for faint of heart, though.

  • Chris Pacia


    While looking into this, I came across this paper offering up an improved merkle signature scheme. It claims it can sign up to 2^40 messages with “reasonable signature and key lengths.”

    • Vitalik Buterin

      Thanks for the link! Okay, Winternitz signatures do seem definitely more efficient, and I like the fact that they’re relatively intuitive.

  • AK Coins

    Here is something less technical. No company is capable of quantum computing. The technology does not exist. There is one company called D-Wave that claims to be able to perform some type of “quantum computing”. Many critics claim that it is nonsense.

    In some speed tests, “quantum computing” computers are faster. In other speed tests, they are slower. Until a company comes out with legit quantum computing technology, I wouldn’t worry about it.

    Secondly, when this technology comes out, there is no way it will be put to use cracking the Bitcoin network. There are much bigger fish to fry. I wouldn’t worry about a couple of BTC floating around.

    AK Coins

    • J.W.

      Even in the event bitcoin is huge at the time QC achieves a breakthrough, one assumes it is more likely to be a well-publicized and funded one, with an interest in bringing their project into the world without such a stigma. Probably they may have their net worth in bitcoin.

  • dplsurve

    Quantum computers could “theoretically” effect a number of industries including the banking sector. So bitcoins will be the least of our worries.

    I’m really not worried so much, mainly because the same computing power could also be used to aid in creating stronger cryptology as well. There are a number of other countries including China, Russia and India, ect. who are not just sitting around waiting for their secure systems to be hacked by quantum computing.

    There will be pluses and minuses on both sides of the table as we learn more about this technology and overall all we’ll learn how to use it to make our encryption schemes even more secure.

  • Robert

    Nice overview. Thanks for your explanations. I also believe that the system should be made QC save as soon as possible. Recently I heard an expert podcast about the history of eavesdropping with the final conclusion: Until now the efforts undertaken by the adversary have been almost always underestimated.

  • Dhillon

    This is from Bruce Schneier’s 1996 book, Applied Cryptography:

    One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant.
    Given that k = 1.38×10-16 erg/°Kelvin, and that the ambient temperature of the universe is 3.2°Kelvin, an ideal computer running at 3.2°K would consume 4.4×10-16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

    Now, the annual energy output of our sun is about 1.21×1041 ergs. This is enough to power about 2.7×1056 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2192. Of course, it wouldn’t have the energy left over to perform any useful calculations with this counter.
    But that’s just one star, and a measly one at that. A typical supernova releases something like 1051 ergs.(About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be
    cycled through all of its states.
    These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And
    they strongly imply that brute-force attacks against 256-bit keys will
    be unfeasible until computers are built from something other than matter
    and occupy something other than space.

    To recap, if you could harness all the energy from a supernova and
    channel it into an ideal computer, you still couldn’t brute force a
    typical encryption key. Needless to say, if you are going to break
    commercial encryption algorithms you’re going to have to attack the
    underlying math.

    • Robert

      This probably holds true only for classical computers. Using quantum computers you try to make all operations reversible. Thus, you only need a infinitesimal amount of energy to make your computation run in the right direction (towards your result). As far as I remember the prime-factorization algorithm by Shor is reversible.

  • Dhillon

    They have to attack using side channels!!

  • Brad

    Dude you are a genius. You are so young too it is incredible you are already thinking of this stuff.

  • J T

    I read this differently, quite differently. To me, you outline the economic incentive (albeit you crushed the incentive to some degree). And what is seemingly likely is quantum computing will come about at nearly the same instant that bitcoin goes mainstream.

    I have always felt this is obvious since I started to at all understand this technology in relation to economics.

    For example, if we didn’t today have the solution you provided or the safe plan you prescribe…then it could be view from a perspective that bitcoin’s function in the grand scheme of things is to incentive someone to create a quantum computer.

    It may not be that simple, but I cannot help but feel such an observation or point is not irrelevant. Its not different than suggesting bticoin would not be so popular or valuable if our current banking system was not so terrible and lacking-such flaws create the “intrinsic value” for bitcoin imo.

  • Ashley Fulks

    Good work Vitalik. It’s important Bitcoin has a solution to this sooner than later and with minds like yours on the problem we are going to be alright.

    P.S. It was good to see you in Vegas and I cherish the Bitcoin Magazines I bought off you with bitcoin. Cheers!