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

### 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.

BTC: 1FxkfJQLJTXpW6QmxGT6oF43ZH959ns8Cq

LTC: LaBhvWiAP7msku6w8QSQ5G7omVWMF3uxJC

#### Get Top Stories Weekly

• 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.

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.

• 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.

• Vitalik Buterin

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

• 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.

• http://blog.riemann.cc/ 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.

• http://blog.riemann.cc/ 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!!