COULD ADVANCED QUANTUM COMPUTING POSE A RISK TO 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.

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 Grovers 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 VECTORSFRAUD 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.