Google Willow is here! Can Bitcoin withstand the impact of quantum computing?

1、 Quantum computing hits: Bitcoin security faces new tests

The two “killer algorithms” of quantum computing are: Grover algorithm and Shor algorithm They pose a direct threat to Bitcoin’s mining and signature mechanisms.

2.1 Threats to Mining Mechanisms

Threat source: Grover algorithm
The Grover algorithm can shorten the time required for brute force cracking of hash functions O(2^n) Reduced to O(2^(n/2)) This means that the speed of calculating mining targets is faster, but It cannot completely crack the mechanism of Hash functions 。

Actual impact
The essence of the Grover algorithm is to “accelerate search”, and its effect is similar to that of a more powerful mining device, rather than directly compromising the security of the mining algorithm. Even with the improvement of quantum computing power, the difficulty of mining will dynamically adjust, and the competition for computing power in the network remains effective.

2.2 Threats to Transaction Signature

Threat source: Shor algorithm
The Shor algorithm is the “ace algorithm” in quantum computing, specifically designed to solve prime factorization and discrete logarithm problems of large integers. Bitcoin’s ECDSA signature relies on the discrete logarithm problem…