The Sword of Damocles of Blockchain: An article to understand the impact of Google's new quantum chip on blockchain

Post-quantum cryptography (PQC) [6] is a class of new cryptographic algorithms that can resist quantum computing attacks.

Author: ZAN Team

Foreword: Google has launched the quantum chip Willow, which can complete the calculation task that the current fastest supercomputer needs 10^25 years to complete in just 5 minutes. Although it cannot currently threaten the algorithms used in reality, such as RSA and ECDSA, it poses new challenges to the security system of cryptocurrencies. The migration of blockchain to resist quantum attacks is becoming increasingly important. AntChain OpenLabs cryptography experts will give you a detailed explanation of the impact of this black technology on blockchain.

Google Launches 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 quantum chip Sycamore first achieved "quantum supremacy" in 2019. The achievement has been published in Nature on an expedited basis and has received likes from the world's richest man Elon Musk and OpenAI CEO Sam Altman on social media, as shown in Figures 1 and 2.

The new Willow chip has 105 qubits and has achieved the best performance in both quantum error correction and random circuit sampling benchmarks. In the random circuit sampling benchmark, the Willow chip completed a calculation task that the current fastest supercomputer would need 10^25 years to complete, in just 5 minutes, which exceeds the known age of the universe and even the known timescales of physics.

Generally, as the number of qubits increases in quantum computing hardware, the computation process becomes more prone to errors. However, Willow is able to achieve an exponential decrease in error rate, bringing the error rate below a certain threshold. This is often a crucial prerequisite for the practical feasibility of quantum computing.

Hartmut Neven, the head of the Willow research and development team at Google Quantum AI, stated that as the first sub-threshold system, Willow represents the most compelling scalable logical qubit prototype to date, and demonstrates the feasibility of large-scale practical quantum computers.

Impact on Cryptocurrencies

Google's achievement not only advances the development of quantum computing, but also has far-reaching impacts on various industries, particularly in the field of blockchain and cryptocurrencies. For example, the Elliptic Curve Digital Signature Algorithm (ECDSA) and the hash function SHA-256 are widely used in transactions of cryptocurrencies like Bitcoin, where ECDSA is used to sign and verify transactions, and SHA-256 is used to ensure data integrity. Studies have shown that Grover's quantum algorithm [3] can break SHA-256, but it requires a very large number of qubits - hundreds of millions. However, Shor's quantum algorithm [4] can completely break ECDSA, requiring only millions of qubits.

In Bitcoin transactions, Bitcoins are transferred from one wallet address to another. Bitcoin wallet addresses can be classified into the following two categories:

• The first type of wallet address is the direct use of the recipient's ECDSA public key, and the corresponding transaction type is called "pay to public key" (p2pk);
• The second type of wallet address is the use of the hash value of the recipient's ECDSA public key, and the corresponding transaction type is called "pay to public key hash" (p2pkh), but the public key will be exposed during the transaction.

Among these two types of transactions, p2pkh transactions account for the largest proportion. Since all Bitcoin transactions are public, this means that anyone can obtain the ECDSA public key of the recipient from the historical p2pk transactions. The Bitcoin Block interval is about 10 minutes, during which time everyone can obtain the ECDSA public key of the recipient from the active p2pkh transactions. Once an attacker with a quantum computer obtains the ECDSA public key, they can run the Shor quantum algorithm on the quantum computer to derive the corresponding ECDSA private key, and thus take possession of all the Bitcoins of that private key. Even if the p2pkh transaction has a window period of only 10 minutes, it is enough for the Shor quantum algorithm to derive the private key.

Although Google's Willow chip has already reached 105 quantum bits, which is still far less than the quantum bits required to crack the Bitcoin cryptographic algorithm, the emergence of Willow nevertheless indicates a broad path to building large-scale practical quantum computers, and Figure 3 shows the latest results of Willow, which are still concerning in terms of the potential of quantum computers to crack cryptographic algorithms.

Cryptocurrencies like Bitcoin can maintain normal transaction operations before the emergence of large-scale quantum computers, as traditional computers would take 300 trillion years to crack the ECDSA private key. Although Google's work is currently unable to pose a threat to algorithms such as RSA and ECDSA used in practice, it can be seen that Google's Willow chip has posed new challenges to the security system of cryptocurrencies. How to protect the security of cryptocurrencies under the impact of quantum computing will become a focus of common concern for the technology and financial sectors, and this essentially depends on quantum-resistant blockchain technology. This also makes the development of quantum-resistant blockchain technology, especially the upgrading of existing blockchains to be quantum-resistant, an urgent task to ensure the security and stability of cryptocurrencies.

Quantum-Resistant Blockchain

Post-quantum cryptography (PQC) [6] is a new class of cryptographic algorithms that can resist quantum computing attacks. Although Shor's quantum algorithm and Grover's quantum algorithm can crack the classical cryptographic algorithms such as ECDSA that are widely used in blockchains and cryptocurrencies, they cannot crack post-quantum cryptographic algorithms. This means that post-quantum cryptographic algorithms remain secure even in the quantum era. Migrating blockchains to quantum-resistant levels is not only an exploration of frontier technology, but also to ensure the long-term robust security of blockchains in the future.

AntChain OpenLabs has previously completed the post-quantum cryptographic capability construction for the entire blockchain process, and has modified an OpenSSL-based [7] post-quantum cryptographic library that supports 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 more than 40 times storage expansion of post-quantum signatures compared to ECDSA, through optimizing the consensus process and reducing memory access latency, the TPS of the quantum-resistant blockchain can reach about 50% of the original chain. This cryptographic library can serve as middleware to provide assistance for the post-quantum migration of blockchains and other scenarios such as government affairs and finance.

Meanwhile, AntChain OpenLabs has also made some deployments in the post-quantum migration of functional cryptographic algorithms, participating in the development of a distributed key management protocol for the NIST post-quantum signature standard algorithm Dilithium, which is the industry's first efficient post-quantum distributed threshold signature protocol. This protocol can overcome the shortcomings of industry post-quantum key management solutions that cannot support arbitrary threshold values, and also has more than 10 times performance improvement over industry solutions. The related work has been published in the top security journal 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.

Disclaimer: As a blockchain information platform, the articles published on this site only represent the personal views of the authors and guests, and are not related to the position of Web3Caff. The information in the articles is for reference only and does not constitute any investment advice or offer, and please comply with the relevant laws and regulations of your country or region.