Preface: Google has launched the quantum chip Willow, which can complete the calculation task that the fastest supercomputer today needs 10^25 years to complete in 5 minutes. Although it cannot pose a threat to algorithms such as RSA and ECDSA used in reality for the time being, it has posed new challenges to the security system of cryptocurrency, and the blockchain's anti-quantum migration is becoming increasingly important. AntChain OpenLabs cryptography experts will explain in detail 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 launched the quantum chip Sycamore in 2019 and achieved "quantum supremacy" for the first time. The achievement has been published in Nature on an expedited basis and has been praised on social media by the world's richest man Elon Musk and OpenAI CEO Sam Altman, as shown in Figures 1 and 2.
Figure 1[1]
Figure 2[2]
The new chip, Willow, has 105 qubits and has achieved the best performance in its category in both quantum error correction and random circuit sampling benchmarks. In the random circuit sampling benchmark, the Willow chip completed a computational task in just 5 minutes that would take today's fastest supercomputer 10^25 years to complete, a number that exceeds the age of the known universe and even the time scale known in physics.
Generally speaking, in quantum computing hardware, as the number of quantum bits increases, the computational process becomes more error-prone. However, Willow is able to reduce the error rate exponentially and keep it below a certain threshold, which is often an important prerequisite for the feasibility of quantum computing.
Hartmut Neven, head of Google Quantum AI, the Willow development team, said that as the first system below the threshold, it is the most convincing scalable logical qubit prototype to date, and Willow shows that large-scale practical quantum computers are feasible.
Impact on Cryptocurrencies
Google's achievement not only promoted the development of quantum computing, but also had a profound impact on multiple industries, especially in the field of blockchain and cryptocurrency. For example, the Elliptic Curve Digital Signature Algorithm (ECDSA) and the hash function SHA-256 are widely used in transactions of cryptocurrencies such as Bitcoin, where ECDSA is used to sign and verify transactions and SHA-256 is used to ensure data integrity. Research shows that the quantum algorithm proposed by scholar Grover [3] can crack SHA-256, but the required quantum bits are very large - hundreds of millions of quantum bits are required. However, the quantum algorithm proposed by scholar Shor in 1994 [4] can completely crack ECDSA, requiring only millions of quantum bits.
In a Bitcoin transaction, Bitcoin is 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, and the corresponding transaction type is called "pay to public key" (p2pk);
- The second type of wallet address uses the hash value of the recipient's ECDSA public key. The corresponding transaction type is called "pay to public key hash" (p2pkh), but the public key will be exposed when the transaction is made.
Of 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 recipient's ECDSA public key from the p2pk historical transactions. The Bitcoin block interval is about 10 minutes, during which everyone can obtain the recipient's ECDSA public key from active p2pkh transactions. Once an attacker with a quantum computer obtains the ECDSA public key, he can run the Shor quantum algorithm in the quantum computer to derive the corresponding ECDSA private key from the ECDSA public key, thereby occupying all the bitcoins of the private key. Even if the p2pkh transaction only has a 10-minute window period, it is enough for the Shor quantum algorithm to derive the private key.
Although the 105 qubits achieved by Google's Willow chip are still far less than the qubits required to crack the Bitcoin cryptographic algorithm, even so, the emergence of Willow heralds a smooth road to building large-scale practical quantum computers. Figure 3 shows Willow's latest achievements. The potential of quantum computers in cracking cryptographic algorithms is still worrying.
Cryptocurrencies like Bitcoin can maintain normal transactions before the birth of large-scale quantum computers, because it takes 300 trillion years for traditional computers to crack ECDSA private keys. Although Google's work cannot pose a threat to algorithms such as RSA and ECDSA used in reality for the time being, it can be seen that Google's Willow chip has posed new challenges to the cryptocurrency security system. How to protect the security of cryptocurrency under the impact of quantum computing will become a focus of common concern in the technology and financial sectors, and this essentially relies on quantum-resistant blockchain technology. This also makes it imperative to develop quantum-resistant blockchain technology, especially to upgrade existing blockchains to quantum-resistant, to ensure the security and stability of cryptocurrency.
Figure 3[5]
Quantum-resistant blockchain
Post-quantum cryptography (PQC) [6] is a new type of cryptographic algorithm that can resist quantum computing attacks. Although the Shor quantum algorithm and Grover quantum algorithm can crack classical cryptographic algorithms such as ECDSA, which are widely used in blockchain and cryptocurrency, they cannot crack post-quantum cryptographic algorithms. This means that even in the quantum era, post-quantum cryptographic algorithms will remain secure. Migrating blockchain to a quantum-resistant level is not only a frontier technology exploration, but also a way to ensure the long-term robust security of future blockchains.
AntChain OpenLabs has previously completed the construction of post-quantum cryptographic capabilities for the entire blockchain process, and has transformed a post-quantum version of the cryptographic library based on OpenSSL [7] to support multiple NIST standard post-quantum cryptographic algorithms [8] and post-quantum TLS communications. At the same time, in order to address the problem that the storage expansion of post-quantum signatures is more than 40 times that of ECDSA, by optimizing the consensus process and reducing memory read latency, the quantum-resistant blockchain TPS can reach about 50% of the original chain. This cryptographic library can be used as middleware to provide support for post-quantum migration in blockchain and other scenarios such as government affairs and finance.
At the same time, AntChain OpenLabs has also made some arrangements for the post-quantum migration of rich-function cryptographic algorithms, and 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 use of this protocol can overcome the shortcomings of the industry's post-quantum key management scheme that cannot support arbitrary threshold values, and at the same time, it has a performance improvement of more than 10 times that of the industry's scheme. 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 DJ, 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.
This article was written by AntChain OpenLabs. ZAN (X account @zan_team ) is based on the TrustBase open source technology system of AntChain OpenLabs.
