What will be the impacts of quantum computers on the blockchain?

Quantum is an emerging technology that follows the laws of quantum mechanicsIt is the study of matter and energy at the atomic and sub-atomic level.. It uses the fundamental principles of quantum mechanics like superposition, interference, and entanglement to solve problems deemed computationally infeasible by traditional computers.

Quantum algorithms

Quantum algorithms are algorithms that run on the model of quantum computation. These algorithms empower quantum computers to leverage the essential properties of quantum computation like quantum superposition, quantum entanglement, and quantum interference to perform fast computation. They can be classified into the types shown in the illustration below.

The types of quantum algorithms, sub-group findings, and amplitude amplification impact blockchains, so we will discuss them only in this answer.

Sub-group finding

Shor’s algorithm best represents the sub-group finding algorithms. This algorithm allows for solving the integer factorizationIn number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. and discrete logarithm problem in polynomial timePolynomial time is O(n^c), where n is the size of the input and c is a constant.. This represents a huge improvement over the classical algorithms, which solve the problem in super-polynomialPolynomial time is O(c^n), where n is the size of the input and c is a constant. time.

Shor's algorithm threatens the current cryptography algorithms, which work at the core of the blockchains. Cryptographic algorithms like RSA, elliptic curve cryptography, and El-Gamal, which are widely in use today, rely on the difficulty of solving the integer factorization problem or discrete logarithm problem to provide security. Shor's algorithm's ability to solve these problems leaves these cryptographic algorithms vulnerable.

Amplitude amplification algorithm

Grover’s algorithm best represents the amplitude amplification algorithms. These algorithms amplify the amplitude of the desired states of the qubits while reducing the amplitudes of the undesired states. This increases the probability of the correct state being returned during the quantum measurement of the system. These algorithms allow for a solution to be found in any search space of cardinality $n$ in time $O(n)$. This allows NP-completeThose problems whose solution can be verified in polynomial time. problems to be solved quadratically faster than the classical algorithms.

Amplitude amplification algorithms impact blockchain, as most consensus algorithms rely on NP-complete problems to be solved to reach consensus. Grover’s algorithm allows an intruding party to complete the consensus process earlier than the miners, allowing them to tamper with transactions in transit.

Blockchain

Blockchain is a peer-to-peer network without a central authority. Nodes in the network are tasked with reaching a consensus on making changes to the ledger. In the absence of a central authority, blockchains use cryptographic techniques and consensus algorithms to oversee transactions and ensure security. Different blockchains use different consensus and cryptographic algorithms, but in this Answer, we will discuss the impact of quantum computers on bitcoin.

Bitcoin uses Proof of Work (POW) as the consensus algorithm and Elliptic Curve Digital Signature Algorithm (ECDSA) as the digital signature algorithm. Quantum computers can attack the bitcoin blockchain by exploiting the weakness of these algorithms. The attack can be classified into two types, storage attack and transit attack.

Storage attack

Storage attack occurs when the attacker gets access to the funds stored within a user’s wallet by generating the private key from the publicly available public key.

Bitcoin uses the ECDSA algorithm to sign the transactions and prove ownership of the tokens. Transactions are the transfer of bitcoin from one entity/wallet to another. Other entities use the wallet address generated by the public key to send bitcoin, but other entities can not access the funds in the wallet unless they own the private key. Public keys can be generated if the private key is given, but not vice versa.

ECDSA relies on the complexity of solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) to find the private key corresponding to a public key. As discussed above, Shor’s algorithm can solve the discrete logarithm problem in polynomial time $O(n^3)$, which is a lot better as compared to the exponential time $O(2^n)$ taken by classical algorithms. This allows the attacker to calculate the private key of a wallet corresponding to a public key. The attacker then can use this private key to sign new transactions and take over the wallet. However, bitcoin implements a security feature during the transaction process that allows it to somewhat mitigate this problem. A transaction in bitcoin is shown below.

During the transaction shown in the illustration above, user A wants to send User B $5$ bitcoins. User A currently has ten bitcoins in their wallet. To perform the transaction, user A sends a UTXOIt is a user transaction output, that represents the bitcoins being given to the user due the transaction or as change. as input to the transaction, and two UTXOs are generated as the output. One UTXO contains $5$ bitcoin for user B, and the other contains $5$ bitcoin for user A as change.

The public key of user A was publicly available when the transaction was initiated. This public key is now vulnerable to an attack using Shor's algorithm. To mitigate this and secure the $5$ bitcoins in user A's wallet, the UTXO representing the change of $5$ bitcoins is sent to a newly created public-private key-based address created and held by the wallet of user A. So if the attacker can generate the private key of user A using the public key, they will not be able to access the funds as the transaction change has been deposited to a newly created wallet address.

This security feature still leaves the private key vulnerable from the initiation of the transaction till it is committed to the bitcoin ledger. The waiting period for the transaction to be committed to the bitcoin ledger can exceed $30$ minutes. A Shor's algorithm running on a 485,555 qubitsA qubit is the basic unit of information in the quantum computer. It has two states 0 and 1, just like traditional computers. In quantum computers, elemental particles such as electrons and photons are known as qubits. quantum computer can solve the discrete logarithm problem in $30$ minutes, making the storage attack quite feasible and a serious threat to the blockchain when capable quantum computers come around.

Transit attack

A transit attack allows the attacker to manipulate a transaction in transit after it has been initiated and is pending addition to the bitcoin ledger. Grover's search algorithm, as discussed above, allows the attacker to perform the POW faster than the minersMiners are nodes that are responsible for generating a block of transaction that is added to the blockchain ledger after consensus.. Grover's algorithm can potentially allow the attacker to perform more POW than the rest of the network combined, leading to a 51% attackWhen a person gains access to a majority share of the computing power of the blockchain or controls a majority of the nodes responsible for voting a new block in to the ledger,. This can lead to the attacker manipulating any ongoing transaction, rejecting it, or updating the destination address of the transaction. They can also approve malicious transactions causing double-spending.

Gaining a majority share in computing power than the whole network combined is a computationally expensive task and performing the POW before other miners leave less time for the attacker to perform the transit attack successfully. However, this is still possible, although not as likely as the storage attack.

Conclusion

Quantum computers represent a leap forward in the computing industry. They have many useful applications in healthcare, finance, and logistics. However, they come with certain challenges, too, involving cryptography and blockchain. In the post-quantum era, all the widely used cryptographic algorithms will be broken and need to be replaced with quantum-safe alternatives. This will also cause blockchains to shift to quantum-safe alternatives, some of which are already under consideration and development. However, as the situation currently stands, the quantum computers capable of breaking these algorithms are at least 10 to 15 years away.