Bitcoin & The Quantum Computing Risk

• Recent news of advances in quantum computing are stoking fears that Bitcoin’s wallet structure is vulnerable to exploits, theoretically undermining its security.

• Using quantum technologies to exploit the Bitcoin protocol is theoretically possible. However, it is exceptionally difficult to do in practice.

• To mitigate against such attacks, a soft fork with a commit–delay–reveal scheme could be implemented.

• Due to the widespread use of 128-bit cryptography, quantum computing poses a much greater threat to a substantial proportion of the existing cryptographic infrastructure that the ecommerce and banking services rely on for everyday transactions.

Recent news has highlighted that China may well be ahead in the race for the most powerful quantum computer with their recently announced 66-qubit computer, named Zuchongzhi 2.1. This computer can purportedly process 10 million times faster than the fastest digital computer and is likely to exacerbate existing fears over the security of blockchain infrastructure and the prospect of “Quantum Supremacy”, where a quantum device can solve a problem, that no classical computer can solve in any practical amount of time.

Here, we describe cryptographic methods and their potential threat to Bitcoin from a balanced perspective.

Today’s cryptographic algorithms, such as those used for online transactions, can be broken, essentially by repeated guesswork, but their security derives from the wildly impractical length of time it takes to do so. Using the so-called brute-force method, where an ordinary computer cycles through all possible keys until the correct one is found, is a daunting task. For example, 128-bit encryption has 340 undecillion (36 zeros) variants. To put that into context, a computer that could test 1 trillion keys per second would take 10.79 quintillion years (Computerworld), that is 785 million times the currently accepted age of the universe. 128-bit encryption used to be the standard, but during the WikiLeaks furore in 2013, it became evident that secret service agencies were purportedly able to crack variants of these codes, albeit in an unorthodox manner. As a result, there has been a migration towards 256-bit encryption.

There are known alternatives to the brute-force attack that concern general computer security. Acoustic cryptanalysis employs a method of listening to a computer processor with a microphone. Using this method, analysts were able to circumvent very high levels of encryption. Some 256-bit encryption standards such as AES can currently be hacked within five minutes using an antenna that measures the power output of the encrypting computer. However, these techniques are not practical due to the need for the measuring equipment to be in very close vicinity to the computer doing the encryption work. Interestingly, most current hacking methods involve listening-in or intercepting the signals made during the encryption process. Due to the distributed nature of Bitcoin, these methods could not be used.

The impracticality of cracking methods is the reason why these forms of hacking are thankfully not prolific, but this may be about to change in the coming 5 - 10 years. Quantum computers are different to traditional computers in that the improvements are not from a rise in the clock speed but from an astronomical reduction in the number of steps needed to perform certain computations. They essentially use the properties of quantum mechanics to probe for patterns within a large number, making some current encryption techniques very vulnerable. Given a powerful enough quantum computer, most forms of public key encryption, commonly used in everyday transactions over electronic devices, could theoretically be cracked by quantum computers within minutes, using Shor’s or Grover’s algorithm (Bernstein & Lange).

Only government administrations and militaries, who often use much more secure symmetric encryption would remain protected from quantum computing, but this requires keys to be securely delivered to each site involved in the communication, with couriers carrying locked briefcases, thus not a practical solution for everyday security.

It is well known that Bitcoin uses SHA-256 cryptography for mining, and for public key obfuscation in the transaction process, and it should therefore be secure in a post-quantum world. However, it isn't as simple as that. Due to Bitcoin’s intricate structure there are theoretically several ways in which its security could be compromised.

Bitcoin transactions use a separate 256-bit Elliptic Curve Digital Signature Algorithm (ECDSA) for authorising transfers, a technique that is commonly used for much of internet security. While the ECDSA used in Bitcoin is 256-bit, the signature scheme is equivalent to 128-bit as a hacker would need only to exploit one private key with funds on the 256-bit curve. This is where most academic research on the subject focusses.

The Quantum attacks on Bitcoin (Aggarwal Et al. October 2017) summarise how ECDSA could be compromised: “An effective quantum attack would consist of finding the private key when the public key is revealed following the broadcast of a signed transaction to the network. This would allow an attacker to sign a new transaction using the private key, thus impersonating the key owner. As long as the quantum attacker can ensure that their transaction is placed on the blockchain before the genuine transaction, they can essentially ‘steal’ the transaction and direct the newly created Unspent Transaction Output (UTXO) into whichever account they choose.” Using this approach would likely require the quantum computer to be able to reliably solve in a similar time to the Bitcoin 10 minute block interval.

Early Bitcoin users were paid using P2PK (Pay-to-Public-Key) technology where users were paid directly to their public keys, so early Bitcoin public keys are known, meaning early and often affluent Bitcoin addresses are more vulnerable to this form of attack. Later addresses use the P2PKH (Pay-to-Public-Key-Hash) address format where addresses are obscured behind two cryptographic hashes (SHA-256 and RIPEMD-160) when new UTXOs are created, making them less vulnerable to an attack. The vast majority of UTXOs are P2PKH. Interestingly, the recent Bitcoin Taproot upgrade (which we discuss here) will again make public keys publicly visible, suggesting that Bitcoin developers aren't overly concerned with the risk of publicly known public keys.

The Proof of Work (PoW) Bitcoin mining process utilises the aforementioned SHA-256 cryptographic hashing algorithm, which we know would remain uncrackable in a post quantum world. Although theoretically a 51% attack can occur where an actor, or coordinated group of actors, could gain enough mining power to allow them to re-write part of the blockchain, or reverse their own transactions, leading to the possibility of a double spend.

It is likely that quantum computers are so widespread in the future that no single quantum enabled agent could dominate PoW mining. Thus it probably has greater implications for miners rather than the protocol itself, by simply lowering the cost per hash and increasing the mining difficulty. A slow transition to better technology as it becomes available is the most likely outcome, as is the standard practice today when new hardware is released.

The energy use of quantum computers is theoretically far lower than traditional computers due to its much more efficient way of being able to solve certain mathematical problems. A paper written by the National Renewable Energy Laboratory (link) suggests that a quantum computer’s energy use is very different from a traditional computer system, being dominated by the energy used for the cooling system rather than the electronic circuitry. Alan Ho from Google Quantum AI said it took 25kW to power and cool one of their quantum computers.

There are other initiatives where such aggressive cooling may not be necessary, but their progress lags the mainstream superconductor approaches. So while the power for the circuitry is likely to be lower, the extreme cooling requirement pushes up power requirements considerably.

We believe that combining the development costs and the technical capability to run a quantum system suggests it remains technically and economically unviable to compete with ASIC miners at present, and perhaps not ever.

Perhaps the key obstacle to reliable quantum supremacy is quantum decoherence. In less technical speak, quantum computers are very sensitive to environmental noise, and as systems increase in size and power, it becomes increasingly difficult to shield them from this noise. Decoherence leads to errors where information is lost, and while quantum computers are improving in reliability, they are following a fairly linear trend in improving reliability. Essentially, today’s quantum computers are too rudimentary to crack 128-bit cryptography at present, but progressively improving systems suggest they will be able to at some point in the future.

Opinion is divided on exactly when 128-bit cryptography could be cracked by quantum computers, with estimates ranging from the next 5 -20 years although consensus is around the 15 year mark. Google stated in a recent blog that they will have created a 1 million qubit computer within the decade, although it isn't entirely clear if this will be powerful or stable enough to threaten Bitcoin wallet infrastructure. According to Celia Merzbacher of the Quantum Economic Development Consortium, by around 2035 quantum computers will be reliable enough to crack current encryption standards, which aligns with views from the National Institute of Standards and Technology (NIST). Other researchers again remain sceptical over the viability of large-scale quantum computers.

There are post-quantum algorithms being developed that tackle the risk that quantum computers pose to security, and some of these approaches have been in development for many years. Lattice-based, multivariate and hash-based cryptography are examples, but these typically involve some trade-off, be it higher costs, higher processing power or greater network traffic. Some proposed post-quantum encryption systems would increase key sizes from a few thousand bits to 1 million bits (Introduction to post-quantum cryptography, Bernstein). This is clearly not practical or necessary for the Bitcoin protocol.

To mitigate against such attacks, Imperial College has proposed a soft fork with “a commit–delay–reveal scheme that enables the secure transition of funds to quantum-resistant wallets. The protocol allows users to execute the first step of transitioning funds even before the upgrade is deployed as the necessary functionality already exists in Bitcoin. Code changes are required only for the reveal stage of the transition, and they can be implemented as a soft fork, allowing users to upgrade at their own convenience.”

This approach works but would still leave existing ECDSA UTXO vulnerable, particularly those where the wallet keys are publicly known. The coins associated with these public keys would have to be moved voluntarily by their owners or else they would remain vulnerable to a sufficiently powerful quantum computer. Should the private keys of these public keys be lost, they would likely remain in place and act as a bounty of sorts for builders of quantum computers. The simple alternative would be for the funds within the vulnerable UTXOs to be moved to quantum proof addresses.

If quantum computers scale as some expect, we are in a race against time to deploy post-quantum cryptography before quantum computers arrive. In that sense, 15 years seems like enough time to prepare. However, it is estimated it would take at least 10 years to modify existing cryptographic infrastructure. This entails modifying all existing systems that use public key cryptography, which includes most electronic devices that connect to the internet.

We are already beginning to see initiatives employed by the ETSI (European Telecommunications Standards Institute) who are attempting to standardise the approach to post-quantum cryptography. Other initiatives will have to be developed to modify existing connected devices, and develop the architecture for new quantum safe devices and software. At present, quantum computers pose a burgeoning threat to internet security that could have significant detrimental economic consequences to organisations that do not immediately act to mitigate the risks.

It is clear that using quantum technologies to exploit the Bitcoin protocol is theoretically possible. However, it is exceptionally difficult to do in practice, and would be non-trivial, even if truly powerful enough quantum computers were to arrive.

Similar exploits exist for other stores of value and perhaps the best analogy are gold vaults. Gold vaults are typically incredibly secure, with very sophisticated security, but there are theoretical ways in which the gold from them can be stolen. Those methods would involve significant resources, perhaps with the help of a state actor, but in reality, highly unlikely to happen. Bitcoin is similar in that it is theoretically vulnerable to attacks, but until those theories become reality, it remains highly secure. The advantage Bitcoin has over gold in this example is that it is programmable, and can be modified to thwart any future security threats.

Due to the widespread use of 128-bit cryptography, quantum computing poses a much greater threat to a substantial proportion of the existing cryptographic infrastructure that the ecommerce and banking services rely on for everyday transactions. Given such a broad use across systemically important organisations, any vulnerability exposed by quantum computing could therefore have far greater consequences to incumbent financial infrastructure than it would to Bitcoin.

The information contained in this document is for general information only. Nothing in this document should be interpreted as constituting an offer of (or any solicitation in connection with) any investment products or services by any member of the CoinShares Group where it may be illegal to do so. Access to any investment products or services of the CoinShares Group is in all cases subject to the applicable laws and regulations relating thereto.

This document is directed at professional and institutional investors. Investments may go up or down in value and you may lose some or all of the amount invested. Past performance is not necessarily a guide to future performance. This document contains historical data. Historical performance is not an indication of future performance and investments may go up and down in value. You cannot invest directly in an index. Fees and expenses have not been included.

Although produced with reasonable care and skill, no representation should be taken as having been given that this document is an exhaustive analysis of all of the considerations which its subject-matter may give rise to.This document fairly represents the opinions and sentiments of CoinShares, as at the date of its issuance but it should be noted that such opinions and sentiments may be revised from time to time, for example in light of experience and further developments, and this document may not necessarily be updated to reflect the same.

The information presented in this document has been developed internally and / or obtained from sources believed to be reliable; however, CoinShares does not guarantee the accuracy, adequacy or completeness of such information. Predictions, opinions and other information contained in this document are subject to change continually and without notice of any kind and may no longer be true after the date indicated. Third party data providers make no warranties or representation of any kind in relation to the use of any of their data in this document. CoinShares does not accept any liability whatsoever for any direct, indirect or consequential loss arising from any use of this document or its contents.

Any forward-looking statements speak only as of the date they are made, and CoinShares assumes no duty to, and does not undertake, to update forward-looking statements. Forward-looking statements are subject to numerous assumptions, risks and uncertainties, which change over time. Nothing within this document constitutes (or should be construed as being) investment, legal, tax or other advice. This document should not be used as the basis for any investment decision(s) which a reader thereof may be considering. Any potential investor in digital assets, even if experienced and affluent, is strongly recommended to seek independent financial advice upon the merits of the same in the context of their own unique circumstances.

CoinShares Capital Markets (UK) Limited is an appointed representative of Strata Global Ltd. which is authorised and regulated by the Financial Conduct Authority (FRN 563834).The address of CoinShares Capital Markets (UK) Limited is Octagon Point, 5 Cheapside, St. Paul’s, London, EC2V 6AA.

The CoinShares Astronaut is a trademark and service mark of CoinShares (Holdings) Limited.