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 blockchains 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 in an expedited manner and has been praised on social media by the worlds 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 best-in-class performance in both quantum error correction and random circuit sampling benchmarks. In the random circuit sampling benchmark, the Willow chip completed a calculation task in 5 minutes that would take todays fastest supercomputer 10^25 years to complete, a number that exceeds the age of the known universe and even the known time scale of 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 team that developed Willow, 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
Googles 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” (p2p k);
The second type of wallet address uses the hash value of the recipients ECDSA public key. The corresponding transaction type is called pay to public key hash (p2p kh), but the public key will be exposed when making transactions.
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 recipients ECDSA public key from the p2p k historical transactions. The block interval of Bitcoin is about 10 minutes, during which everyone can obtain the recipients ECDSA public key from active p2p kh 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 p2p kh 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 Googles 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 the latest results of Willow. 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 Googles work cannot pose a threat to algorithms such as RSA and ECDSA used in reality for the time being, it can be seen that Googles 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 the Grover quantum algorithm can crack classical cryptographic algorithms such as ECDSA that are currently 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 cutting-edge 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], supporting multiple NIST standard post-quantum cryptographic algorithms [8] and post-quantum TLS communications. At the same time, in order to address the problem that post-quantum signatures have more than 40 times the storage expansion of ECDSA, by optimizing the consensus process and reducing memory read latency, the TPS of the quantum-resistant blockchain can reach about 50% of the original chain. This cryptographic library can be used as middleware to provide support for post-quantum migration of 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 industrys first efficient post-quantum distributed threshold signature protocol. The use of this protocol can overcome the shortcomings of the industrys 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 industrys 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 35 th 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.
