Quantum Meets Blockchain — Part II
Quantum Technologies should not only be reduced to a threat to blockchains for they can also be used to strengthen blockchain security against any kind of attacker. This post explores in detail some of the architectures that are already being considered for implementation following a previous post about the fundamental concepts of Quantum Computing and Blockchain security.
Blockchains secured by Quantum hardware and protocols
A new type of blockchain architecture where the consensus is based on a Byzantine agreement protocol, has been recently proposed by Russian researchers. The consensus relies on pairwise authentication of each communication channel provided via Quantum Key Distribution. Two communication layers are used, one optical that establishes secret keys through QKD and one classical, authenticated with a Toeplitz hashing scheme, that is used to exchange public informations.
After its creation, a new transaction is sent via authenticated channels to all the other nodes. Each node compares this new data with their own local database for verification and emits an opinion on the validity of the transaction. All the unconfirmed transactions are then aggregated into a new block.
At a pre-determined time frequency — e.g. 10 minutes — the Byzantine agreement protocol is applied to each unconfirmed transaction by the whole network, defining a consensus on the correctness of each transaction. Each node forms a block out of all admissible transactions sorted by time stamps and adds it to its local database. Not only this collective procedure avoid double-spending but it also prevent forks — situations in which several versions of the same block are simultaneously created by different users.
The authors have tested this new quantum-secured architecture on an urban-fiber QKD network constituted of four nodes, including a malicious one. The QKD key consumption required for performing 10 transactions per minute, which is less than 7 bit/s from their experiment, is easily ensured by current QKD devices.
They were even able to simulate and successfully prevent an intrusion attempt by considering a block construction from a pool of four unauthorized transactions, including one false transaction produced by the malicious node. This node is recognized and eliminated after applying the broadcast protocol.
In real life, security is never perfect and this proposal is not exempt of limitations. An ill-intended participant provided with a Quantum Computer could attempt to forge a false database offline by modifying a past transaction record. By running Grover’s algorithm, this attacker could find a variant of the target transaction within the same block, resulting in the same hash. Such rigged transaction will then appear as legitimate to the other users and the dishonest participant will be able to substitute his forged database to all other databases in the network provided that he can hack simultaneously at least one-third of the nodes.
In this platform, the number of QKD-secured communications required during the block construction procedure is of the order of n square for n participants, making it highly impracticable beyond private blockchains with a limited number of nodes.
However, in addition to providing a first interesting example of hybridization between QKD and blockchain, this platform can still be considered to secure small sensitive parts of a wider network, for example in the context of a global Quantum Internet.
Apart from this QKD-secure blockchain, other Quantum algorithms implemented with future Quantum Computers could be considered to enhance blockchain security. The first Quantum Digital Signatures(QDS) scheme designed in 2001 is very similar to a classical signature algorithm called Lamport-OTS (One Time Signature) where the classical one-way function has been replaced by a quantum one-way function.
Post-Quantum blockchains
Classical Post-Quantum signature schemes are based on diverse mathematical constructions that are supposedly resistant to Quantum Computers, i.e. it is not easier to crack them with a Quantum Computer than it is with a Classical Computers.
Their security is still under scrutiny: their security proofs are either based on unproven — but conjectured to be — mathematical hard problems or on alternate versions of proven hard problems — called security reductions — for which the security is unclear. But they have the huge benefit of not necessitating Quantum hardware to provide safety, contrary to solutions based on Quantum Key Distribution.
Several candidates for signature, key exchange and encryption are under evaluations in the recent NIST Post-Quantum cryptography certification process, which began in late 2017 and is expected to run at least until 2021. No less than 79 proposals covering various mathematical problems were submitted during the first round. Their security and requirements will be exhaustively examined, and the NIST expects to select several of them for certification. As of October 2018, several of these algorithms have been withdrawn due to unfixable security flaws. Many others have suffered attacks with various degrees of severity and are being adjusted (source: Post-Quantum Crypto Lounge).
For each transaction occurring in the blockchain, a public key and a signature value are stored to allow for a validity check. Small parameter sizes and fast execution times are of the utmost importance when choosing suitable security solutions. Unfortunately, in many Post-Quantum algorithms, acceptable parameter sizes and efficiencies come at the expense of assumptions on the algorithm’s security that make it vulnerable.
There are more than 10 startups worldwide working on blockchain designs based on Post-Quantum signature schemes. The most frequently mentioned candidates are Hash-based Merkle tree schemes such as the eXtended Merkle Signature Scheme (XMSS) which is designed from One-Time Signatures, e.g. Lamport-OTS or Winternitz-OTS. Another widely considered category, lattice-based cryptography, is constructed around mathematical lattice problems, e.g. finding the shortest non-zero vector between two points in a given lattice. The BLISS or CRYSTAL-DILITHIUM signature schemes are considered as promising candidates to construct new post-quantum blockchains.
Another, and complementary, angle towards quantum-safe blockchains is the choice of an adequate consensus that should at least be able to satisfy the following requirements. The new challenge should be difficult to solve but easy to verify and it should not be solved faster with a Quantum Computer than with a classical computer. Concerning Proof-of-Work, the difficulty of the underlying mathematical problem should also be tunable in accordance with the network overall computing power.
Some interesting short-term candidates based on search problems are called memory-intensive PoW. The Momentum consensus (Haschcash) is based on the difficulty of finding two pre-images resulting in the same hash, a collision problem which admits a quantum speed-up with Grover’s algorithm but reduced vs the standard PoW consensus. In a completely different way, Cuckoo Cycle (CodeChain) relies on the difficulty of finding constant sized subgraphs in a random graph and Equihash (Zcash) is based on the generalized birthday problem.
Another interesting possibility is to replace the Proof-of-Work consensus by a Proof-of-Stake consensus, the later being safe against Grover’s algorithm by design. This replacement could also result in a very cost-efficient alternative provided the reduction of the energy necessary to append new blocks to the blockchain. An important technical challenge in the establishment of a PoS protocol is to provide entropy for the randomized election process to avoid influence by a malicious party. In current PoS, this is ensured by multi-party coin flipping algorithms which are based on Public-Key algorithms and thus also vulnerable against Quantum attacks. Unconditionally secure multi-party coin flipping and computation algorithms must be considered and implemented in PoS to ensure their security in the future Quantum world.
It is clear now that in the coming age of Quantum Computing, all cryptography-related industries will be immensely impacted. Quantum Technologies such as QKD as well as Post-Quantum cryptography running on classical computers could provide adequate solutions for cybersecurity in this era.
What is less clear though is how the data that will have been generated and encrypted until this time will be kept secured …
