Last week, Google CEO Sundar Pichai reignited a quantum computing news cycle with his announcement of a “breakthrough” from the company’s new chip, Willow. Quantum computing is a difficult topic for even experienced technical writers (like us!), so we asked more experienced developers to tackle the subject. Coloradan Bitcoin developer, Hunter Beast, is one of the go-to voices to pierce through the noise.
With regards to Google’s Willow chip, Beast recently contextualized the breakthrough (and made it a little less scary).
But even if this recent news isn’t too much cause for concern, how do we even address the potential risk that a quantum computer would pose to Bitcoin? Bitcoin’s quantum threat is kind of like climate change: it’s a big looming problem that is largely misunderstood by the public due to its complexity, but it’s worth talking about and exploring solutions. Like climate change, it’s unclear what level of urgency we should have (or if it’s even something we should actually worry about). Luckily, we can more materially measure quantum computing’s threat to Bitcoin, and there are a few people already working on it.
In the interest of making this piece accessible, we’re doing a lot of handwaving and oversimplifying. But we still want to communicate the overall idea to you. We’re assuming that you know a couple basics about Bitcoin, such as the 101 of self custody, and that you have probably looked up a few transactions on a blockchain explorer.
First, what exactly is the risk of quantum computing for Bitcoin?
There are 2 ways that a quantum computer could threaten Bitcoin:
- breaking the cryptography that secures Bitcoin in an address you own.
- breaking the mining algorithm (SHA256) used to produce bitcoin blocks.
We are not going to address #2, as most experts consider that vector much less vulnerable to exploitation from quantum computers because it’s much more computationally expensive than #1 and would theoretically happen well after the first scenario.
What could happen is that someone uses a quantum computer to break the public/private key cryptography that secures Bitcoin. E.g. “Not your keys, not your coins” now becomes “If you have a quantum computer you reverse engineer someone’s keys.”
A quick primer on public/private key cryptography
When you set up a Bitcoin wallet and you write down a private key, the public address of that wallet is actually derived from that private key.
Even though many users may think 1 private key = 1 public address (public key), you can derive many public addresses from a single private key. Also there are many different ways to derive the public key from the private key. You might know these as different address types, e.g. a Segwit (P2SH) or Taproot (P2TR) or Legacy (P2PKH) address as some examples.
Technically, when you’re sending someone Bitcoin to any of these addresses you are using your private key to “unlock” your Bitcoin by signing a transaction that pays that Bitcoin to another address. It’s routine to go from private → public key, but theoretically impossible to get the private key from the public key.
However, a sufficiently powerful quantum computer could break the encryption that secures the one-way private → public key cryptography. This would allow an attacker with a quantum computer to see bitcoin in an address and derive the private key from the public address.
As Bitcoin has changed and soft forked over the years, we have introduced new address types. Some of these address types are more quantum secure. Generally, the older the address type, the more vulnerable, but this is not always the case. For example, the most recent soft fork (Taproot, November 2021) introduced the Pay-to-Taproot (P2TR) address type, which is actually one of the least secure due to the address encoding.
This is one reason why a lot of the conversation for Bitcoin and quantum computing centers on Satoshi’s ~1 million bitcoin stash. Satoshi’s bitcoin sits in an older Bitcoin address standard (Pay-to-Public-Key), which is probably the most vulnerable to quantum computing. Plenty of users outside of Satoshi, however, still hold bitcoin in P2PK addresses.
The two ways quantum computing can break Bitcoin addresses
There are two types of quantum computing attacks that could break Bitcoin’s public/private key cryptography: long range and short range.
A short range attack applies to transactions that are in-flight (i.e., a transaction that has been broadcast to the Bitcoin network but has not yet been included into a block). In such a scenario, a quantum computer would have to reverse engineer that transaction before it gets included into a block. Because Bitcoin has roughly 10 minute block times, the clock is ticking for the attacker. This time limit means that we probably won’t see a short range attack before a long range one.
A long range attack occurs when the attacker derives the private key from the public address of bitcoins at rest. In this scenario, a quantum attacker could theoretically have all the time in the world to reverse engineer the private key. This is what we are most worried about when we talk about a quantum threat.
Solutions for quantum proofing Bitcoin
So, what are we doing about it?
Frankly, until recently most of the discussion for addressing these types of quantum threats has been theoretical. Hunter Beast recently produced the first BIP with a proposal to create an address type that is quantum resistant.
The meat of the proposal introduces Pay-to-Quantum-Resistant-Hash, a new hashing algorithm for private/public keys that should sufficiently armor Bitcoin against quantum attacks. This BIP, which has not received a BIP number yet, would ideally be part of a “QuBit” soft fork, a series of upgrades that improve Bitcoin’s quantum resistance along several dimensions (including the examples described above).
While a proposal like Hunter’s is actually pretty straightforward at a high level, the details can get pretty hairy.
For example, introducing post-quantum cryptography to bitcoin would mean that the size of transactions increases. Bitcoin has a 4mb block size, but that 4mb is technically calculated by weighting the cost of different types of data differently in a transaction (Segwit in 2017 resulted in a net blocksize increase because we changed how weight is calculated in a transaction). Hunter suggests that, with post-quantum cryptography, we could consider a different weight calculation. This would technically result in a block size increase, which is a very controversial topic. It’s important to reiterate that we have changed this variable before and it has resulted in a block size increase (Segwit). Hunter says that this would not affect the net number of transactions in a block (a very different thing than the crux of arguments surrounding SegWit in 2016 and 2017).
“If we do a 16x discount [for P2QRH], that would bring blocks to about 10MB each, allowing for roughly 1-3,000 tx per block,” Beast said. “For more, read my article estimating chain growth rate.”
Hunter Beast’s BIP is “mostly ready to go, just needs more review,” he told Blockspace.
How urgently do we need to quantum proof Bitcoin?
How urgent is it that we address these threats? Here’s what Beast told us:
“We have no idea how urgent it is, and we have no idea what’s out there. Bitcoin could already be broken by nation states and we wouldn’t know for some time. The USG plans to have ECC phased out by 2035, so at the far end of the estimate, we have about 10 years.”
TL;DR: nobody knows, but 10 years would be a good finger in the air for what kind of timeline we should anticipate.
Bitcoiners pride themselves on thinking adversarially. Whether or not we prioritize the right adversarial questions will always be up for debate. However, it is good to have researchers exploring how to secure Bitcoin from quantum threats. Given that it almost certainly requires a soft fork, that means we should probably think much further out than many realize. It has historically taken several years to discuss, argue, and activate previous soft forks. What if it takes us 5+ years to come to agreement on this topic?
Further reading on quantum computing and its relation to Bitcoin:
- Quantum Computer as a field is obvious bullshit
- Deloitte on Quantum threats to Bitcoin
- Proposal to timestamp commitments to wallet secrets
Special thanks for technical review from Hunter Beast.
