Can quantum computing break Bitcoin?

Let me start this piece off with a disclaimer. I don’t have a brain anywhere near big enough to come close to understanding what quantum computing is.

Having said that, I am super curious as to its potential impact on Bitcoin and as a result, it is something I have spent a bit of time researching in my spare time recently. You know, “for fun”. In fairness, I spent half a day in an airport earlier this month, so what was I meant to do to kill time?

I figured I would put together a piece trying to sum up my research and explain what quantum computing is, as well as its implications for Bitcoin, in simple terms so other normal folk like me – the non-prodigious scientists, if you will – can comprehend it. Here is what I found.

What is quantum computing?

Quantum computing is a rapidly-emerging technology which leans on quantum mechanics to solve problems which are too advanced for “normal” computers. It deals with the interaction and motion of sub-atomic particles, and it has evolved to a place that most scientists could never have imagined even a few years ago.

In essence, think super-powerful computers which are capable of solving extremely difficult mathematic and cryptographic puzzles wayyyyy quicker than classical computers today. Hint hint.

What has this got to do with Bitcoin?

Bitcoin is based on something called asymmetric cryptography. This means that it works off a principle called a “one-way function”. There are two vital aspects to every Bitcoin wallet: a private key and a public key. If you have a private key, you can deduce the public key easily. However – and this is the crucial part – the other way round doesn’t hold true, so if you have somebody’s public key, you can’t deduce their private key. Hence, “one-way function”.

This makes sense. Obviously, Bitcoin would be useless if you could pull up somebody’s public key (which is available for all to see online, for the most part), and from that deduce their private key, hence gaining access to their wallet. There is no way to do this with the computers of today because you would need to sift through an astronomical number of calculations to crack what the private key is.

Step in quantum computers. Think of a quantum computer like Albert Einstein’s brain, and a normal computer like my measly brain. Things that are completely infeasible for me are well within the realm of the possibilities for Mr Einstein. And in this analogy, Einstein can crack the private key.

Many think it is inevitable that quantum computers advance to that point. Looking at their progress in recent years, it would be difficult to bet against it. For example, in 2019, Google claimed in a paper (that was eagerly awaited by researchers) that it had developed a particularly advanced quantum computer. This computer was capable of performing a calculation in 200 seconds that would take today’s most advanced classical computer, known as Summit, approximately 10,000 years.

With Bitcoin, in order to send bitcoins from one address to another, the sender must authorise that they own the (public) address where the funds are stored. In order to do this, they must provide a digital signature in the form of their private key to prove that the funds in that address are theirs. With a quantum computer of sufficient power, somebody who has your public key could crack the code to get your private key, hence gaining the power to falsify the signature and sweep up all your bitcoins.  Shock and horror! Exclamation point!

But hold on – that doesn’t mean bitcoin wallets are about to be cracked. Not all of them, at least.

Will quantum computers crack Bitcoin?

Bitcoin addresses, for the purpose we are looking at here, can be split into two categories. This will sound a bit complex at the start, but bear with me – remember, I don’t come from a computing background either, so I’ll keep it simple and tie it all together.

The first of the two categories of Bitcoin address is called a “pay to public key” (p2pk). It was the OG address type and hence most addresses from back in the day fall under this category. That includes your bitcoins, Mr or Ms Nakamoto – but more on the implications of Satoshi later.

These p2pk addresses are the vulnerable ones when it comes to a potential future that includes quantum computers. The public key is directly obtainable from the wallet address and, this being blockchain, the addresses are all visible to everybody in the world.

For example, this is the genesis bitcoin address of Bitcoin, the first address ever made. Satoshi Nakamoto – wherever you are, big fella – received 50 bitcoins as a reward for mining it back on January 3^rd 2009. The 50 bitcoins have never left the address since. And everybody can deduce the public key of this address.

(Oh, as a fun sidenote, as you can see below there are 68 bitcoins in this address, despite the fact Satoshi only earned 50 bitcoins for mining it. That is because people have sent bitcoins to the address throughout the years to show their appreciation for what Satoshi did).

Satoshi actually mined over 22,000 bitcoin blocks with a new address generated each time because he or she wanted to remain as anonymous as possible. With 50 bitcoins in each of these addresses (again, none have ever moved – diamond hand emperor), there are about 1 million bitcoins assumed to belong to Satoshi.

But anyway, back to the point. These are obviously early bitcoin addresses and hence fall under the p2pk category. This means that the publicly visible addresses, for example the genesis address as shown above – 1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa – all have their public keys obtainable by anybody in the world.

And when a quantum computer comes along, it will be able to crack the private key of these addresses from these available public keys, and sweep up all the bitcoins. The crucial takeaway from this section is that in order for a Bitcoin address to be compromised by a quantum computer, it must have an accessible public key first.

Are all addresses susceptible to being cracked by quantum computers?

Luckily, not all addresses fall under this category. The second category is a newer type of address called a “pay to public key hash” (p2pkh). For these addresses, the public key cannot be obtained from the address. Instead, the public key is only revealed to the world when a transaction is made sending funds from that wallet.

This means that these addresses are impenetrable by quantum computers until the user sends funds from that wallet. After that, they are just like Satoshi’s p2pk addresses above – their public keys are visible to the world and they are vulnerable to quantum computers.

This is why purists encourage the reuse of Bitcoin addresses. Indeed, if one is being as secure as possible, they should never reuse the same address – but many don’t heed this advice.

So how many Bitcoin addresses can quantum computers crack?

To summarise the previous section, two types of bitcoin addresses are vulnerable to quantum computing. The first is the old-school p2pk addresses, like Satoshi’s. The second is reused p2pkh addresses.

Deloitte published an analysis assessing the number of addresses falling into these categories. The below graph summarises their findings.

It shows that the old-school p2pk addresses dominated in the early years. The more secure p2pkh addresses came online in 2010 and soon became the dominant address type. A key conclusion drawn is that the number of coins contained in the old-school p2pk addresses seems to have remained constant at about 2 million bitcoins (9.5% of the final supply of 21 million bitcoins, over half of which are assumed to belong to Satoshi).

I think it is fair to conclude from looking at the stagnant 2 million coins in p2pk addresses (blue line) that these can be attributed to early adopting miners who have never sold and many are likely lost coins (again, half of these are Satoshi’s).

Of more intrigue is the reused p2pkh addresses (purple line), the second category vulnerable to quantum computers. After increasing between 2010 and 2014, it has decreased since then and now sits at about 2.5 million coins.

This means that a total of between 4 and 4.5 million coins (red dotted line in graph) are vulnerable to quantum computers (2 million from old school p2pk addresses and 2.5 million from reused p2pkh addresses). That is over 20% of the final supply.

How can you reduce the risk of Bitcoins being stolen?

There is one type of address that is safe: p2pkh addresses that have never been used to send bitcoins elsewhere. On the flipside, a p2pkh address that has previously sent bitcoins elsewhere, as well as p2pk addresses (regardless of whether they have sent bitcoins or not) are vulnerable.

So, in order to protect your bitcoins, they need to be sent to a new p2pkh address. This is the main argument against the threat of quantum computing for Bitcoin. Believers say that bitcoins can simply be transferred to new p2pkh addresses and hence they are impenetrable. They are correct.

But there is a catch. If you have lost the private keys to your address, you cannot access these bitcoins and hence they cannot be moved. This means that they will be free pickings for hackers once quantum computers come online.

So while the Deloitte study assessed the number of Bitcoin addresses that would be vulnerable if quantum computers came online today (21%), perhaps a more pertinent question is how many bitcoins will always be vulnerable to the threat of quantum computers. Because whatever that number is, that is the key one that poses a systemic risk to the Bitcoin network at large.

Is there a systemic risk to Bitcoin?

Let’s say a 21st-century Albert Einstein wakes up tomorrow and suddenly has a quantum computer. Little Albert Junior sweeps up over 20% of the total Bitcoin supply. What happens next?

Obviously, the price will drop. Firstly, you get the supply essentially increasing as all the lost coins, including the 5% assumed to belong to Satoshi, are now back in circulation. But the price will drop because of more than a simple supply-side adjustment.

It is anyone’s guess as to where the price lands, but mine is that it goes to near zero. How do you convince a people that Bitcoin – forever marketed as the hardest form of money to ever exist – has one massive catch?

The argument then becomes “OK, we all thought this was the hardest money ever to exist, although technology was flawed and computers developed to a point where they cracked it, but now we promise it’s safe again and technology won’t ever crack it again”.

How many people will use Bitcoin in that scenario? Can you forsee any S&P 500 companies holding it on their balance sheet? Any more countries declaring it as legal tender? Any pension funds investing in it? It’s not just 20% of the supply gone, the entire gig would be up. It would be over.

This is why the reduction in the 20% vulnerable bitcoins needs to happen. Thanfully, it is not anticipated that Albert Einstein Jr will have his super computer online by tomorrow.

Why doesn’t everybody just transfer to (impenetrable) new p2pkh addresses?

This is the solution. But like I said, there are wallets containing bitcoins to which their users have lost the private keys, or are dead, or various other reasons. These bitcoins cannot be moved. If Satoshi is dead, for example, his or her coins will not be moved until a quantum computer of sufficient power is developed.

This is what led blockchain technology expert Andreas Antolopoulos to declare the following:

We will know when quantum computing exists when Satoshi’s coins move

We will know when quantum computing exists when Satoshi’s coins move

Andreas Antolopoulos

But all is not lost. There is, thankfully, a solution to this hopefully-hypothetical-but-in-reality-one-day-not-hypothetical issue. That solution is to come to a plan within the Bitcoin community to force people to move their bitcoins to addresses which are not vulnerable. Deloitte suggests that such a plan could outline that “after a predefined period (of time allowing people to move their bitcoins to safe addresses), coins in unsafe addresses would become unusable (technically, this means that miners will ignore transactions coming from these addresses)”.

This would be an incredibly messy and divisive issue, in all likelihood. Trying to achieve a consensus within the community would be a nightmare and it reminds me of the infamous civil war period within the Bitcoin community in 2017, which led to a “hard fork” and the creation of Bitcoin Cash.

Is Bitcoin definitely safe if transferred to “impenetrable” addresses?

Hmm. Well, there is one more issue. Once a transaction is enacted to send funds from a wallet, the public key becomes available. This then means a quantum computer can crack the private key.

But there is a delay between the time a transaction is initiated and when it is confirmed miners. Bitcoin blocks get mined every ten minutes, meaning there exists a window where the public key is available but the funds have not yet been transferred from a wallet.

So, if an attacker could obtain the private key from the public key within this time period and then make a transaction of their own whereby they send those same bitcoins you are trying to send but to a different address, and pay a higher mining fee to gain priority in the queue, the bitcoins could be stolen.

So, if a quantum computer ever gets to a point whereby it can crack a private key in less than ten minutes – and this is getting into increasingly mythical territory here, I should caveat – then all bets are off and theoretically every transaction made on the network could be hacked.  

I will defer to Deloitte here who sums up this issue well:

Current scientific estimations predict that a quantum computer will take about 8 hours to break an RSA key, and some specific calculations predict that a Bitcoin signature could be hacked within 30 minutes

This means that Bitcoin should be, in principle, resistant to quantum attacks (as long as you do not reuse addresses). However, as the field of quantum computers is still in its infancy, it is unclear how fast such a quantum computer will become in the future

If a quantum computer will ever get closer to the 10 minutes mark to derive a private key from its public key, then the Bitcoin blockchain will be inherently broken

Itan Barmes & Bram Bosch, Deloitte

Conclusion

Evidence points toward Bitcoin being secure for many years.

Evidence also points towards a world in the future where quantum computers will exist and Bitcoin will eventually be vulnerable. Even in a case where this happens, the Bitcoin network could nullify the threat by performing a soft fork and migrating to a network with a quantum-secure encryption method.

The problem in that case (hate to be the bearer of more bad news) is that it would likely cause serious scalability issues, something the network already struggles with.

To wrap this up, it comes down to which way technology goes – both with quantum computing and with Bitcoin. Technology evolves at lightning pace. A case in point is this very discussion, which would have been preposterous 20 years ago, both in relation to the inevitability of quantum computers but also regarding the existence of a digital currency and something called a “blockchain”.

More research and continued development on the Bitcoin side need to be done to ensure its future against the threat of quantum computing. The community has come a long way and Bitcoin does evolve, despite what many naysayers argue, so this is very possible.

A world where Bitcoin transitions to a post-quantum cryptography mechanism is no more preposterous than a world where quantum computers that can crack private keys exist. We have just got to hope that the former arrives first.

Thanks for reading my attempt at simplifying this incredibly complex and speculative issue, and if you have any comments or feedback (even hatemail!) feel free to reach out to me on Twitter at @DanniiAshmore or @InvezzPortal

The post Can quantum computing break Bitcoin? appeared first on Invezz.