BSV DevCon China 2021 | Blockchain and quantum technology - the past, present and future
Distinguished cadres and experts, greetings! I am Yuan Yong from the School of Mathematics of Renmin University of China. I am very glad to have this opportunity to attend the Shanghai Blockchain DevCon. I’d also like to thank the sponsor for the invitation. Today, my topic is Blockchain and Quantum Technology: the Past, Present and Future. As we all know, the blockchain is an underlying technology behind Bitcoin and many cryptocurrencies and also represents a significant breakthrough which has been assisting China in pursuing innovation of core technologies single-handedly.
In 2008, a scholar who went by the alias of Satoshi Nakamoto published a short article of 9 mere pages in a cryptography themed mailing list, which was titled “Bitcoin: A Peer-to-Peer Electronic Cash System”. This article is hailed as the White Paper or Genesis Thesis of Bitcoin and puts forward a vision as to the fundamentals of Bitcoin and the blockchain technology that powers it. In fact, over the first couple of years, the price of Bitcoin was close to zero, and few people knew about it.
But between 2013 and 2014, the price of Bitcoin went up to a marked extent momentarily, rising from almost nil to more than the then price of 1 oz of gold. It caused hordes of people from various industries, political and academic circles to flock to this market. Although the Bitcoin price plummeted shortly after, people have found that the blockchain technology behind the Bitcoin actually is of greater societal value and technical significance. Therefore, since 2015, both Chinese and foreign companies have been working together on the blockchain technology, which has been gaining traction all along. People think highly of the blockchain technology, regarding it as an emerging technology most likely to trigger off a new round of industrial revolution following the steam engine, electricity, IT and the Internet. China has got to quite an early start in the blockchain field.
In the 13th Five-Year Plan for Informatisation promulgated by the Central Government in 2016, it was required to intensify the efforts in conducting R&D of the infrastructure and pursing avant-garde technology in the sectors of AI, blockchain and quantum communication, etc. During the 18th group study session of the Political Bureau of the Central Committee of the Chinese Communist Party, convened by General Secretary Xi Jinping on October 24, 2019, it was stressed that the blockchain technology should be taken as a major breakthrough assisting China in pursuing innovation of core technologies single-handedly and also regarded as a national strategy. Besides, it was required to take the lead on the theoretical front in this field, come out top in terms of innovation and secure new advantages across the industry. Subsequently, many departments and commissions including the Ministry of Education, the Ministry of Science and Technology as well as the National Natural Science Foundation of China, etc. have pulled up their socks to help implement some measures for the purpose of achieving these goals. For instance, the Ministry of Education initiated a blockchain technology innovation plan for higher education institutions, proposing to build a galaxy of blockchain technology innovation centers in universities, foster and pool up blockchain task forces by 2025.
Besides China, the US, the European Union, Japan, South Korea, Russia and the UK have all been promoting the blockchain technology as a major national strategy. There are many definitions of a blockchain now. In 2016, we gave 2 definitions in an article titled: “Blockchain Technology: Status Quo and Perspective of Development”.
In a narrow sense, we define a blockchain as a specific data structure comprising a chain of data blocks in chronological order. We use cryptology to ensure the data structure is not altered or forged. This ledger can securely stores some simple, sequential data that can be self-verified in the system. In a broad sense, we define blockchain technology as using an encrypted chain structure to validate and store data, using the consensus of myriad distributed nodes to generate and renew data as well as using automated script codes. Personally, I'm very optimistic about the immensely promising smart contract technology which is used for programming and data operation in a brand-new decentralised infrastructure as well as a distributed computing paradigm.
Now let’s do a recap of the 3 features of the blockchain. The first one is decentralisation. The processes of validating, entering, storing, maintaining and transmitting blockchain data are all based on a distributed system structure.
Consensus algorithm and mathematical algorithm, instead of any centralised mechanism, are used to voluntarily strike up trust-based relations between certain trustless distributed nodes, enabling peer-to-peer transactions, coordination and collaboration in a decentralised way. The second feature is that it is extremely difficult to alter blockchain data. Once any data is written in a blockchain by way of consensus among nodes, no one can alter or deny the data unless he has got more than 51% of the Hash power.
I think these are the two most distinctive features of a blockchain, and cannot be achieved by the conventional next-generation information technology at the moment. The third feature is the security and fault-tolerance of a blockchain. We use cryptological algorithms, particularly the consensus algorithm as to myriad nodes, to pool up a large number of numerical examples to guarantee a high level of fault tolerance, security and credibility in a large-scale distributed system. Therefore, the security core of blockchain is built on the basis of cryptographic security and protection of consensus Hash power. As for quantum technology, the explosive Hash power is its feature.
Quantum technology was originated in the early twentieth century. In common parlance, a quantum is the smallest unit that can exhibit the properties of some substance or physical quantity. On the basis of the quantum, quantum physics and quantum mechanics were derived to describe the natural laws of the microworld.
We all know that the quantum has some wonderful properties. For example, the quantum state is inseparable. The quantum state, like the experiment of Schrödinger's cat, is superimposable and nonreplicable. In addition, the quantum state can be entangled. Thus, these features robustly support such subsequent experiments as the distribution of quantum keys and the quantum entanglement.
One of the basic principles of quantum computing is the superposition effect of quantum states. We know that in classical computers, each bit is a binary variable, and its data is either 0 or 1. Thus, a binary N-bit string can express only one number. But as for quantum bit, because of the feature of quantum superposition, every quantum bit could be 0 or 1 at the same time. So, an N-bit quantum bit is capable of expressing 2 to the Nth power, which is the basic principle of quantum computing.
So, we normally consider a quantum computer with N quantum bits to be exponentially faster than a standard classical computer, speaking from the angle of equivalence. Hence the rapid development of quantum computing in recent years. In January 2019, IBM launched the world's first standalone quantum computer, named Q System One. It has 20 quantum bits and can conduct operations of 2 to the 20th power in each step.
In September of the same year, Google’s R&D team presented a quantum computer prototype, called Sycamore. It has 53 quantum bits and adopts a superconducting route. It would take a traditional super-computer 10,000 years to finish such a task.
But Sycamore only needs 200 seconds. In December last year, the University of Science and Technology of China completed Jiuzhang, a quantum computer prototype, using the optical quantum route. Speaking in terms of equivalence, it is 10 billion times faster than Google's Sycamore. In May of this year, the University of Science and Technology of China’s R&D team, once again, successfully developed a 62-bit programmable superconducting quantum computer. A programmable two-dimensional quantum walk was achieved.
So, in the last two or three years, quantum computing has advanced greatly. On September 15, 2019, the Hefei Declaration was formed at the International Conference on Emerging Quantum Technology held in Hefei. Experts have reached a preliminary consensus on the three development stages of quantum computing. We believe for now quantum computing needs to go through three steps. The first step is to achieve quantum superiority, or what was originally called quantum hegemony.
In other words, we have to prove that the computational power of the quantum simulator for a specific question exceeds that of a classical supercomputer. Then this step has actually been repeatedly proven to be achieved in the last two or three years. The second step is to realise a specialised quantum simulation system with practical value. It can be useful in combinatorial optimisation, quantum chemistry, machine learning, etc.
This is a midterm goal. And the third step is the implementation of programmable and, in particular, fault-tolerant generic quantum computers. Thus, it can play a huge role in all aspects of classical password cracking, big data search, artificial intelligence, deep learning, etc. The third step is a long-term goal that requires painstaking and continuous efforts from our academic community. The computational power of quantum computing is very significant, so it obviously poses a threat to the blockchain. So, in response to the threat posed by quantum computing against the blockchain, we did an initial research in 2019.
A paper was born from that research. The paper was titled, Quantum Blockchain: can the blockchain integrated with quantum information technology resist quantum supremacy? The initial purpose of this paper was to discuss how quantum computing threatens the blockchain in terms of the offender-defender relationship between quantum computing and the blockchain. In turn, how can the blockchain withstand quantum computing? However, in the course of our research, we gradually came to realise that, the relationship between quantum computing and the blockchain is not a mere offender-defender or spear-shield one. We should combine these two tools to materialise the quantum blockchain. We can turn the offender-defender contradiction into a set of weapons that can be used to both offend and defend.
So, we think that quantum and blockchain are actually very complementary to each other, which is why we carried out these relevant studies later on. First of all, quantum computing is indeed a very big threat to the blockchain, which is mainly reflected in the impact on the underlying cryptography of the blockchain, especially asymmetric cryptography, or so-called public key cryptography. We know there are three main systems of asymmetric cryptography. The first one involves a RSA algorithm based on the challenging question of prime factorisation and an elliptic curve encryption algorithm based on the challenging question of discrete logarithm, as well as the discrete logarithm encryption algorithm based on the challenging question of discrete logarithm in the prime field. The essence of these three mathematically difficult questions in these three systems can actually be reduced to a one-way function, or a single trapdoor function.
This function is very easy to compute in the forward direction and very difficult to compute in the reverse direction, and it must be done with a considerable amount of work. To crack this one-way function, we need a great deal of Hash power which is not currently available in classical computers. But with the great development of quantum computers, this kind of Hash power can be accomplished in the future era of quantum. The security of this traditional cryptographic theory is based on the theory of computational complexity of such challenging questions. With the development of quantum computers, it is a mere matter of time to crack the theory of computational complexity.
So NIST, the National Institute of Standards and Technology, has also released a report on this post-quantum cryptography. In this report, the impact of quantum computing on some traditional cryptographic algorithms is listed. We can see that for symmetric encryption and hash functions, quantum computing has cut the difficulty of attack in half. For traditional Public Key Infrastructures (PKIs), such as RSA, ECDSA, ECDH, DSA, etc., quantum computing is capable of cracking these asymmetric encryption systems.
In the blockchain, we can see that among the algorithms frequently used in the blockchain, the hash functions like SHA-2 series and SHA-3 are commonly used. SHA-3 is now in the process of calling for standards, and there are a number of other hash functions. For symmetric encryption and hash functions, quantum computing has cut the difficulty of attack in half. As to some oft-seen asymmetric encryption mechanisms of the day, including the digital signature mechanism, quantum computing is able to completely crack them. So, the impact of quantum computing on blockchain cryptography is very significant. I will give two examples here.
The first one is the Shor’s algorithm that you all may be familiar with. We know that the security of RSA, ECDSA and DSA algorithms is based on such questions as large prime factorisation, discrete logarithm and elliptic curve discrete logarithm, etc. Shor's algorithm can solve these challenging computational questions in polynomial time. So, we say it can crack these common cryptographic algorithms.
For example, currently Bitcoin is using the ECDSA algorithm. We use an elliptic curve called Secp256k1. On top of this elliptical curve, we can see that the system calls for the underlying random number generator. After generating an 856-bit private key, we can use this elliptic curve algorithm to generate 65 public keys of our own. This is a one-way process.
Seeing from the difficulty of the challenging question of elliptic curve discrete logarithm, we can guarantee that it is relatively easy to derive a public key from a private key, and it’s extremely hard to do the opposite, i.e. deriving a private key from a public key. But if we use Shor's algorithm, we can then theoretically reconstruct the private key based on any given public key. In this way, we can use quantum computers to forge any digital signature, passing off as any blockchain user, and we can steal every cent from this digital asset or address. Existing studies have also found that solving the question of elliptic curve discrete logarithm as to ECDSA requires far fewer quantum bits than solving the question of prime factorisation as to the RSA algorithm.
Therefore, we normally think ECDSA is more susceptible to attacks. It is estimated a quantum computer with 1300-1600 quantum bits, which is still difficult to realise, could crack a 228-bit ECDSA. But in the near future, we are very confident we can achieve this level of capacity.
Then the second one is the Grover’s algorithm. This algorithm can effect square acceleration as to the time of searching on disordered arrays. Thus, it can speed up the searching process for hash collisions, which wields two impacts on the blockchain. The first impact is that I can use this algorithm to alter historical data. Using this algorithm, I can make it half as difficult to crack the SHA-256 hash function often seen in the Bitcoin realm.
Accordingly, I can use this quantum computer to alter the blockchain data by means of acceleration, search and hash collision, or even replace all the data on the chain. Then the second impact is that I can also monopolise the future data. Because nowadays, Bitcoin and many other cryptocurrencies all use the mainstream Proof of Work (PoW) consensus algorithm. This means that the consensus solution can be found quickly by computing a large number of hash functions. So, we can use Grover's algorithm to quickly find the consensus solution for each block by speeding up the hash collision searching process, helping the attacker monopolise the bookkeeping right of the blockchain.
That means we can disrupt transactions at will, prevent our own transactions from being recorded in the block, or launch real-time double-spending attacks. Take Bitcoin’s Hash power as an example. We know the “nonce” in Bitcoin is a 32-bit arbitrary random number, which is the 32nd power from 0 to 2.
Even if it is extended to 48 bits, it would take a classical computer 40 million seconds, or 465 days, to go through it, but with a quantum computer, it takes only 2 seconds to do it. This is very short for Bitcoin's 10-minute mining interval. Therefore, the threat posed by quantum computing against the blockchain is truly in existence. But is the blockchain really as useless as people have claimed, in the face of quantum computing? Of course, there are also many scholars who have raised opposing views.
For example, Craig Wright, the chief scientist at nChain, has proposed that the quantum threat is based on two fundamental assumptions. First, the bitcoin address must be reused and contain common knowledge. Second, we shall have an all-purpose, fault-tolerant quantum computer with a sufficient Hash power and a proper amount of quantum bits. The two assumptions must exist at the same time, if not, quantum mechanics will not exist in any foreseeable future. And as we know, for now, bitcoin addresses are not reused.
Then the second is that we are nowhere near having such Hash power, or all-purpose fault-tolerant quantum computers in particular. So, the two assumptions do not exist at the moment. So, while the quantum threat exists, we don’t need to worry much about it. Also in 2009, a Singaporean scientist named Bernstein proved that the quantum algorithm can reduce the cost of N-bit hash collisions from the original square acceleration to a third of N, which is also three accelerations. But this speed, even with such accelerations, is less cost-effective than the traditional hash collision circuit.
So, from the point of view of cost effectiveness, there is no incentive for miners to replace their existing ASIC mining machines with quantum computers. So, we don’t need to worry too much about the quantum threat. There are also some other experts who believe the PoW consensus will be able to withstand quantum computers in the next decade from the perspective of cost effectiveness.
So, it is probably too early for us to talk about the security threats caused by quantum computing. In 2018, we did a simple survey. Some preliminary views were formed. Overall, our team was not quite convinced that quantum computing poses a threat against the blockchain. Because the current argument is to use quantum algorithms to attack the current cryptographic algorithms after the great leap of quantum computing in twenty years, this is certainly inappropriate.
We need to take a long-term view. Quantum computing and the existing cryptographic system of Bitcoin are in a symbiotic relationship. If quantum computing launches an attack against the current cryptography system, the latter will surely come up with its own countermeasures. In addition, the Hash power of quantum computing is very impressive. But our consensus algorithms are not all based on Hash power.
In 2018, we did a simple survey. At that time there were already more than fifty consensus algorithms, and now there should be more than a hundred. Many of these 100-odd consensus algorithms are actually not based on Hash power. So, we can switch the Hash power and algorithms to resist the current quantum computing. So, the above is some simple research we did for the offender-defender relationship between quantum computing and the blockchain.
But the threat posed by quantum computing is also real. So, we now have two responsive solutions. The first one is called the quantum-resistant blockchain.
The idea of this solution is to still use anti-quantum cryptography to replace traditional cryptographic algorithms. So, this idea is still based on the challenging question of mathematics and on the assumption of computational security. Although many mathematically challenging questions are solvable by the current quantum computers.
But there are always some that are not solvable, like the coding question or the lattice question. We can use these specific mathematically challenging questions to design quantum-resistant cryptographic algorithms, and use these to replace traditional cryptographic algorithms in the existing blockchain system. This is called the anti-quantum blockchain. The second solution is called quantum blockchain. The idea is to use quantum cryptography, such as the quantum key distribution, to provide physically unconditional security.
This also means my safety is guaranteed when the attacker has infinite Hash power. This idea requires a fixed network of participating nodes with quantum capability. Both of these responsive solutions are evolving independently at the moment. Trend-wise, the development direction of quantum-resistant blockchain is mainly integrated into the current public blockchain system. Because the quantum blockchain solution requires nodes to be fixed and must be quantum capable, it’s more suitable for the current consortium blockchain system, especially in some important scenarios like finance and government affairs. In anti-quantum cryptography, which is also currently evolving very fast, we generally refer to it as post-quantum cryptography.
So far, mainstream quantum-resistant cryptographic schemes have included hash-based, code-based, lattice-based, multivariate-based, and hypersingular elliptic curve homologous password-based solutions. As far the existing study is concerned, for example, in 2018, researchers proposed the BPQS, a blockchain-enabled post-quantum signature scheme. This is the first post-quantum signature scheme using the blockchain or DAG structure to reduce the cost of signing. The signing is faster and the signature is shortered. Another is QRL, a quantum-resistant cryptocurrency that uses a hash-based signature scheme to provide quantum resistance instead of Bitcoin's elliptic curve.
It aims to provide a back-up version of Bitcoin for the quantum age, and of course, there are some other studies. Among other quantum blockchain ideas, the most influential one of the day is the 4-node Byzantine fault-tolerant quantum network. It was proposed by scholars of the Russian Quantum Center in 2018 and is based on the quantum key distribution technology in order to supplant the existing digital signature algorithm in the blockchain and materialise a prototype quantum blockchain network which is characterised by the distributed quantum computing and also bears unconditional security features in the urban network of optical fibers. It excels in adopting a consensus protocol in the form of the classic Byzantine Agreement so as to enable one-third of fault tolerance. Its disadvantage is even though the study was published in the leading periodical Nature, researchers generally consider the scheme to be incomplete, lacking some specific algorithms and security analysis, especially the complexity of its communication.
In a network with a large number of nodes, the communication is extremely complex. Even so, at the start of their research, researchers proposed various quantum blockchain systems in such an architecture by expanding the infrastructure, data structure and consensus algorithms, etc. For example, some scholars proposed a quantum blockchain based on the time entanglement technology. Time entanglement takes places in different time points.
Two particles which do not co-exist at the same time point can also get entangled. Thanks to the time entanglement technology, a new quantum blockchain/computer scheme was proposed in 2018. It is a technique using the time entanglement technology to replace the chain structure and timestamps in the blockchain technology, coding the data on the blockchain as photons, which have never coexisted in time, in the GZH state. For now, it is still a theoretical idea. The above mentioned is the relationship between blockchain and quantum computing. In fact, quantum technology includes not only quantum computing, but also quantum communication.
China is at the forefront of the world in quantum communication. A recent article was published by Academician Pan Jianwei's team at the University of Science and Technology of China, which summarised some of their team's current efforts in quantum communication. So far, we have constructed a satellite-earth integrated quantum communication network spanning a length of 4,600 kilometres.
We have quantum satellites in the space and the 32-node Beijing-Shanghai trunk route on the ground. Each major city has its urban network, which has grown relatively mature. And the network of quantum communication and blockchain are quite complementary to each other. By far, some scholars have proposed to use the blockchain to transform the existing quantum communication technology. One of the pain points in today’s quantum communication is that we are using the quantum key distribution network to deploy the quantum trunk line and have suffered from some concurrency conflicts, delays of relay, inconvenience of use.
In particular, the relay node can learn of the plaintext, which poses risks of privacy leakage. So, in 2020, researchers proposed to use the blockchain to construct quantum relay or trusted relay networks, negotiating a quantum key between the relay node and each node and incorporating the quantum key into our block as a transaction, so as to provide real-time services as to quantum keys. The above is a brief introduction of the blockchain and quantum technology, including some linkage between quantum computing and quantum communication. As for the future trend, we think breakthroughs may be made in the following respects. First, we can achieve a wide-area quantum communication network by use of the blockchain, because the quantum communication network and the distributed blockchain communication network are impressively complementary to each other.
Combine the two and you have a highly fault-tolerant, secure, low-cost communication network based on the blockchain. So, we can try to use the blockchain architecture to materialise the Byzantine fault tolerance mechanism in the realm of quantum communication, control the fault tolerance in the quantum relay network in a distributed way, transform the existing linear structure of the Beijing-Shanghai-trunk line based on high-cost trusted relay nodes into a wide-area quantum backbone network based on a low-cost and fault-tolerant node. This is still based on the Byzantine fault-tolerant quantum network with four Russian nodes, and we can improve the QKD-based key infection network accordingly.
The second potential direction is to combine quantum random numbers and the blockchain. We all know that today’s blockchain uses random numbers on computers, whereas quantum technology is able to generate random numbers in real sense. China has grown rather mature as far as the quantum random number generator is concerned. So, it is possible to combine quantum random numbers and consensus algorithms to design new consensus algorithms by use of the quantum random number generator.
It can fix such defects in the existing proof-based consensus as energy wastage, time wastage, poor performance and lengthy process of confirmation, so as to confirm the blockchain data in a secure, fast and efficient way and also solve some of the existing performance defects. In particular, it is able to alleviate the so-called impossible trinity problem. In addition, we can combine quantum random numbers with smart contracts, to design new types of applications as to smart contracts. Especially on some unpredictable occasions such as gaming, voting, auctioning, its security and fairness can be guaranteed.
The third direction is quantum digital currency. The research of quantum currency was actually started quite early. It was proposed and conducted initially in the 1960s and the 1970s, but the research is very slow and has met with some bottlenecks. That means that quantum states are difficult to prepare and maintain, giving rise to decoherence in the environment conveniently. Therefore, the quantum digital currency remains a hot topic although it has not been faring quite well.
We can capitalise on the superposition effect of quanta and the non-clonability of quantum states to achieve a godsend anti-counterfeiting quantum technology. The last potential direction is distributed quantum computing. The underlying logic of this direction is that the performance of quantum computers is growing exponentially in line with the controllable number of quantum bits.
Although there may be an exponential improvement in the performance with each new quantum-bit, the R&D cost will increase exponentially, too. So, we think that in the foreseeable future, we can use large-scale, low-cost, small-quantum-bit quantum computers and the blockchain to pool up the Hash power and make it a lot easier to adopt quantum computers. Because low-cost, small-quantum-bit quantum computers have become a mainstream choice by far.
e.g. 5-quantum-bit quantum computers have been put to commercial use, so that we can use the blockchain-based method to use them as quantum miners, in order to pool up their Hash power to make it easier to adopt quantum computers. This advantage can improve the collaboration efficiency of distributed quantum computing and accelerate the application of quantum computers. Of course, there are inherent disadvantages as well.
Because the distributed integration method cannot achieve the exponential acceleration effect of the original quantum computing. It can achieve linear acceleration only, which is to say that if I have some computers, I can achieve such acceleration by pooling up the Hash power via the blockchain. These are some of our initial thoughts on the combination of the blockchain and quantum computing and technology. Fellow experts, please feel free to comment and correct my remarks, thank you.