The Sword of Damocles Over Blockchain: Understanding the Impact of Google’s New Quantum Chip on Blockchain

Introduction: Google has launched the quantum chip Willow, which performed a standard benchmark computation in under 5 minutes that would take one of today’s fastest supercomputers 10^25 years. Although it currently does not pose a threat to algorithms in use like RSA and ECDSA, it presents a new challenge to the security system of cryptocurrencies. The resilience to quantum migration in blockchain is becoming increasingly important. Cryptography experts from AntChain Open Labs will provide a detailed analysis of the impact of this black technology on blockchain.

Google's New Quantum Chip Willow

On December 10, Google announced the launch of its latest quantum computing chip Willow. This innovative technology is another breakthrough since Google's introduction of the quantum chip Sycamore in 2019, which achieved "quantum supremacy" for the first time. The achievement has been urgently published in Nature and received praise from the world's richest man, Elon Musk, and the CEO of OpenAI, Sam Altman, on social media, as shown in Figures 1 and 2.

Figure 1 [1]

Figure 2 [2]

The new chip Willow is equipped with 105 qubits, and it has achieved the best performance in both benchmark tests of quantum error correction and random circuit sampling. In the random circuit sampling benchmark test, Willow performed a standard benchmark computation in under 5 minutes that would take one of today’s fastest supercomputers 10^25 years — a number that exceeds the age of the known universe and even the time scale known to physics.

Generally speaking, as the number of qubits increases in quantum computing hardware, the computation process is more prone to errors. However, Willow is able to achieve an exponential decrease in error rates and keep the error rate below a certain threshold. This is often an important prerequisite for making quantum computing practical.

Hartmut Neven, the leader of Willow's R&D team Google Quantum AI, stated that as the first system to operate below the threshold, this is the most convincing and scalable logic qubit prototype to date, demonstrating the feasibility of large-scale practical quantum computing.

The Impact on Cryptocurrency

This achievement by Google has not only advanced the development of quantum computing but also had a profound impact on multiple industries, especially in the blockchain and cryptocurrency. For example, the Elliptic Curve Digital Signature Algorithm (ECDSA) and the SHA-256 hash function are widely used in transactions involving cryptocurrencies such as Bitcoin, where ECDSA is used for signing and verifying transactions, and SHA-256 is used to ensure data integrity. Researches show that the quantum algorithm proposed by Grover [3] could potentially crack SHA-256, but would require a large number of qubits - on the order of hundreds of millions. However, the quantum algorithm proposed by Shor in 1994 [4] has the ability to completely break ECDSA, requiring only a few million qubits.

In Bitcoin transactions, bitcoins are transferred from one wallet address to another. Bitcoin wallet addresses are divided into the following two categories：

• The first type of wallet address directly uses the recipient's ECDSA public key, corresponding to the transaction type known as "pay to public key" (p2pk)；
• The second type of wallet address uses the hash of the recipient's ECDSA public key, corresponding to the transaction type known as "pay to public key hash" (p2pkh), but the public key is exposed during the transaction.

In these two types of transactions, p2pkh transactions account for the majority. Since all Bitcoin transactions are publicly obtained, anyone can obtain the recipient's ECDSA public key from past p2pk transactions. The block interval time of Bitcoin is about 10 minutes, during which everyone can obtain the recipient's ECDSA public key based on active p2pkh transactions. Once attackers with a quantum computer obtain the ECDSA public key, they can use Shor's quantum algorithm to derive the corresponding ECDSA private key from the public key and take control of all bitcoins associated with that private key. Even with only a brief period of 10 minutes for p2pkh transactions, it is enough for Shor's quantum algorithm to derive the private key.

Although Google's Willow chip has only reached 105 qubits, much smaller than the number of qubits needed to crack Bitcoin cryptographic algorithms, its existence signals a promising path toward building large-scale practical quantum computers. Figure 3 shows the latest achievement of Willow, and the potential of quantum computers in cracking cryptographic algorithms is still concerning.

Cryptocurrencies like Bitcoin can maintain normal operation before the emergence of large-scale quantum computers, as traditional computers would require 300 trillion years to crack ECDSA private keys. While Google's Willow chip has not posed a threat to real-world algorithms like RSA and ECDSA yet, it is clear that Willow has presented new challenges to the security of cryptocurrency systems. Protecting the security of cryptocurrencies in the face of quantum computing impact will become a focus of attention for both the technology and financial community, which essentially depends on quantum-resistant blockchain technology. It also makes the development of quantum-resistant blockchain technology, especially the upgrading of existing blockchains to be quantum-resistant, a top priority to ensure the security and stability of cryptocurrencies.

图3 [5]

Post-Quantum Blockchain

Post-quantum cryptography (PQC), a new type of cryptographic algorithm, can be resistant to quantum computing attacks. Although Shor's quantum algorithm and Grover's quantum algorithm can break classical cryptographic algorithms such as ECDSA, which are widely used in blockchain and cryptocurrencies, they cannot break post-quantum cryptographic algorithms. It means that even in the quantum era, post-quantum cryptographic algorithms remain secure. Migrating blockchain to a quantum-resistant level is not only an exploration of cutting-edge technology but also to ensure the long-term security and robustness of blockchain in the future.

AntChain Open Labs has previously completed the post-quantum cryptographic capability construction for the entire blockchain process and has reformed a post-quantum version cryptographic library based on OpenSSL [7], supporting multiple NIST standard post-quantum cryptographic algorithms [8] as well as post-quantum TLS communication. At the same time, in response to the problem of 40 times or more storage expansion for post-quantum signatures compared to ECDSA, the library has optimized the consensus process and reduced memory read delays, enabling the TPS of post-quantum blockchain to reach around 50% of the original chain. This cryptographic library can serve as middleware to facilitate the post-quantum migration for blockchain and other scenarios such as government affairs and finance.

At the same time, AntChain Open Labs is also making progress in the post-quantum migration of advanced cryptographic algorithms and has participated in the development of a distributed key management protocol for the NIST post-quantum signature standard algorithm Dilithium. This is the industry's first efficient post-quantum distributed threshold signature protocol. The protocol overcomes the limitation of industry post-quantum key management solutions in supporting arbitrary threshold values and also provides a performance improvement of over 10 times compared to similar solutions in the industry. The research effort has been published in the top journal in the field of information security, IEEE Transactions on Information Forensics and Security [9].

Ref

[1] https://x.com/sundarpichai/status/1866167562373124420

[2] https://x.com/sama/status/1866210243992269271

[3] Grover L K. A fast quantum mechanical algorithm for database search[C]//Proceedings of the 28th annual ACM symposium on Theory of computing. 1996: 212-219.

[4] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring[C]//Proceedings 35th annual symposium on foundations of computer science. 1994: 124-134.

[5] https://blog.google/technology/research/google-willow-quantum-chip/

[6] Bernstein D J, Lange T. Post-quantum cryptography[J]. Nature, 2017, 549(7671): 188-194.

[7] https://github.com/openssl/openssl

[8] https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4

[9] Tang G, Pang B, Chen L, Zhang Z. Efficient Lattice-Based Threshold Signatures With Functional Interchangeability[J]. IEEE Transactions on Information Forensics and Security. 2023, 18: 4173-4187.

[10] Cozzo D, Smart N. Sharing the LUOV: threshold post-quantum signatures[C]// Proceedings of the 17th IMA Conference on Cryptography and Coding - IMACC. 2019: 128–153.