Why Quantum Computing will not Crack Blockchain Burner Addresses

This article is sponsored by Resonance Security.

There are ongoing concerns about the impact that quantum computing will have on blockchain, possibly in the not-too-distant future, given the rate at which advancements in the technology are being announced. The main concern is that quantum computing enables the discovery of private keys to blockchain addresses in short periods of time, thus putting the digital assets stored against those addresses at risk of theft.

A second concern involves burner addresses, which are public blockchain addresses for which it is clear that the private key is not known by anyone, and therefore any assets sent to them are supposed to be irretrievable. This makes them black holes with which to dispose of unwanted tokens and crypto.

It is these burner addresses that I will be looking at in this article, and if you don’t have enough time to read it, the answer is: no, quantum computers do not put burner addresses at any more serious a risk than conventional computers do.

Burner addresses

Blockchain addresses such as the zero address on Ethereum (0x000…000), and the Bitcoin Eater Address (1BitcoinEaterAddressDontSendf59kuE) hold millions of dollars worth of tokens and crypto. If the private key to either were to be discovered then those assets could be spent, for example, by transferring them to a crypto-exchange and selling them.

But first — how can we be sure that the Ethereum zero address and the Bitcoin eater address are burner addresses?

They’re both clearly made up, rather than the product of picking a private key and deriving an address. And producing blockchain addresses uses cryptographic hash functions, which are like random number generators: the output cannot be predicted in advance.

For both Bitcoin and Ethereum, the process of producing a blockchain address starts by picking a 256 bit number as the private key. The private key is used to derive a public key using the Elliptic Curve Digital Signing Algorithm (ECDSA).

The public key is then hashed. In Bitcoin this involves a SHA-256 hash of the public key, followed by a RIPEMD-160 hash, and then some further operations to produce a checksum that is added to the end of the address.

In Ethereum it involves a Keccak256 hash of the public key and taking the last 160 bits. In both cases, this means that the odds of a randomly chosen private key producing a specific desired address are 1 in 2¹⁶⁰, which would involve about 1.5 trillion trillion trillion trillion tries.

So the good news for any would-be burner address hacker is that there are 80 thousand trillion trillion private keys that produce a given burner address. The bad news is that for every key that produces the burner address, there are 1.5 trillion trillion trillion trillion that do not.

To put this in context:

• The sun is expected to die in about 7 to 8 billion years, which is approximately 20,000 trillion seconds from now.
• To find a private key that generates one of the above burner addresses before the Earth is engulfed by the dying sun would require a conventional computer to execute more than a billion trillion trillion tries a second.
• The entire Bitcoin mining effort is only performing a billion trillion hashes per second.
• So we are talking about a computing effort equivalent to a trillion (that’s 1,000,000,000,000) Bitcoin mining networks running from now to the end of the solar system to find the private key for one single burner address.

The numbers are that big.

Quantum computing to the rescue?

Ah, but doesn’t quantum computing allow us to magically side-step all those standard linear computations through the mysteries of the quantum realm?

Well, we have two major tools in quantum computing that improve speed:

• Shor’s algorithm (discovered in 1994)
• Grover’s algorithm (discovered in 1996)

Just as Alan Turing was able to hypothesize about conventional computing well before the first physical computers could be built, quantum computing research has been taking place for decades without actual quantum computers being available to run the algorithms. And although over a hundred other quantum algorithms have been discovered in the subsequent thirty years, Shor’s and Grover’s algorithms remain by far the best.

Cracking ECDSA

The first tool, Shor’s algorithm, exponentially speeds up the factoring of numbers, and a modified version of Shor’s algorithm can be used by a quantum computer to break ECDSA. This is the signing algorithm that is used by both Bitcoin and Ethereum to sign transactions that transfer cryptocurrency (and in the case of Ethereum, tokens).

It reduces the number of tries required to find a private key for a public key from trillions of trillions of trillions, which is infeasible, down to less than a billion. If your quantum computer can make a thousand attempts per second, cracking an ECDSA public key to obtain the corresponding private key would only take a week or two.

However, this activity requires the ECDSA public key, which for standard blockchain addresses have been hashed with what is effectively a 160 bit hash function (RIPEMD-160 for Bitcoin, and Keccak-256 with 96 bits thrown away for Ethereum). For burner addresses, ECDSA is initially irrelevant. We first have to find a mystery number X that hashes to our Bitcoin or Ethereum burner address.

Only then can we apply Shor’s algorithm to X to find the private key that produces the burner address.

And hash functions are still, to the best of our knowledge, quantum secure. Shor’s algorithm doesn’t help with hashes, because they don’t involve factorization, and the best known quantum tool for reversing them is called Grover’s algorithm.

Cracking hash functions

Whereas Shor’s algorithm speeds up factorization exponentially, Grover’s algorithm speeds up searching across a list, but it only does so quadratically. Cracking a hash function, that is, finding an input to a hash function that gives a desired output, is a brute-force search. You just have to keep trying different inputs until you find one that gives the output you want. If a hash function has an output of 160 bits, then you are almost guaranteed to find a suitable input with 2¹⁶⁰ tries. As we discussed above, that in involves a lot of failed attempts.

Grover’s algorithm reduces the number of tries by about a square root of the linear conventional method, so from 1.5 trillion trillion trillion trillion to roughly 1 trillion trillion. That’s a significant improvement, but it only takes us from the realm of the completely insurmountable to the impossibly unachievable.

Instead of re-purposing the whole of the Bitcoin mining network to crack the RIPEMD-160 or Keccak-256 hash function for the rest of the life of the solar system, we now only need to and run it for 64 thousand years.

After converting the million or so miners that are out there into quantum computers.

In short, hash functions are quantum-secure. Therefore, so are burner addresses.

Coda: Ethereum contract addresses

At this point some of you may have the thought, “What if, instead of looking for a private key that derives an Ethereum burner address, I look for a private key that derives an externally owned Ethereum address that can deploy a smart contract with a burner address? The smart contract could contain code that allows me to transfer out the assets it holds!”

Those of you who did think of that get a bonus point from me for lateral thinking. Unfortunately the smart contract approach is also doomed to fail:

• Smart contracts deployed with CREATE are computed by Keccak-256 hashing a concatenation of the deployer address and a nonce, and using the last 160 bits.
• Smart contracts deployed with CREATE2 are computed by Keccak-256 hashing a concatenation of the hex number 0xff, the deployer address, a salt, and a Keccak-256 hash of the bytecode to be deployed, and using the last 160 bits.

As you can see, once again a hash function needs to be cracked to get a specific desired contract address, so we are back to Grover’s algorithm and running the world’s largest ever proposed quantum computing system for sixty-four millennia.