Preface: Google has launched the quantum chip Willow, which can complete the calculation tasks that the fastest supercomputer today would take 10^25 years to complete in just 5 minutes. Although it cannot currently pose a threat to algorithms such as RSA and ECDSA used in practice, it poses new challenges to the security system of cryptocurrencies, making the quantum resistance of blockchains increasingly important. AntChain OpenLabs cryptography experts will give you a detailed explanation of the impact of this black technology on blockchains.
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 launch of the Sycamore quantum chip in 2019, which first achieved "quantum supremacy". The achievement has been published urgently in Nature 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.
Figure 1 [ 1 ]
Figure 2 [ 2 ]
The new Willow chip has 105 Threshold bits 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 would take the fastest supercomputer today 10^25 years in just 5 minutes, a number that exceeds the age of the known universe and even exceeds the time scale known to physics.
Generally speaking, as the number of Threshold bits increases in quantum computing hardware, the computation process becomes more prone to errors. However, Willow can achieve an exponential decrease in the error rate and keep the error rate below a certain Threshold. This is often an important prerequisite for the practical feasibility of quantum computing.
Hartmut Neven, the head of the Willow research and development team Google Quantum AI, said that as the first system below the Threshold, this is the most convincing scalable logical Threshold bit prototype to date, and Willow shows that large-scale practical quantum computers are feasible.
Impact on Cryptocurrencies
Google's achievement not only promotes the development of quantum computing, but also has a far-reaching impact on multiple industries, especially in the field of blockchains and cryptocurrencies. 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. Studies have shown that the quantum algorithm proposed by scholar Grover [ 3 ] can crack SHA-256, but it requires a very large number of Threshold bits - hundreds of millions of Threshold bits. However, the quantum algorithm proposed by scholar Shor in 1994 [ 4 ] can completely crack ECDSA, requiring only millions of Threshold bits.
In Bitcoin transactions, Bitcoin is transferred from one wallet address to another. Bitcoin wallet addresses are divided into two categories:
The first type of wallet address directly uses the ECDSA public key of the payee, and the corresponding transaction type is called "pay to public key" (p2p k);
The second type of wallet address uses the hash value of the payee's ECDSA public key, and the corresponding transaction type is called "pay to public key hash" (p2p kh), but the public key will be exposed during the transaction.
Of these two types of transactions, p2p kh transactions account for the largest proportion. Since all Bitcoin transactions are public, this means that anyone can obtain the ECDSA public key of the payee from the p2p k historical transactions. The Bitcoin block interval is about 10 minutes, during which time everyone can obtain the ECDSA public key from the active p2p kh 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 control all the Bitcoin in that private key. Even if the p2p kh transaction window is only 10 minutes, it is enough for the Shor quantum algorithm to derive the private key.
Although Google's Willow chip has only reached 105 Threshold bits, which is far less than the Threshold bits required to crack the Bitcoin cryptographic algorithm, the emergence of Willow nevertheless indicates a broad road to building large-scale practical quantum computers, and Figure 3 shows the latest results of Willow, the potential of quantum computers in cracking cryptographic algorithms is still a concern.
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 cannot currently 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 be a common concern of 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 quantum-resistant upgrade of existing blockchains, an urgent task to ensure the security and stability of cryptocurrencies.
Figure 3 [ 5 ]
Quantum-Resistant Blockchains
Post-quantum cryptography (PQC) [ 6 ] is a class of new 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 even in the quantum era, post-quantum cryptographic algorithms remain secure. Migrating blockchains to quantum-resistant levels is not only a frontier technology exploration, 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 [ 7 ] -based 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, by optimizing the consensus process and reducing memory access latency, the TPS of quantum-resistant blockchains can reach about 50% of the original chain. This cryptographic library can serve as middleware to assist the post-quantum migration of blockchains and other scenarios such as government and finance.
Meanwhile, AntChain OpenLabs has also made 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, which 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 28 th annual ACM symposium on Theory of computing. 1996: 212-219.
[ 4 ] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring[C]//Proceedings 35 th 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 17 th IMA Conference on Cryptography and Coding - IMACC. 2019: 128 – 153.
This article was written by AntChain OpenLabs, and ZAN (X account @zan_team) is based on the TrustBase open source and open technology system of AntChain OpenLabs.
