Is Bitcoin (BTC) Safe from Grover’s Algorithm? – Yahoo Finance

§ July 30th, 2021 § Filed under Quantum Computer Comments Off on Is Bitcoin (BTC) Safe from Grover’s Algorithm? – Yahoo Finance

When crypto investors discuss quantum computing, they invariably worry about its potential to undermine encryption. Quantum computers alone do not pose such a mortal threat, however. Its their capacity to exploit Shors algorithm that makes them formidable.

Thats because Shors algorithm can factor large prime numbers, the security behind asymmetric encryption.

Another quantum algorithm can potentially undermine the blockchain as well. Grovers algorithm helps facilitate quantum search capabilities, enabling users to quickly find values among billions of unstructured data points at once.

Unlike Shors algorithm, Grovers algorithm is more of a threat to cryptographic hashing than encryption. When cryptographic hashes are compromised, both blockchain integrity and block mining suffer.

Collision Attacks

One-way hash functions help to make a blockchain cryptographically secure. Classical computers cannot easily reverse-engineer them. They would have to find the correct arbitrary input that maps to a specific hash value.

Using Grovers algorithm, a quantum attacker could hypothetically find two inputs that produce the same hash value. This phenomenon is known as a hash collision.

By solving this search, a blockchain attacker could serendipitously replace a valid block with a falsified one. Thats because, in a Proof-of-Work system, the current blocks hash can verify the authenticity of all past blocks.

This kind of attack remains a distant threat, however. Indeed, achieving a cryptographic collision is far more challenging than breaking asymmetric encryption.

Mining Threats

A somewhat easier attack to pull off using Grovers algorithm involves proof-of-work mining.

Using Grovers search algorithm, a quantum miner can mine at a much faster rate than a traditional miner. This miner could generate as much Proof-of-Work as the rest of the network combined. Consequently, the attacker could effectively take over the blockchain and force consensus on any block they selected.

Story continues

A quantum miner might also use Grovers search algorithm to help facilitate the guessing of a nonce. The nonce is the number that blockchain miners are solving for, in order to receive cryptocurrency. Thats because Grovers algorithm provides a quadratic speedup over a classical computer (for now, ASIC-based mining remains considerably faster).

How fast is a quadratic speedup? Roughly stated, if a classical computer can solve a complex problem in the time of T, Grovers algorithm will be able to solve the problem in the square root of T (T).

Thus, any miner who can solve the nonce faster than other miners will be able to mine the blockchain faster as well.

Grovers algorithm could also be used to speed up the generation of nonces. This capability would allow an attacker to quickly reconstruct the chain from a previously modified block (and faster than the true chain), .In the end, a savvy attacker could substitute this reconstructed chain for the true chain.

Grovers algorithm may ultimately help make Proof-of-Work obsolete. Thats because there is no possible PoW system that is not susceptible to Grover speed-up. In the end, quantum actors will always have an advantage over classical ones in PoW-based blockchains. (allowing them) to either mine more effectively or (instigate) an attack (source).

Proof-of-Work Weaknesses

As bitcoin matures, the weaknesses inherent within PoW become ever-more evident. Miners are pitted against each other as if in a never-ending arms race This arms race is incentivized by the ability of larger mining pools to achieve economies of scale, a cost advantage that quickly erodes the capacity of individual miners to survive.

Of course, Proof-of-Stake is not without flaws. For instance, critics assert that it favors larger stakeholders (hence the claim that it enables the rich to get richer). These critics neglect to note that PoW is amenable to the same strategy (albeit with miners).

As this arms race comes to a head, any miner with the resources to do so will use quantum computing to achieve a competitive advantage. Combined with Grovers algorithm, a quantum-based miner would outperform other miners (most likely, small-and medium-sized miners). .

With access to quadratic speedup, any PoW coin will inevitably fall under the control of mega-cap institutions and governments. If so, regular investors and mid to large-cap enterprises risk getting priced out of the market. In particular, their devices will be either too expensive or prone to excessive regulation (much the same way that PGP encryption once was).

Summary

Shors algorithm undoubtedly poses the most immediate threat to bitcoin (namely, the potential to break ECDSA, its digital signature algorithm). Grovers algorithm is a distant second in this respect.

Grovers algorithm may someday pose a formidable challenge to PoW mining, however. And it could conceivably threaten cryptographic hashing as well. Any algorithm powerful enough to reverse engineer hash values would invariably undermine PoW itself.

Quantum Resistant Ledger (QRL) will ultimately offer protection against both.

For instance, a quantum-safe digital signature scheme named XMSS safeguards the coin from Shors algorithm.

Likewise, the QRL team will rely on Proof-of-Stake to head off mining-based attacks using Grovers search algorithm.

As you can see, the QRL team is thoroughly preparing for a post-quantum future. Their mission is an increasingly urgent one, as quantum computing continues to advance by leaps and bounds.

See more from Benzinga

2021 Benzinga.com. Benzinga does not provide investment advice. All rights reserved.

Read the original:

Is Bitcoin (BTC) Safe from Grover's Algorithm? - Yahoo Finance

Comments are closed.