Response to "The End of Cryptocurrency"

No, sorry, your quantum cluster won't destroy Bitcoin

photo by Adi Goldstein, curtesy of Unsplash

A friend of mine sent me this video, explaining why the Atom quantum cluster spells the end of cryptocurrency and bitcoin, which I hate to link because I don't want to drive traffic and engagement to FUD, but since his audience is so for context, here it is.

This video in particular struck me because the author knows just enough about these topics to sound like he knows what he’s talking about and to convince people like my friend who don’t know the technical details enough to see why he’s wrong.

In this case, he's ignoring two very important things that I can hopefully explain without a lot of technical detail:

1. There is a cost to running these quantum computers that must be lower than the profits gained from the attack

2. There is a significant difference between simple public/private key encryption and the many ways payments can be secured on the Bitcoin network (like P2SH/multisig)

He's right that some cryptocurrencies are going to be adversely affected by quantum compute. I won't argue for random cryptos that are most certainly broken, and some aspects of Bitcoin may need to upgraded eventually, but I can explain why he's completely off the mark on what he says about Bitcoin specifically.

If you are simply talking about public/private key encryption, sure there are ways that quantum poses a risk, and there are mitigations already being rolled out.

There was a very old way of spending Bitcoin called P2PK (pay to public key), which allows it to be sent to the public key itself, but current addresses, in the worst cases, use P2PKH, or pay to public key hash, which does not expose the public key until the moment funds are sent from the address and only while they sit in the mempool for processing. If you do not reuse addresses, and you have never spent funds from a P2PKH address, the world does not know the public key. P2PKH is considered legacy, but there is still a ton of Bitcoin on the ledger attached to these addresses, so let's dig into them a bit.

Let's say you want to try to steal the 530 BTC that are currently sitting in this address: 1111111111111111111114oLvT2.

Well, that looks like a really simple address to crack, right? Look at all those 1's! Let's explore that. First, this is not the public key, so you cannot just use Shor's algorithm with a sufficiently large quantum array to factor it to the private key because this isn't even the right number to factor. And once we get there, it's another huge task for quantum that requires significant qubits that don't currently exist on the market, about 2,330 (in theory, assuming they work consistently—more on that later).

This bitcoin address is a ripemd160 hash of the sha256 hash of the public key. So if you want to use Shor's algorithm to crack it, you first have to use Grover's algorithm to break sha256 and ripemd160 in two additional runs of your quantum cluster--much more costly. But let's assume that you can break these things in a positive cost to benefit way and go over the steps of how the address was created and how you would have to attack it just so we can be clear on what this would take. And note, that Bitcoin payment addresses are a little more complicated than just these hashings of the pub key but the other steps in P2PKH are simple enough not to require major compute.

This is (roughly) how the address was created (giving us some variable names so we can discuss this without using word soup).

shaPub = sha256(pubKey)

address = ripemd160(shaPub)

So the steps to reverse this to find the pubKey look like this:

1. Spin up the world's largest quantum compute datacenter, programmed with Grover's algorithm to get the ripemd160 source of address (get the value that you had to pass into ripemd160 hash in order to get a result of 1111111111111111111114oLvT2). This gives you the value of shaPub (after a very long and expensive quantum compute job)

2. Use that same expensive cluster to then get the sha256 source of shaPub (get the input value required for sha256 to return the value of shaPub), this will give you the pubKey (again, very long and expensive)

3. Use that cluster again with Shor's algorithm to factor pubKey to find privKey (oh, the time and money!)

4. Use a regular computer to sign and issue a network transaction to steal the funds

5. Hope that the owner of that address isn't programmatically watching the mempool for transactions containing keys they own and that they don't have automation in place and miners setup to replace the transaction (using replace-by-fee), moving their funds to a different address before your transaction can go through which would waste all the time and money you spent trying to get at these funds (they most certainly are watching and have this automation and are running their own miners because you are trying to attack addresses with very large balances)

6. And finally, realize that you were an idiot and tried to hack into a bitcoin burn address that has no private key because you don’t understand how any of this works.

The Cost

This attack (assuming you find a real target) requires running several operations on large quantum compute clusters, which takes a long time, is absolutely NOT free to run, nor is it stable/reliable yet (the record for largest prime number reliably factored with Shor’s is still 21). The current cost of running quantum compute is non-trivial. And there are major differences between physical qubits (subject to decoherence) and logical qubits (idealized), quantum annealing (such as D-Wave), and other types of quantum systems--you need to really research this stuff if you want to plan an attack without throwing a lot of money at nothing. If you think you can run the world's largest physical qubit quantum computer cluster at a cost below the reward of what you are attacking, you might want to rethink your plans. You could spend millions of dollars trying to hack one address and not get to the result because these types of clusters haven’t even been able to factor the number 35 (because the decoherence at higher qubit levels is so bad). A few researchers have come out with higher number factorizations but they are cheating by using classical computers to do part of the computation, which will not work when you get to large enough numbers like bitcoin keys (these attempts are invalid and do not break the record for quantum factoring because they rely on classical compute shenanigans that only work with smaller numbers).

But maybe a bigger address is vulnerable like 12ib7dApVFvg82TXKycWBNpN8kFyiAN1dr, which has $1,078,252,625 worth of bitcoin in it as of this writing—surely you could spend less than $1B to run this attack, right? Or maybe target the famous 1Feex address, which currently has $2.9B worth of bitcoin in it. Maybe build your own quantum compute company for this purpose. They are also relying on the simple P2PKH security method, so the process is the same. Well, the owner of this billion dollars worth of bitcoin clearly doesn't think that the cost-to-benefit ratio exists yet for quantum to be a threat to these addresses--and you will absolutely see that as quantum grows, these savvy players will act, and balances will move out of P2PKH that exceed the cost of attack. So, sorry to break it to you, it doesn’t matter how many laypeople heart your comments on TikTok rebuttals, there are billions of dollars that are saying you are wrong.

Now, not everyone will or even can move their bitcoin from P2PKH--Satoshi mined a lot of bitcoin (1.1 million) that have not moved since, and very likely Satoshi is not around, has lost those keys, or never saved them to disk because the mining was experimental and the payment addresses may have been programmatically generated and thrown away. Many savvy players in the market are watching the mempool for movement of these funds and when they finally do move, it will shake the market like it has never been shook before—alerting anyone with smaller balances to move a little further down the road. The information will be available instantly when the weakest of keys finally become vulnerable.

The Absurd Argument of Fractional Theft

The video author makes the argument that attackers are going to steal just a little bit of bitcoin from people's wallets (not enough to be noticed). How absurd is that? Bitcoin isn't 49 cents worth of pennies floating in your pocket that you won't notice turned into 48 pennies, or a rounding error bug in your bank account stealing fractions of a cent. Bitcoin owners watch the contents of their wallets programmatically. They will know as soon as any amount of Satoshis are moved from their wallets—the clever ones will notice as soon as a transaction even attempts to move funds in the mempool. This idea of an attack assumes that the cost of quantum compute is free and that nobody will notice the security is compromised and it's somehow worth it to just take a little bit. The argument is absurd.

Why would you try to steal a tiny bit of someone's bitcoin, when you could crack Satoshi's keys and sign messages to the internet as Satoshi? You would effectively be the CEO of a $648B company. Additionally, nobody would be able to contest you on the rights to the funds because nobody else has these keys. You could target 1NSPqTZae3bCdiCNWSbkE4qBxfqjybA93S, one of the early block reward addresses (P2PKH) and then just sign messages to the internet saying things about Bitcoin or other cryptocurrencies or about Satoshi that would move markets. Better yet, if you can hack into any bitcoin address, hit up 12cbQLTFMXRnSzktFkuoG3eHoMeFtpTu3S, the famous address where Satoshi sent 10 BTC to Hal Finney, which would mathematically prove your identity to the internet without a doubt. You would be immensely powerful. Stealing pocket change not only would be noticed as soon as you did it, it would be the most absurd usage of spending the resources to break P2PKH.

Additionally, there are about 4 million bitcoin that are currently assigned directly to public keys or to P2PKH sources that have been used multiple times. These are the easiest target for quantum to attack since you don't need to do the multiple Grover's steps and only need to use Shor's to factor the public key into the private key. When the cost of running this attack becomes a positive equation, we will see these funds move. These addresses are the canary in the trillion dollar bitcoin mine.

In theory, an attacker could also try to skip the Grover's steps and only use Shor's by attacking transactions as they wait in the mempool, but this would require running the quantum attack during the window where funds wait to be processed. In order to achieve this rapidly, you need a massive quantum compute cluster. This would take 317 × 10^6 physical qubits (or 317,000,000 qubits, far more than Atom’s 1,000+ cluster) to break the encryption within one hour (assuming the attack target is not scheduled to process within the next block). See Webber et al.

Higher Security

We've now seen how to reverse a P2PKH into a pubKey, hoping to afford using Shor's algorithm to obtain the private key, but this method is not so easy when you use other methods of security like P2SH (script addresses that start with a `3`), P2TR (taproot, starting with `bc1p`). These newer systems offer multiple layers of security that require a lot more than simply identifying a single public key and factoring the private key to match.

All you really need to do to not be eaten by the bear is to run faster than all the people who are lazily enjoying a picnic behind you. Proper self-custody of bitcoin and key management is hard. It’s not for everyone, which is why so many choose to hold Bitcoin in a custody service like Coinbase, allowing them to do the work of staying out of the bear’s grasp.

Ultimately, there are many major societal changes that would surface well before multisignature protected Bitcoin would be even remotely at risk, and so many mitigations available that quantum compute is not a threat for the foreseeable future.

There are several valid ways to add even more security if you are concerned about quantum attacks:

1. The simplest: don't assign large balances to a single address (don't be a valid cost-to-attack target). With an HD wallet, you can create as many addresses as you want and keep low (sub-1 BTC) balances in each. The cost to attack you will not be worth it vs attacking someone else for the foreseeable future.

2. Use multisig, requiring the signature from multiple private keys to spend funds--now they have to identify multiple keys that go with each other in order to move the funds, which turns this already astronomical problem into a multiverse problem.

3. Watch the large addresses and see where the money flows. You can be sure that major companies like Coinbase and Binance are smarter about this than you are and if you are storing your bitcoin in the same way they are but with smaller address balances (not in the 1000+ per address range), you are probably safu (few get this) with your self-custody in terms of quantum risk (you may have other problems).

4. Not typically recommended (and I’ll probably get destroyed in the comments by the hardcore folks), but if you really don’t think you can keep up with the security requirements of having sovereign control of your finances, maybe just put your bitcoin in Coinbase or CashApp and let them worry about technological advancements—maybe it’s too soon in the adoption curve for you to worry about this.