Making Blockchains Unbreakable in the Age of Quantum Computers

Table of Links

Abstract and 1. Introduction

2. Context

2.1. Quantum computing as a threat to cryptography

2.2. Current approaches for quantum-safe cryptography

2.3. Blockchain and the LACChain Blockchain Network

3. The vulnerabilities of blockchain technology with the advent of quantum computing

4. A Proposal for a Quantum-Safe Blockchain Network

5. Implementation and 5.1 Generation and distribution of quantum entropy

5.2. Generation of Post-Quantum Certificates

5.3. Encapsulation of the communication between nodes using quantum-safe cryptography

5.4. Signature of transactions using post-quantum keys

5.5. On-chain verification of post-quantum signatures

6. Conclusions and next steps, Acknowledgements, and References

Abstract

This paper describes the work carried out by the Inter-American Development Bank, the IDB Lab, LACChain, Cambridge Quantum Computing (CQC), and Tecnologico de Monterrey to identify and eliminate quantum threats in blockchain networks.

The advent of quantum computing threatens internet protocols and blockchain networks because they utilize non-quantum resistant cryptographic algorithms. When quantum computers become robust enough to run Shor’s algorithm on a large scale, the most used asymmetric algorithms, utilized for digital signatures and message encryption, such as RSA, (EC)DSA, and (EC)DH, will be no longer secure. Quantum computers will be able to break them within a short period of time. Similarly, Grover’s algorithm concedes a quadratic advantage for mining blocks in certain consensus protocols such as proof of work.

Today, there are hundreds of billions of dollars denominated in cryptocurrencies that rely on blockchain ledgers as well as the thousands of blockchain-based applications storing value in blockchain networks. Cryptocurrencies and blockchain-based applications require solutions that guarantee quantum resistance in order to preserve the integrity of data and assets in their public and immutable ledgers. We have designed and developed a layer-two solution to secure the exchange of information between blockchain nodes over the internet and introduced a second signature in transactions using post-quantum keys. Our versatile solution can be applied to any blockchain network. In our implementation, quantum entropy was provided via the IronBridge Platform from CQC and we used LACChain Besu as the blockchain network.

1 Introduction

Quantum computing, one of the most recent cross-pollination efforts between physics and computer science, is a scientific and engineering field focused on developing information processing devices and algorithms based on quantum mechanics [1–7]. Quantum computing is now an established research field with solid theoretical and experimental results [8–12]. Furthermore, high-tech businesses across various sectors are increasingly experimenting with quantum computing technological solutions [13–16].

Since the early days of quantum computing, the role of quantum algorithms and quantum protocols in information security has been a crucial issue. On the one hand, Shor’s algorithm [17] could be used to break public-key cryptography protocols. On the other hand, Quantum Key Distribution schemes provide security levels to information transmission that are not based on mathematical conjectures but instead on the properties of quantum mechanics [18]. Quantum entropy provides perfect randomness and strong cryptographic keys based on quantum mechanics [19]. Post-Quantum Cryptography encompasses a new generation of algorithms for the creation of asymmetric keys that are thought to be resistant to attacks by quantum computers [20].

Currently, blockchain [21] is the most popular technology amongst emerging applications for decentralized data sharing and storage. The design and implementation of blockchain networks makes extensive use of cryptography protocols; thus, studying the potential uses of quantum computing to both weaken and strengthen blockchain technologies is essential to ensuring its future reliability.

The rest of this paper is divided as follows. Section 2 presents an introductory review of Quantum Computing, Quantum Key Distribution, Post-Quantum Cryptography, blockchain, and the LACChain Blockchain Network; Section 3 analyzes relevant vulnerabilities of blockchain within the context of quantum computing technologies; Section 4 introduces our solution for guaranteeing quantum-resistance in blockchain networks and describes the implementation carried out in the LACChain Blockchain Network; Section 5 explores several key implementation matters; Section 6 presents conclusions and future directions.

2 Context

2.1 Quantum computing as a threat to cryptography

Theoretical results, such as Shor’s algorithm [17], and state-of-the-art quantum computing technology in conjunction with expected near-to-mid future scalability and robust developments have attracted the attention of international standards agencies in cyber security and cryptography, including NIST [22], NSA [23], and ETSI [24]. They have made critical warnings that running some quantum algorithms on full-scale quantum computers will necessitate the protection of internet and telecommunication information exchanges for widely used cryptography protocols. Most notably, NIST is currently running a post-quantum cryptography competition for standardization to replace existing cryptographic algorithms that are susceptible to breakage using quantum computers [25].

In general, physical channels currently used to transmit digital information are unprotected (e.g., optical fibers or wireless transmissions) and the security of data exchanges within these channels relies on cryptographic protocols. It is only a matter of time before large and robust quantum computers capable of breaking current cryptographic protocols are built. It is crucial that we be prepared for these future technologies, especially in order to investigate the transition to quantumsafe cryptography for blockchain technologies.

2.2 Current approaches for quantum-safe cryptography

Discussions on quantum computers and cryptography usually surround two main areas of cryptography that are thought to resist attacks by large and robust quantum computers: quantum key distribution and post-quantum cryptography.

2.2.1 Quantum Key Distribution

Quantum Key Distribution (QKD) refers to quantum protocols for the co-creation of private symmetric keys between two parties using quantum and classical channels (e.g., optical fibers and wireless channels) by codifying private key bits into quantum states. If these quantum states are intercepted and observed by any eavesdropper, the information they contain (i.e., the bits of the key) is modified, and therefore the key is corrupted and the eavesdropper is detected. Best known QKD protocols are BB84 [26, 27] and E91 [28].

An illustrative example of a QKD implementation is the BB84 protocol using polarized photons. In this protocol, we have a sender (Alice), a recipient (Bob), and an eavesdropper (Eve). Alice codes the bits of a private key to share with Bob using non-orthogonal quantum states, such as bit value 0 using either |0i or |+> and bit value 1 using |1i or |−>. Then, photons are sent by Alice to Bob. Due to the properties of measurement in quantum mechanics, Eve’s eavesdropping activities will eventually be detected (that is, Eve’s activities will leave a trace that will eventually be detected by Alice and Bob) and, consequently, the protocol will stop and start over at a later stage [29, 30].

QKD protocols such as BB84 and E91 have been successfully implemented since 2003. However, QKD is not fully scalable today because ground-based key exchanges using optical fibers are limited to a few hundreds kilometers due to the degradation of the quantum states containing the keys [31]. Additionally, ground-to-satellite key exchanges require sophisticated infrastructure for generation, transmission, and reception of quantum keys [32, 33]. The scalability of these networks depends on the development of quantum repeaters, which require very sophisticated quantum memories. This is still an area under development [34, 35]. For these reasons, QKD has been discarded as a feasible solution to provide quantum safeness to blockchain networks today. However, this may change in the future as NSA, NIST, and ETSI, among others, have declared that quantum cryptography (such as QKD) would be the only alternative for long term secure encryption [22–24].

2.2.2 Post-Quantum Cryptography

Existing symmetric standards such as AES have already well-understood variants that are believed to provide adequate security against quantum adversaries. In contrast, it is well known that public (asymmetric) key cryptographic protocols such as RSA [36, 37], (Elliptic Curve) Digital Signature Algorithm [38], and (Elliptic Curve) Diffie-Hellman [39, 40] are considered vulnerable to quantum attacks.

Post-Quantum Cryptography (PQC) refers to a new generation of asymmetric algorithms that cannot be broken by Shor’s algorithm. Unlike QKD, PQC does not rely on any underlying quantum processes but rather on more complex mathematical problems. The main focus areas for postquantum algorithms to generate quantum-safe asymmetric key pairs are:

• Hash-based Cryptography, based on the security of hash functions.

• Code-based Cryptography, based on the difficulty of decoding generic linear code.

• Lattice-based Cryptography, based on the difficulty of well-studied lattice problems (e.g., shortest vector problem).

• Multivariate Cryptography, based on multivariate polynomials over a finite field.

As mentioned above, there is a standardization process being conducted by NIST which started in August 2016 with a request for comments [25]. This process, which called for submissions in the areas of “Public-key Encryption and Key Establishment Mechanisms (KEM)” and “Digital Signature Algorithms” announced the final and alternate rounds of in July 2020 [41]. The final algorithms are estimated to be standardized between 2022 and 2024 [42]. There are various initiatives running alongside NIST’s initiative such as PQCrypto [43] and Open Quantum Safe [44]. NITS’s finalists in the KEM category are:

• Classic McEliece, a code-based scheme. [45].

• Crystals-Kyber, a suite of algebraic lattices utilizing a Kyber primitive for KEM [46].

• NTRU, a lattice-based scheme [47].

• Saber, a lattice-based scheme utilizing learning with rounding [48].

The Digital Signature Algorithms are:

• Crystals-Dilithium, a suite of Algebraic lattices using a Dilithium primitive for signature [49].

• Falcon, lattice-based algorithm with shake256 hashing [50].

• Rainbow, multivariate based solution [51].

There are also a number of alternates proposed for both categories. Comments on the submissions’ security and efficacy can be found in [52]. While there are several candidates sharing a similar approach, their proposals vary in key sizes and signature sizes, making it necessary to evaluate each scheme against the architecture in which candidates are intended to be deployed.

2.3 Blockchain and the LACChain Blockchain Network

Blockchain is a technology that allows one to build decentralized ledgers in which different entities can register transactions that are grouped into blocks that are linked using hashes [21]. The immutability of the transactions stored in blockchain networks is guaranteed because it is impossible to tamper with the ledger without being detected. As any entity can, in principle, have a synchronized copy of the ledger and transactions that are validated according to predefined rules, the history cannot be rewritten. The integrity of the transactions is guaranteed by digital signatures because every transaction is signed by the sender, and the immutability of the chain is guaranteed by hash functions [21].

Our work analyzes vulnerabilities of hash functions and cryptographic algorithms. The security of these core elements of blockchain networks will be threatened when quantum computers become robust enough. This applies to most blockchain networks and it is a critical concern that the blockchain community has not yet properly addressed.

Vitalik Buterin, one of the founders of the Ethereum blockchain technology, acknowledged the quantum threat back in 2015 and suggested moving towards Lamport signatures eventually [53]. Prior to our work, the University of Waterloo and Microsoft Research estimated that the number of logical qubits necessary to implement quantum algorithms that can break 256 bit-long digital signatures generated with (EC)DSA, typically used in current blockchain networks, are 1500 [54] and 2330 [55], respectively. It is still unclear how many physical qubits would be needed for that purpose. Another study by researchers in Singapore, Australia, and France claimed in 2017 that quantum computers will be large and robust enough to break Bitcoin keys in 10 minutes by 2017 [56]. In 2018, three groups of scientists from Russia and Canada achieved an implementation of a quantum-secured blockchain based on an exchange of keys using QKD techniques [57], but their scalability is limited by the limitations of the channels for QKD exchange. Additional work has been published since these initial analyses [58–63]. However, we are not aware of any scalable implementation of a quantum-safe blockchain network prior to our work.

We have designed a solution that can be deployed in different blockchain networks. As a key component to show the viability of our proposal, we have implemented it in the LACChain Consensys Quorum (a.k.a. Besu) Network. LACChain is a blockchain infrastructure led by the Innovation Lab of the Inter-American Development Bank (IDB Lab) in Global Alliance with some of the entities leading the development of blockchain technology in the world [64]. The main goal of LACChain is to enable a robust and scalable blockchain network that can host multipurpose use cases with social, economic, and financial impact. Hyperledger Besu is an Ethereum client originally developed by Consensys and now maintained by the Ethereum community, including Consensys [65].

Blockchain can be thought of as a computational system with a distributed state shared among a network of nodes, of which consistency can be verified by any participant. The state is dynamically updated through messages, called transactions, that are broadcasted by the nodes, and each participant can have a verified and verifiable copy of the state and the transaction history. These transactions allow users to deploy executable code to the network, a.k.a. smart contracts, and interact with them.

In order for a new state to be agreed upon by the network, a subset of nodes, called validator or producer nodes, apply a consensus protocol. There are different types of consensus protocols and each network decides which type of consensus protocol they implement. Essentially, every consensus protocol consists of a set of rules that establish how these nodes will accomplish a computational validation of the latest transactions replicated across the network. The validator or producer nodes propose a package, called a block, which contains the transaction, block number, nonce, block hash, previous block hash, and signatures of the block validators or producers. With this, a new block is cryptographically sealed and, once appended to the blockchain, it cannot be undone or tampered with.

In Ethereum Networks, the code deployed in the network is a stream of bytes representing operation codes from the Ethereum Virtual Machine (a.k.a. EVM). This set of operations can be considered Turing complete and are executed as a stack machine with a depth of 1024 items. The EVM is then the runtime environment where any state transformation takes place [66]. Every smart contract has its own memory space and can be changed or updated by a transaction, which is recorded in the transaction history and implies a modification of the current distributed state. Additionally, each operation has an associated cost, which is an abstraction of the computational power required to perform the requested action by an ideal computer. The cost is called gas and serves as a metric for the amount of computation required to process each block.