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

[ad_1]

When crypto investors discuss quantum computing, they invariably worry about its potential to undermine encryption. However, quantum computers alone are not such a deadly threat. It is their ability to exploit Shors’ algorithm that makes them formidable.

This is because Shors’ algorithm can take into account large prime numbers, the security behind asymmetric encryption.

Another quantum algorithm can potentially undermine the blockchain as well. The Grovers algorithm facilitates quantum search capabilities, allowing users to quickly find values ​​among billions of unstructured data points at a time.

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

Collision attacks

One-way hash functions help cryptographically secure a blockchain. Conventional computers cannot easily reverse engineer them. They should find the correct arbitrary entry that matches a specific hash value.

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

By solving this research, a blockchain attacker could accidentally replace a valid block with a forged one. This is because, in a proof of work system, the hash of current blocks can verify the authenticity of all past blocks.

This type of attack remains a distant threat, however. Indeed, achieving a cryptographic collision is much more difficult than breaking asymmetric encryption.

Mining threats

A slightly easier attack to perform using the Grovers algorithm involves extracting proof of work.

Using the 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 combined network. Therefore, the attacker could effectively take control of the blockchain and force consensus on any selected block.

The story continues

A quantum miner can also use the Grovers search algorithm to make it easier for a nonce to guess. The nonce is the number that blockchain miners resolve to receive cryptocurrency. This is because the Grovers algorithm provides quadratic acceleration compared to a conventional computer (for now, ASIC-based mining is still considerably faster).

What is the speed of a quadratic acceleration? Basically, if a classical computer can solve a complex problem in the time of T, the Grovers algorithm will be able to solve the problem in the square root of T (T).

Thus, any miner who is able to resolve the nuncio faster than other miners will also be able to mine the blockchain faster.

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

The Grovers algorithm can ultimately help make proof of work obsolete. This is because there is no possible PoW system that is not sensitive to Grover’s acceleration. Ultimately, quantum actors will always have an advantage over traditional actors in PoW-based blockchains. (allowing them) either to exploit more efficiently, or to (provoke) an attack (source).

Weaknesses in proof of work

As bitcoin matures, the inherent weaknesses of PoW become more and more evident. Miners are pitted against each other as in an endless arms race This arms race is driven by the ability of the largest mining pools to achieve economies of scale, a cost advantage that is rapidly eroding the survival capacity of the miners. individual minors.

Of course, Proof-of-Stake is not without its flaws. For example, critics claim that it favors larger stakeholders (hence the claim that it allows the rich to get richer). These critics neglect to note that PoW lends itself to the same strategy (albeit with minors).

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

With access to quadratic acceleration, any piece of PoW will inevitably fall under the control of mega-capitalized institutions and governments. If this is the case, regular investors and mid to large cap companies risk being left out of the market. In particular, their devices will either be too expensive or subject to overregulation (much like PGP encryption once was).

Summary

Shors’ algorithm is arguably the most immediate threat to bitcoin (i.e., the potential to break ECDSA, its digital signature algorithm). Grovers’ algorithm is far behind in this regard.

However, the Grovers algorithm could one day present a formidable challenge for PoW mining. And it could also threaten crypto hashing. Any algorithm powerful enough to reverse engineer the hash values ​​would invariably undermine the PoW itself.

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

For example, a quantum-secure digital signature scheme named XMSS protects part of Shors’ algorithm.

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

As you can see, the QRL team is preparing in depth for a post-quantum future. Their mission is increasingly urgent, as quantum computing continues to progress in leaps and bounds.

See more Benzinga

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

[ad_2]