nuxttest - Can A Quantum Computer Hack Bitcoin?

Bitcoin is a new form of money secured by cryptography rather than trust in a central institution. When dumbed right down this means Bitcoin is protected by maths. If you can break the maths, you can break Bitcoin, but since its launch in 2009, it has functioned flawlessly reassuring hodlers that its cryptography is secure. However, just as technology has evolved to enable decentralised money it is also creating an existential challenge to its cryptography through a new breed of quantum computers. The question is, can a quantum computer hack Bitcoin?

In an adversarial world protecting information is critical to security, which is why governments invest heavily in information intelligence. Historians believe that the outcome of World War II was influenced by the British cracking the Nazi’s machine for encrypted communication called ‘Enigma’.

In the digital age, cryptography has arguably become a more important arms race than physical weaponry, which is why the National Security Agency (NSA) - the department of the US government responsible for intelligence - develops algorithms to secure the sharing of sensitive information. 

Symmetric & Asymmetric Cryptographic Algorithms

Cryptographic algorithms aim to protect information behind entropy - random codes - which humans are terrible at producing. Cryptographic algorithms generally follow two approaches - symmetric and asymmetric.

The symmetric approach requires the sender and receiver of information to both use the same key to decrypt it. A version called AES (Advanced Encryption Standard) developed by two Belgian cryptographers, Joan Daemen and Vincent Rijmen, at NGRAVE's partner COSIC  is the most common commercial approach used today relying on either 126-bit or 256-bit encryption. (Bits are the smallest unit of computer data written in binary - zeros or 1s). 

AES has never been hacked, but its predecessor DES, introduced in 1976, used 56bit keys which can now be broken within a few hours. The limitation with symmetric algorithms is how to deliver the single key, with the most analogue solution being a suitcase handcuffed to a secret service agent.

Asymmetric encryption requires both the information and a Public Key to encrypt it - which as its name suggests can be shared - as well as a Private Key to then decrypt it.

Symmetric & Asymmetric Cryptographic Algorithms.

RSA, the common asymmetric approach, is based on factoring large numbers but has to resort to increasing sized keys. A French team cracked a 795-bit key in 2019 (that’s 232 decimals) and it is rumoured that Chinese government engineers have broken a 1024-bit key, which means RSA keys must now be 4096 or even 8192 bits in length to be confidentally secure. 

Bitcoin is protected with an asymmetric algorithm but with a different approach called ECDSA - Elliptic Curve Digital Signature Algorithm - which is as secure as RSA but not as computationally demanding. 

ECDSA uses a complex combination of digital signatures, Public and Private Key pairs and a hashing algorithm called SHA 256 which was again developed by the NSA. 

Without attempting to delve into the complexities, ECDSA ensures that making a Bitcoin transaction is mathematically complex - requiring two correct Signatures derived from the correct 256-bit key pair via a hash function - yet trivial to verify. The key question is: just how secure is Bitcoin’s encryption?

How secure is Bitcoin’s encryption?

Not only are humans bad at being random, we also struggle to conceive of big numbers, mainly because it is of no evolutionary benefit. This weakness means your head will hurt grappling with the odds of guessing a unique 256 bit Private Key which is the same as the number of atoms in the universe. But this infographic might help.

Difficulty of guessing a specific 256bit private key.

You can be forgiven for thinking that based on the insanely improbable chance of cracking 256 Private Keys that Bitcoin’s cryptography is untouchable. The common approach to breaking encryption is through pattern recognition and brute force attack - throwing as much computer processing power as you can muster to systematically cycle through guesses.

The Passwords we regularly use can be hacked because of our weakness in creating random strings - we revert to pets’ names, birthdays and the classic Password123.

But even when applying randomness, standard computer processing power can crack an eight-letter password in lower case and containing no special characters in 8.5hrs, while a Super Computer making 1 billion guesses a second can do that instantly. 

Impressive as this is, the improvement in conventional computer processing power is limited by Moore’s Law - predicting the number of transistors on microchips will double every two years.

On that basis guessing a unique atom from the entire universe will remain beyond even a supercomputer’s capability.

However, the whole basis of computing power and the threat posed to algorithms like SHA256 is being disrupted by a new paradigm in technology unrestricted by binary computation. It’s called quantum computing and some fear it could be a game-changer for the security of Bitcoin’s cryptography.

What is Quantum Computing?

Quantum computers aren’t smarter than existing binary-based computers, but they are much faster. ‘Quantum Supremacy’ makes challenges that because of time constraints are simply unfeasible for existing chip-based computers suddenly within reach. 

This includes the search for the largest prime numbers and cracking cryptographic algorithms. Hence the fear that Bitcoin might be hacked by quantum computers.

Quantum computers aren’t constrained by binary processing, where something is either a 1 or 0. They work in qubits which have a quantum state, meaning they can be both a 1 or 0, or a superposition of the 0 and 1 state, until the point of measurement, when it is always a 1 or 0. 

Quantum computing is way too complex to effectively explain in detail here, but the rules of soccer provides a useful analogy. Soccer is played mostly using your feet and head, with rules forbidding use of your hands (except for goalkeepers). So think of classic physics as soccer under standard rules.

Quantum physics is like being able to play soccer using your hands. In some scenarios, it provides a huge advantage over existing rules, but for others, you still just use your feet.

The key takeaway is that working quantum computers exist and are opening up a completely new realm of computational capability. Including the potential to crack algorithms, like SHA 256, that were previously thought to be unbreakable.

How might Quantum Computing hack Bitcoin?

The fear of quantum computers in relation to Bitcoin is that they take brute force attacks to a whole new level, attacking the way signatures are applied to spend bitcoin.

Remember, all you need to spend bitcoin is a valid pair of 256-bit keys, so a quantum attack would simply try to break the ECDSA algorithm by computing the Private Key from a known Public Key.  So this particular threat applies to known Public Keys.

In its early days, Bitcoin used P2PK (Pay-to-Public-Key) which exposed Public Keys, but the majority of Unspent Bitcoin Transactions (UTXOs) use an updated hashed form (P2PKH) making it much harder to know the public key. 

The recent Taproot upgrade to Bitcoin reverted to exposing Public Key information suggesting that the Bitcoin Core Team, responsible for its development, isn’t concerned by the threat of quantum computing.

Could Quantum Computing hack Bitcoin Mining?

Aside from the potential for quantum computing to break the cryptography that secures bitcoin transactions, there is the risk to the mining process which is also algorithm-based.

Bitcoin mining is how new bitcoin are issued. Miners run a hashing algorithm called Proof of Work competing to find what is described as the golden hash, an arbitrary value that is difficult enough to find to ensure a consistent time to confirm new blocks of transactions.

Quantum leaps in computing could enable miners to solve the puzzle in a fraction of the time currently taken, but this is unlikely to endanger the network. We’d logically assume that the technology would be widely available so there would be no competitive advantage.

 In a scenario where bitcoin is mined using quantum computers, there would be a massive drop in the energy used to run the SHA 256 hashing algorithm, but quantum computers need a huge amount of energy to keep them close to absolute zero, which is impossible to quantify right now.

If just one miner was using a quantum computer they could theoretically mine every new block, create double spends in their favour and enforce that incorrect version of the bitcoin blockchain going forward. 

These worst-case scenarios rely on huge assumptions about the scaling of quantum computing power, don’t take into consideration parallel development in quantum-resistant algorithms and don’t address the motivations that might justify a quantum computing attack on Bitcoin.

The reality of the threat posed by Quantum Computing

Before you panic-sell your entire crypto portfolio it is worth noting the potential of quantum computing is very different from the reality right now.

Joint research from the University of Sussex, Universal Quantum and Qu&Co published in January 2022 in AVS Quantum Science suggests that quantum computers would have to become a million times faster to break bitcoin’s cryptography. 

Their research worked on the assumption that the largest current quantum computer, IBM’s Eagle processor, currently contains 127 superconducting qubits. This surpasses Google and the University of Science and Technology in China and is theoretically more powerful than all the supercomputers on the planet combined.

But to crack Bitcoin in a 24-hour window, the team calculated it would require a quantum computer with 13 million qubits - 1million times bigger than Eagle - rising to 1.9billion qubits to achieve that within Bitcoin’s 10-minute confirmation window.

“State-of-the-art quantum computers today only have 50-100 qubits. Our estimated requirement of 13-300 million physical qubits suggests Bitcoin should be considered safe from a quantum attack for now” - Mark Webber, quantum architect at Universal Quantum.

Hodlers might be letting out a collective sigh of relief at this point but those last two words - “for now” -  are crucial. What is crucial is the speed at which Quantum Computing might improve and whether there are any logistical factors which might hinder development beyond a certain point.

Webber went on to say:

“Quantum computing technologies are scaling quickly with regular breakthroughs affecting such estimates and making them a very possible scenario within the next 10 years.”

And to drive that point home, back in 2018 Universal Quantum calculated that in order to break RSA encryption - commonly used by email providers and banks - an ion quantum computer would need to be 100m2 – roughly the size of a football pitch. 

Given the development in the field in the intervening four years, they’ve now revised that estimate down by a factor of 50, estimating a Quantum Computer of just 2.5m2 would suffice.

IBM aims to more than triple its capability to 433 qubits in 2022 with a processor called Osprey, then its road map predicts a jump to 1,121 qubits with Condor in 2023. If those ambitions are achieved it aims to reach 1 million qubits by 2030.

Coincidentally, that is the same target set by Google, while China is pouring a huge amount of funding into the area. At that rate, Bitcoin’s cryptography could very realistically come under threat but that assumes no parallel improvement in cryptographic algorithms to address the challenge posed by Quantum Computing.

The development of Quantum Resistant algorithms

Bitcoin developers and mathematicians haven’t been sitting with their fingers in their ears pretending not to hear the approaching threat of quantum computing. They’ve been developing different quantum-resistant solutions to Bitcoin’s current protocol for years.

The most obvious solution is to increase the size of the Public/Private Key pairs from 256bit to anything up to over  1million bits - 2^20. The problem with this approach is the practical impact it would have on Bitcoin usage and mining whether in higher costs, higher processing power or greater network traffic.

COSIC are again at the forefront of this space submitting entries to a four-year-long competition to find a post-quantum cryptography standard run by the National Insititute of Standards and Technology (NIST - part of the US Department of Commerce) with the draft standards available by 2024.

Imperial College London has also proposed a robust solution that would see the existing Public/Private Key secured under a quantum computing-threatened algorithm combined with an additional quantum-resistant signature pair. Additionally, a flexible commit-and-delay approach would be used where the user can adjust transaction confirmation time based on their willingness to assume greater potential risk to the quantum hijacking of the Public key during the mining process.

The commit-and-delay approach would require a soft fork on the Bitcoin protocol and action from individual users, with Imperial College estimating that around 33% of all BTC would otherwise be at risk given their use of unhashed Public keys.

Is a Quantum Computing attack on Bitcoin plausible?

Understanding the threat to Bitcoin posed by Quantum Computing is hard because there are so many unknowns. 

• How can we know the current benchmark in quantum capability? Given it is considered a national security issue.
• What is the rate at which quantum computing will scale?
• Is there a practical limit to quantum computing?
• How easy is it to apply quantum-resistant algorithms?

See NGRAVE’s CEO, Ruben Merre, explaining the future of quantum-resistant algorithms with Kitco in April 2022.

These are essentially questions of scientific possibility, but the discussion around quantum computing’s potential for breaking Bitcoin should also focus on whether it is plausible.

Quantum computers aren’t being created for the sole purpose of cracking Bitcoin, it just makes a good headline to assume that might be on their to-do list. Some analysts believe that the most plausible scenario for a quantum attack is to harvest encrypted data now, essentially doing the groundwork ready when and if enough qubits are lined up.

But the cost of building quantum computers is so great that there are only a few organisations with deep enough pockets. 

“By most estimates, a single qubit costs around $10K and needs to be supported by a host of microwave controller electronics, coaxial cabling and other materials that require large controlled rooms in order to function.” Seeqc - The challenge of scaling QCs

On the basis of the rough figures from Seeqc - who develop commercially viable quantum computing applications - and the 13million qubit requirement calculated by Universal Quantum, a conservative estimate of the cost of a quantum computer big enough to crack Bitcoin would be (13 million*10,000)= $130bn PLUS hardware costs.  

That machine would have to be built in complete secrecy, without Bitcoin’s Protocol changing to apply resistant signatures. As soon as it started creating double spends and holders understood why Bitcoin’s price would collapse rendering the process futile. This is essentially the same argument as mounting a 51% attack - it amounts to financial suicide.

Otherwise, the only real justification would be for a state actor, motivated by control, not direct financial gain, to build a quantum computer capable of breaking Bitcoin. But if their intention is to destroy or subvert it, there are less complicated options. 

The exhaustive Bitcoin Threat Model by JWWeatherman calls these Human Threats. No qubits are required, just the types of techniques already employed by secret services, such as infiltrating the Bitcoin Core Team or simply controlling the market for Bitcoin Mining hardware. Failing that, they can simply do what China has done and ban it.

The real Elephant in the quantum computing room is that Bitcoin is at the back of the queue when it comes to logical targets. Almost all of the secure online services we use today, including banking, rely on inferior encryption so the media should be focusing on that much more imminent threat. 

Given the parallel development in quantum resistance, it could well be that threat posed by quantum computing ends up being as overblown as the threat from the Y2K bug. Many predicted January 1st, 2000 would trigger an end of days computer catastrophe; it ended up being a trivial inconvenience.

At this stage, there are just too many unknowns to make bold predictions about quantum computers slaying Bitcoin. So rather than worrying about a potential future threat that is too complex to properly understand, focus on protecting your bitcoin from the threats that we know are real today.