Could advanced quantum computing pose a risk to Bitcoin security?

The rapid advancement in quantum computing could put certain types of Bitcoin transactions at risk. How can we counter this risk?

The rapid advance in quantum computing is predicted by some have a critical impact on domains that use public key cryptography, such as the Bitcoin ecosystem.

Bitcoin’s “asymmetric cryptography” is based on the “one-way function” principle, which means that a public key can easily be derived from its corresponding private key, but not the other way around. This is because classical algorithms take an astronomical time to perform such calculations and are therefore impractical. However, Peter is Shor Polynomial time quantum algorithm, which is executed on a sufficiently advanced quantum computer, could carry out such deductions and thus forge digital signatures.

Potential risks from quantum computers

For a better understanding of the levels of risk introduced by advanced quantum computing, let’s limit ourselves to simple person-to-person payments. These can be divided into two categories, each of which is affected differently by quantum computing:

1. Pay to Public Key (p2pk): Here the public key can be obtained directly from the wallet address. A quantum computer could potentially be used to derive the private key so that an adversary could spend money at the address.
2. Pay to Public Key Hash (p2pkh): Here the address is made up of a hash of the public key and is therefore not directly available. It is only disclosed at the time a transaction is initiated. So as long as funds have never been transferred from a p2pkh address, the public key is unknown and the private key cannot even be derived with a quantum computer. However, if funds are ever transferred from a p2pkh address, the public key will be disclosed. Therefore, such addresses should never be used more than once to limit public key disclosure.

While avoiding the reuse of a p2pkh address can limit vulnerability, situations can nonetheless arise in which a quantum capable adversary can successfully commit fraud. Transferring coins even from a “secure” address reveals the public key. From that moment until the transaction is broken down, an adversary has a window of time to steal funds.

Theoretical Methods to Attack Bitcoin Using Quantum Computing

1. Transaction hijacking: Here an attacker computes the private key from a public key of a pending transaction and creates a contradicting transaction by issuing the same coins and thus stealing the victim’s assets. The adversary offers a higher fee to incentivize inclusion on the blockchain via the victim’s transaction. It must be noted that before the victim’s transaction is mined, the attacker must not only create, sign, and transmit the conflicting transaction, but also first run Shor’s algorithm to derive the private key. Of course, timing is crucial for such attacks. Therefore, the level of performance of quantum computers determines the likelihood of success of this threat vector.
2. Selfish Mining: With this potential attack vector, the attacker could theoretically use Grover’s algorithm to gain an unfair advantage in mining. This quantum calculation routine helps in the search for unstructured data and can provide a square jump in the hash rate. The ability to mine quickly in the event of sudden quantum acceleration could destabilize prices and control the chain itself, leading to possible 51% attacks.
3. Combined Attacks: By combining the two vectors above, an attacker could theoretically build a secret chain and, if at the top, selectively publish blocks to reorganize the public chain. The opponent can also choose to hijack transactions at the same time. Here, not only bonuses and transaction fees, but also all funds in (non-quantum-resistant) addresses that were spent on the overwritten transactions would be blocked.

Methods to Combat Potential Quantum Computing Attack Vectors

Fraud analysis

Data science tools can be used to mitigate the window of opportunity an adversary has to steal funds.

Data collected through Mempool APIs can be used to run machine learning algorithms in real time to detect anomalies in the transaction fees offered, thus flagging attempts at transaction hijacking. Such algorithms can also help to identify sharp jumps in the blockchain hashrate and to trigger warnings of possible “egoish mining”.

Dynamic AI models can calculate the fraud risk of outstanding transactions at any point in time until they are confirmed. These models can infer potential gains from adversaries for each threat vector, thus determining the likelihood of a fraudulent transaction. Insurance products can be designed in such a way that they cover the risk of fraud in pending transactions, the price of which can be calculated dynamically from the probability of fraud derived from models.

In addition, a “reputation score” can be calculated for each node in the blockchain. APIs that collect device details, IP addresses, etc. can be used to group activities (mining and / or transactions) into homogeneous clusters with a high likelihood that they are from the same users. Such patterns can also be used to identify quantum computers directly in the blockchain. Reputation scores can be of particular concern in combined attacks as opponents use a multi-vector approach to siphon off funds.

Bitcoin’s public transaction log provides extensive data on user profiles. “Network algorithms” can use this information to link different wallet addresses and thus uncover coordinated attacks. This can enable us to blacklist linked wallet addresses of quantum-activated opponents.

Wallet interface design

Smart user interface design can help alert customers to the risk of address reuse through strategic placement of alerts.

Consensus rules

Principles of effective incentive design can be used to formulate changes to the consensus rules, such as the application of a surcharge on transaction fees for p2pk and reused p2pkh wallets. This would encourage users to switch to safer behavior. In addition, this would lead to a reduction in the confirmation time of such transactions, as the miners would select them first, which would limit the time window for the opponent.

diploma

The growth of quantum computers with internal states made up of many qubits could raise questions about the underlying cryptographic security of Bitcoin. Even users who adhere to best security practices can still be affected by situations where significant numbers of Bitcoin are stolen from insecure addresses, leading to increased price volatility. A wide range of initiatives in post-quantum cryptography are underway to mitigate such scenarios.

It is important to note that the advent of “quantum domination” does not necessarily mean a weakening of the Bitcoin ecosystem. Better quantum computing systems will eventually provide opportunities for a slow economic transition to better tools.

During the phase of asymmetrical use quantum computers could generate multiple threat vectors, fraud risk management principles along with user awareness can help develop solutions for such a future.

References

1. In short, PW. Polynomial time algorithms for prime factorization and discrete logarithms on a quantum computer, 1999. SIAM Rev. 41, pp. 303-332. Retrieved from https://arxiv.org/abs/quant-ph/9508027

2. Grover, LK. A fast quantum mechanical algorithm for database searches, 1996. In Proc. 28th ACM Symposium on Theory of Computing (STOC ’96), Philadelphia, Pennsylvania, pp. 212-219. New York, NY: ACM. Retrieved from https://arxiv.org/abs/quant-ph/9605043

3. I. Stewart, D. Ilie, A. Zamyatin, S. Werner, M. Torshizi, and WJ Knottenbelt. Commitment to Quantum Resistance: A Slow Bitcoin Defense Against a Rapid Quantum Computing Attack. Royal Society Open Science, 5 (6): 180410, 2018. Retrieved from https://royalsocietypublishing.org/doi/pdf/10.1098/rsos.180410

This is a guest post by Debanjan Chatterjee. The opinions expressed are solely their own and do not necessarily reflect those of BTC Inc or. contrary Bitcoin magazine.

The views and opinions expressed herein are those of the author and do not necessarily reflect those of Nasdaq, Inc.