Will Bitcoin Proof of Work change due to quantum attacks? A lot of crypto experts and analysts believe that the quantum computers will have a significant impact on almost every field and it will be more profound in the field of crypto.
Since Bitcoin and most of the other crypto coins work on the Proof of Work consensus, the ability of the quantum computers to solve complex mathematical puzzles much more quickly and efficiently than other computers will affect the process.
This is particularly applicable to the fields that involve discrete algorithms and integer factorization like public key cryptography.
Ideally, this specific computing threatens the Elliptic Curve Digital Signature Algorithm or ECDSA that Bitcoin typically uses to sign transactions.
This may affect the working process of Bitcoin drastically.
Therefore, the crypto world needs to commit to quantum resistance even if the defense is slow for Bitcoin in opposition to a rapid quantum computing attack.
Typically, a simple and slow commit, delay, and reveal protocol is followed as a defense mechanism for alleviating the threats to Bitcoin transfer and its working process.
This mechanism allows the users to move their funds securely from the old and non-quantum resistant sources to destinations that adhere to quantum-resistant outputs and digital signature schemes.
Typically, this particular protocol for transfer of funds works even if the ECDSA is compromised in some way or the other.
Sometimes, you may need to make some changes in the Bitcoin protocol to implement these as a soft fork.
This article will enlighten you about it all including the status of Bitcoin and cryptography in the post-quantum world.
Contents
Will Bitcoin Proof of Work Change Due to Quantum Attacks?
Bitcoin, as you may know, is a digital currency that works on a decentralized system that leverages the P2P distributed network introduced by the pseudonymous Satoshi Nakamoto.
All transactions, new and old, are grouped as one in blocks and added to the blockchain which is also called the distributed public ledger.
Each block is linked with a hash and therefore modifications cannot be made once a block is added to the blockchain.
This guarantees the immutability of the records and transaction history.
There is no central authority to oversee the state of Bitcoin transactions but the participants of the network maintain the security and validate the authenticity of transactions through Proof of work consensus mechanism.
This is a process which requires the nodes or the participants in the network to solve complex cryptographic puzzles.
The participants of the consensus are called the miners and when they are able to solve the cryptographic puzzle, they are rewarded in two ways such as:
- By the new units of the underlying crypto coins mined and
- The transaction fees.
Therefore, Bitcoin and other crypto transactions are considered to be very safe and secure.
However, with the advent of the quantum computers it is expected that it will have a significant impact on this security aspect of crypto and Bitcoin.
With the powerful emergence and development of the quantum computers in the future, the architecture can break the ECDSA by using the polynomial time quantum algorithm of Peter Shor.
It can surely be considered as a powerful QCA or Quantum Capable Adversary that can steal funds easily from the users who reveal their public keys.
Therefore, it is required to secure Bitcoin transactions with a changeover from the existing signature scheme to a more efficient signature scheme that is typically quantum resistant.
In order to ensure secured Bitcoin transactions today, there is typically the need for a sizable delay phase.
This will provide adequate protection from accidental and, most importantly, from adverse chain reorganization.
The Bitcoin community has also supported the idea of deploying a quantum-resistant signature scheme that will enhance the safety of Bitcoin transactions.
Apart from that, it will also make the current systems quite capable of competing with the fast Quantum Capable Adversaries.
This will ensure that the current protocol can react to the autonomous quantum computing and do away with the common vulnerabilities that are ingrained in the public key cryptography of Bitcoin.
Quantum Algorithms
The efficiency of quantum computing depends on different quantum phenomena which include entanglement and superposition.
These phenomena help in representing typical data in a quantum context.
Apart from that, it also helps in manipulating data in order to have interpretable results.
Typically, the quantum computers are made of Qubits or Quantum Bits as opposed to the conventional computers that are made of bits.
The Qubits usually have two basic states, 0 and 1.
However, when the computation process is on, the state is typically a superposition or linear combination of the fundamental states.
Each of these states has a possibility to be measured.
While extracting information about a state of a quantum computer, the superposition of the system is collapsed to one of the probable basis states.
Technically, this means that the n-Qubits of the quantum computer is represented internally by the entire range of n-bit numbers to help in performing calculations simultaneously on all the numbers.
However, when these are measured, the state will typically collapse to only one of the basis states.
This means that there will be only one of the results returned to the calculation that has been performed.
In order to amplify specific basis states, the quantum algorithms use the fundamental structure of the problem.
This increases the probability and helps in making the results more conclusive and repeatable.
The quantum algorithms, however, can result in a radically enhanced runtime complexity as compared to the conventional counterparts which inevitably speed things up.
Ideally, there are two specific types of algorithms used by quantum computers.
Shor’s algorithm:
These computers use Shor’s algorithm for integer factoring.
This particular algorithm comes with a runtime complexity of O ((log N) 2(log log N) (log log log N)). This algorithm is much faster than the known conventional algorithms.
In reality, a period can reduce the integer factorization problem. This period is calculated as:
f(x) = ax mod N. Here, ‘a’ represents the random integer and ‘N’ represents the number that is to be factored.
Ideally, the Shor’s algorithm creates a superposition of the basis states to work.
Here every basis state is created by conjoining x with the value of f(x).
While measuring the Qubits that store the f(x), the superposition collapses and leaves a little value ‘v’ on the measured Qubits.
Here, the Qubits that stored x will have a superposition of diverse x’s where f(x) is equal to ‘v.’
The rest of the algorithm is required to extract the differences between the states in superposition in order to get the period of the function.
This is achieved by using the quantum Fourier transform circuit.
The Shor’s algorithm weakens the security of a few specific types of public-key cryptographic systems dramatically which include RSA.
Grover’s algorithm:
This algorithm is also an efficient tool that helps in quantum computation with an objective to solve the difficulty of searching free and unstructured data.
The probability of computing Grover’s algorithm is quite high which typically uses a rare solution x.
Here, f(x) = v, which represents the desired value. In this case, the time complexity is represented by O (√N/t), where ‘N’ symbolizes the domain size of ‘f’ and ‘t’ represents the number of solutions.
Grover’s algorithm typically operates by organizing a superposition of all the probable input states first.
Once again, every input state has a likelihood of being measured.
Then, the algorithm uses a few specific methods to boost up the probability amplitude iteratively of the states representing the solution.
The number of iterations after which the probability amplitudes of the proper states become maximum can be calculated mathematically when ‘N’ and ‘t’ are given. When the ‘t’ is known, the scheme will create a solution in O (√N/t) steps.
However, this state cannot be measured after every iteration. This is because the superposition will be collapsed at the end of the computation.
Typically, the Grover’s algorithm is quite useful for mining purposes because it hypothetically causes a quadratic increase in the speed while guessing a nonce.
Post Quantum Cryptography
Typically, post-quantum cryptography is an innovative division of cryptography that involves a set of algorithms.
This is supposed to be much more secure than conventional cryptography and is well protected from the attackers.
There are several applications of cryptographic systems that have not yet been broken by quantum computing.
A few of these are:
- Code-based cryptography that depends on the contumacy of decoding unidentified linear error correcting codes
- Hash-based cryptography that depends on the security aspect of the hash functions and
- Lattice-based cryptography that depends on the difficulty of the lattice problems.
In order to replace ECC or Error Correction Code as the fundamental for digital signatures to make a transaction it is imperative that the Bitcoin community is in agreement on and puts into practice an apt alternative, if not more than one.
This specific cryptography may result in the risk of public key unveiling.
It is assumed that the quantum computers will be used by some of the adversaries with malicious intent and reveal the public keys of the users.
The public key revealed previously can be deduced by a Quantum Computer Adversary very easily.
It may also pose a significant risk by ‘hijacking’ transactions live.
This is done by computing a private key that corresponds to the revealed public key that may be stored in the memory pools of the nodes in the transaction input of the network.
As a result of this, it produces an inconsistent transaction spending, just like double-spending, using the same UTXOs6 subset, enabling the attackers to steal funds of the victim.
However, this type of live transaction hijacking is quite different from the traditional form of double spending.
This is because it is the attacker here who is the only recipient rather than the initiator of the original transaction.
Changeover to Quantum Resistance
Therefore, there is a need for a conversion to quantum resistance by following a scheme that will secure the current signature scheme of Bitcoin and make it quantum resistant.
As said earlier, this scheme is based on the commit–delay–reveal mechanism.
This is quite simple which can be set up by using a soft fork in Bitcoin. When it is set up, the conventional ECDSA signatures will not be accepted any longer.
The users will then be allowed to spend only the UTXOs based on the quantum resistant signature scheme that was introduced previously or on the transition scheme.
Moreover, if anyone spends by using a public key which is not quantum resistant, the fund may be lost.
This is because the public key will be revealed and there will also be no proper protective mechanism that can be used effectively.
Quantum Enhanced Blockchain Networks
Quantum cryptography will fortify the security of blockchain even further since the communications will be authenticated inherently which will eliminate the chances of any user impersonating others.
This is based on the fundamental principle of physics of light which states that the quantum states are impossible to be duplicated or measured without being changed.
This means that anyone wanting to do so in the blockchain will be uncovered immediately.
Therefore, it is quite useful to replace standard digital signatures into quantum cryptography as well as to encode all P2P communications made in the blockchain network.
However, there can be a limitation to the adoption of cryptography networks due to the complexity and cost involved in it.
Also, to make this deployment a safe and effective one it is required to connect all the nodes in pairs since there is no trust in any one node and the communications must be direct.
This working process is much different from the one that works in the internet currently in which all communications are protected by one-way cryptography method and routed through different transitional nodes.
With the development of quantum communication protocols that do not depend on the independent device allow the untrusted quantum stations in the middle to relay secured signals between the involved parties.
When and if such protocols are integrated into the blockchain networks, it will simplify it greatly and will also make it more easily accessible to the consumers.
However, there is a notable challenge in this aspect that you should take care of which is the loss of photons in the optical fibers.
This may limit the capability of the quantum key distribution systems drastically bringing it down to just a couple of tens of kilometers.
One effective solution to this issue could be using a quantum repeater.
This works by using a quantum optical memory and quantum teleportation in order to share out quantum entangled states between the parties communicating with each other.
It is expected that both security of the blockchain network as well as the speed and efficiency will be enhanced with the use of quantum internet for running the blockchain processes.
The process of ‘quantum internet’ involves connecting all computers engaged in the communication network to make them able to run a fully quantum blockchain.
This would help in avoiding a few of the computationally intensive methods used in the current consensus and verification processes.
Therefore, this will be much more secure and efficient.
Moreover, the quantum Bitcoin currency would have more recognition due to its assured security which is based on the non-cloning theorem of quantum technicalities.
This means that even the bank notes cannot be forged if they contain quantum information records.
Attack on Proof of Work
Before looking into the attack possibilities of quantum computers on the Proof of Work consensus protocol, it is good to take a look at the advantages the quantum computers would provide when the hash cash PoW is performed by the Bitcoin blockchain network.
The quantum computer performs the function by using fewer hashes as compared to any traditional computers.
However, the specialized ASIC hardware when compared to the much slower estimated gate speeds of the existing quantum architectures cancels out the quadratic speedup essentially.
This means that, considering the existing difficulty level, the quantum computers as of now do not provide any significant advantage.
It needs some further improvements to achieve gate speeds of nearly 100 GHz. It is only then that quantum computers will be able to resolve the PoW 100 times faster than what it is doing now with the current technology.
Until then there is no significant threat to the Bitcoin PoW.
However, such remarkable improvement is highly unlikely within the next decade.
By that time even the conventional computers will be much faster.
Also, quantum technology will be more widespread by then and therefore there will not be a particular quantum enabled driving force that would dominate the field.
Now, take a look at the technical aspects.
As you may know, the Bitcoin PoW validates a block header as: h (header) ≤t, where h (·) = SHA256 (SHA256 (·)).
Based on this particular principle, the blockchain security does not depend on any agent with a probability factor of greater than 50% to solve the Proof of Work task first.
For that matter, the computing power of a standard computer will have to match with that of the quantum computer in order to perform this task.
Considering a random oracle model, Pr [h (header) ≤t] = t/2256, the probability is assumed to be uniform over all block headers that are created in the pool with the available transactions at any given point of time.
These block headers are well-formed and are set up by changing the nonce, the bits of the timestamp of the headers that are least significant, and the transactions incorporated in the blocks.
Comparing the two types of computers, on a conventional computer, the number of nonces and block headers needed to be hashed to find the one with a hash value of ‘t’ is D × 232. Here, D represents the difficulty level and is defined by D= 2224/t3.
On the other hand, for the random oracle model quantum computers the generic quantum approach is followed to solve the PoW task by using Grover’s algorithm.
According to this algorithm, when a database of N items are searched for a marked item, it is to be done with O(√N) queries made to the database, unlike the Ω(N)queries required by a conventional computer to perform the same task.
In this process, a function ‘f’ needs to be defined.
This will determine whether or not the block header is good. The formula used for it is:
f(x) = 0 if h (g(x)) >t and
f(x) = 1 if h (g(x)) ≤t.
However, the good thing about the quantum computer is that it can perform the mapping or calculate ‘f’ on a superposition of inputs. And, every application in this particular operation is expressed as an oracle call.
A quantum algorithm can search through it by using Grover’s algorithm to identify a good block header.
For that it has to work out #O=π/4√p10·N/t = π214√10·D oracle calls.
In order to run with such scaling, the Grover algorithm can be modified if there are no solutions existing or the number of them is not known beforehand.
Ideally, the number of hashes required to be performed is determined by the number of oracle calls.
There will be some extra overhead incurred for calculating every hash and to perform quantum error correction.
There is also the cost of constructing an appropriate block header which should also be taken into account.
Talking about quantum error correction codes, most of these use T gates to represent the time consuming gate instead of Toffoli gates.
In addition to that, it also needs some careful analysis to be done regarding the cost incurred in performing an SHA 256 function call.
The inversion about the average used in the Grover algorithm also needs to find the total T gate count for a single oracle call.
Ideally, the T gates in circuit decomposition can be parallelized only by approximately a factor of three.
Then, there is an additional overhead expense of the quantum computers in order to perform error correction as well as consider a number of tradeoffs in order to decide on a good quantum Error Correction Code.
These are:
- The number of Qubits used
- The tolerance to a specific physical error model
- The complexity of the logical gate
- The versatility of the subroutines and
- The amount of standard processing of error feedback and syndromes.
The analysis for estimating the quantum algorithm’s total runtime can be modified by implementing the surface code.
This will provide the advantage of a comparatively high local set of symptoms measurements and fault lenience error threshold.
For performing a blockchain attack by a single quantum computer, its performance will act as a function of two specific elements such as:
- The physical gate error rate represented as pg, which is actually an internal device pattern and
- The mining difficulty is represented as D and which is determined by the blockchain protocol.
Ideally, the effective hash rate of a quantum computer, represented as hQC, for all anticipated limits of probable clock speeds could be 50 GHz.
However, this hash rate may increase as the square root of the difficulty level.
Well, based on the current rate of improvements in the field of the superconducting quantum circuit technology, it can be said that there is still some time for the quantum computers to outpace the conventional computers.
It is yet to achieve a lot in order to influence the Proof of Work mechanism significantly with its current status.
And, when quantum computing technology improves significantly, it will not be enough for a single quantum computer to have the exceptional amount of hashing power that is required to overpower the classical mining computers.
It will not be exaggerating even an iota if it is said that, under given conditions and performance parameters, a set of 20 quantum computers running in parallel can achieve only 0.1% of the total hashing power.
It is only then the quantum computers will have a chance to attack on the mining pool with negligible inducement cost to reduce the revenue of the pool by only 10%.
Countermeasure
Though there is no significant threat posed by the quantum computers on the traditional computers used for crypto transactions or to the Proof of Work consensus of Bitcoin and other crypto coins, countermeasures should be ready.
Typically, as said earlier, a quantum computer may perform the Bitcoin PoW by using Grover search.
This will allow the computers to use far fewer hashes than that is required by a conventional computer.
With alternative Proof-of-Work mechanisms in place, the quantum computers will typically have fewer advantages.
Typically, the Proof of Work comes with these basic properties such as:
- Difficulty of a problem – This can be adjusted according to the computing power accessible in the network.
- Asymmetry – This makes it quite easy for the PoW mechanism to be verified if it has been completed successfully.
Ideally, a quantum computer cannot accomplish Proof of Work faster than a classical computer.
It is based on this particular factor that an alternative Proof of Work should be found that will work better.
A useful approach to achieve this is by focusing on memory intensive PoWs such as:
- Momentum that is based on discovering collisions in a hash function
- Cuckoo Cycle that is based on finding subgraphs in a random graph with constant size and
- Equihash that is based on the widespread centennial problem.
However, with the current Proof of Work in Bitcoin, the quantum computer will not be able to achieve a significant advantage if the speed is not significantly more than the constant size of the sub-graphs.
In the end, in simple words, it can be said that the specialized ASIC miners are quite capable enough to clock the speed of the quantum computers to be considered as their near equivalents.
Therefore, for about a decade or so, there seems to be no major threats posed to the Proof of Work consensus or Bitcoin and other crypto coins.
Conclusion
Therefore, these are the risks of Bitcoin and other crypto coins to quantum computer attacks.
However, as the article points out, the Proof of Work consensus used by Bitcoin is comparatively resistant to the comparatively fast quantum computers as of now.
I have special interest in crypto and intend to help common people to gain knowledge about the digital asset as well as its potential. Follow Me at Linkedin.
