Quantum Computing And Bitcoin Security

Rapid progress in quantum computing is predicted by some to have crucial ramifications in domains using public-key cryptography, such as the Bitcoin ecosystem.

Bitcoin’s “asymmetric cryptography” is based on the principle of “one-way function,” implying that a public key can be easily derived from its corresponding private key but not vice versa. This is because classical algorithms require an astronomical amount of time to perform such computations and consequently are impractical. However, Peter Shor’s polynomial-time quantum algorithm run on a sufficiently-advanced quantum computer could perform such derivations and thus falsify digital signatures.

Potential Risks Posed By Quantum Computing

For a better understanding of risk levels introduced by advanced quantum computing, we restrict ourselves to simple person-to-person payments. These can be divided into two categories, each affected differently by quantum computing:

Pay to public key (p2pk): Here, the public key is directly obtainable from the wallet address. A quantum computer could potentially be used to derive the private key, thus allowing an adversary to spend funds at the address.
Pay to public key hash (p2pkh): Here, the address is composed of a hash of the public key and hence, is not directly obtainable. It is revealed only at the moment of initiation of a transaction. Hence, as long as funds have never been transferred from a p2pkh address, the public key is not known and the private key cannot be derived even using a quantum computer. However, if funds are ever transferred from a p2pkh address, the public key is revealed. Hence, to limit exposure of the public key, such addresses should never be used more than once.

While avoiding reuse of a p2pkh address can limit vulnerability, there might still arise situations where a quantum-capable adversary can successfully commit fraud. The act of transferring coins even from a “safe” address, reveals the public key. From that moment until the transaction is mined, an adversary has a window of opportunity to steal funds.

Theoretical Methods Of Attacking Bitcoin With Quantum Computing

Transaction hijacking: Here, an attacker computes the private key from a public key of a pending transaction and creates a conflicting transaction spending the same coins, thus stealing the victim’s assets. The adversary offers a higher fee to incentivize inclusion in the blockchain over the victim’s transaction. It must be noted that, before the victim’s transaction is mined, the attacker must not only create, sign and broadcast the conflicting transaction, but also first run Shor’s algorithm to derive the private key. Clearly, timing is crucial for such attacks. Hence, the performance level of quantum computers dictates the success probability of this threat vector.
Selfish mining: In this potential attack vector, the attacker could theoretically use Grover’s algorithm to gain an unfair advantage when mining. This quantum computation routine aids searching unstructured data and can provide a quadratic jump in hash rate. The ability to mine quickly in a sudden quantum speedup could lead to destabilization of prices and control of the chain itself, resulting in possible 51% attacks.
Combined attacks: Combining the above two vectors, an attacker could theoretically build up a secret chain and, when in the lead, selectively publish blocks to reorganize the public chain. The adversary can also choose to simultaneously hijack transactions. Here, spoils of fraud would not only block rewards and transaction fees, but also all funds contained in (non-quantum-resistant) addresses spent in the overwritten transactions.

Methods For Combating Potential Quantum Computing Attack Vectors

Fraud Analytics

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

Data gathered via mempool APIs can be used to run real-time machine learning algorithms to spot anomalies in offered transaction fees and thus, flag attempts at transaction hijacking. Such algorithms can also help to spot sharp jumps in the blockchain hashr ate and accordingly raise alerts on possible “selfish mining.”

Dynamic AI models can compute fraud risk of pending transactions at every instant until confirmation. These models can deduce potential profits of adversaries for every threat vector, thus arriving at the probability of any transaction being fraudulent. Insurance products can be designed to cover fraud risk of pending transactions, pricing of which can be dynamically computed from the fraud probability inferred by models.

Additionally, a “reputation score” can be computed for each node in the blockchain. APIs capturing device details, IP address, etc. can be used to cluster activities (mining and/or transactions) into homogenous clusters, thus having a high chance of originating from the same users. Such patterns can also be used to directly detect quantum computers in the blockchain. ‘’Reputation scores’’ might be of special significance in case of combined attacks as adversaries use a multi-vector approach to siphon funds.

The public transaction log of Bitcoin provides substantial data about user proﬁles. “Network algorithms” can use this information to link diﬀerent wallet addresses, thus unmasking coordinated attacks. This can enable us to blacklist linked wallet addresses of quantum-enabled adversaries.

Wallet Interface Design

Intelligent design of user interface can help in alerting customers to the risk of reusing addresses, via strategic placement of warning messages.

Consensus Rules

Principles of effective incentive design can be used to formulate changes in consensus rules, such as applying a markup on transaction fees for p2pk and reused p2pkh wallets. This would prompt users to switch to safer behavior. Additionally, it would result in shortening the confirmation time of such transactions as miners would pick them first, thus narrowing the window of opportunity for the adversary.

Conclusion

The growth of quantum computers, with internal states consisting of many qubits, may raise questions about the underlying cryptographic assurance of Bitcoin. Even users adhering to security best practices might still be impacted in situations where a significant number of bitcoin is stolen from unsafe addresses, thus causing increased price volatility. A broad set of initiatives in post-quantum cryptography are underway to mitigate such scenarios.

It is crucial to note that the emergence of “quantum supremacy” does not necessarily imply weakening of the Bitcoin ecosystem. Better systems of quantum computing will eventually provide opportunities for a slow economic transition to better tooling.

While the phase of asymmetric usage of quantum computers might generate multiple threat vectors, principles of fraud risk management along with user awareness can help design solutions for such a future.

References

Shor, 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
Grover, LK. A fast quantum mechanical algorithm for database search, 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
I. Stewart, D. Ilie, A. Zamyatin, S. Werner, M. Torshizi, and W. J. Knottenbelt. Committing to quantum resistance: a slow defence for bitcoin against a fast 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. Opinions expressed are entirely their own and do not necessarily reflect those of BTC Inc or Bitcoin Magazine.