Reaching a leaderless consensus in distributed ledgers with quantum computing

By Alvin Lee

SMU Office of Research & Tech Transfer – The Blockchain Trilemma, as described by Ethereum founder Vitalik Buterin, is the three-issue conundrum blockchain developers face, having to sacrifice one aspect in the interest of the other two but never able to achieve all three. The three issues are:

1. Number of validating nodes (also known as decentralisation);
2. Speed of consensus; and
3. Security of the network

In well-known blockchains such as Bitcoin, Proof of Work (PoW) mechanisms underpin a distributed ledger (DLT) that involves an open community of ‘miners’ validating transactions for payment. The higher the number of miners, the less likely one node or miner can change the history of the blockchain for his own benefit; therefore security is enhanced but speed of consensus is compromised.

Conversely, the number of validating nodes can be reduced for speed but it also exposes the DLT to attacks such as the possibility of a 51 percent attack.

“The simplest way to achieve consensus is that all nodes take data from one source (a leader),” explains Paul Griffin, Associate Professor of Information Systems (Practice) at Singapore Management University (SMU). “If everyone trusts the leader then the same leader can be used. If the leader cannot be trusted then a new leader can be elected periodically (e.g. every time a block is created in a blockchain). Leaders are often a particular type of node (called ‘miners’ in Bitcoin and Ethereum) that perform validations whereas typically, all nodes can transact.

“Another approach to achieve consensus is for a majority of nodes to agree on a value and this is called leaderless.”

Achieving leaderless consensus with quantum computing

Because work on leader election had already been done (Mazzarella 2013), Professor Griffin will focus on a leaderless consensus protocol in his latest research project. In partnership with fintech company OneConnect, Professor Griffin started the one-year project in February 2020 focusing on how quantum computing can help nodes come to a leaderless consensus securely and quickly at large scales.

Whereas traditional computing stores information in binary bits that are either ‘1’ or ‘0’, quantum computing stores information in qubits (short for quantum bits) which can be both ‘0’ and ‘1’ at the same time. It is done through the quantum principle of superposition, which Professor Griffin explains thus:

“A superposition of quantum states is a quantum particle existing in more than one state at any time. For example, a coin being flipped exists in both heads and tails as it rotates in the air.”

“The quantum state of a qubit has both real and imaginary components that can take any value between 0 and 1,” Professor Griffin tells the Office of Research and Tech Transfer. “Current blockchains have block size limitations that typically contain a few hundred transactions of approximately a few MB (where each megabyte or MB = 10^7 bit values). A quantum computer scales by 2^n (where n = number of qubits), so a 100-qubit quantum computer can process 2^100 values, which is roughly equivalent to 10^30 values (approximately 1MB followed by twenty-three zeros).”

This ability to hold exponentially more information is crucial to achieving consensus in DLTs in a Big Data era where agreement of all the data may be required.

Leaderless consensus requires agreement by all nodes on external values called ‘oracle values’ that get incorporated into the DLT. For example, information from online sources pertaining to commodity prices, or data pertaining to the physical world such as RFID signals of a shipment in supply chains.

“Leaderless consensus provides for all nodes to agree on a value which would be useful for determining oracle values and also detecting nodes which may be compromised,” Professor Griffin explains, “As there is a quantum advantage of the possibility to hold much larger data sizes than in classical systems, the data used for consensus could also be very large.”

The experiment and the results

For the research project, Professor Griffin ran experiments on quantum simulators and real quantum computers to achieve classical leaderless consensus agreement.

“We did experiments on IBM quantum simulators and on real quantum backends and compared to a classical consensus,” he elaborates. “These were all run on one physical machine because quantum networks are not yet connected to quantum computers. Initially, 3 nodes were tested for how many rounds were needed to reach agreement.

“Then we expanded from 3 to 10 nodes to compare the scaling characteristics of quantum and classical. The quantum consensus behaved similarly to classical in general. However, the quantum consensus was sometimes faster and sometimes slower than classical with a non-normal distribution.”

He adds: “If the distribution was normal, then it could just be explained by randomness but as it was non-normal then examining the behaviour closer may lead to understanding of how a speed-up of agreement could be achieved.”

The experiments yielded results:

1. Quantum and classical take a similar number of rounds to agree. “This means that there is no degradation to consensus agreement by using quantum instead of classical. Good news.”

2. Quantum consensus has more variation than classical and can take longer or shorter. “Unlike classical consensus, quantum consensus has the potential to be able to reach agreement quicker than classical consensus.”

3. Real quantum computers need careful configuration and noise mitigation. “Current technologies have noisy qubits that are not all connected together and quickly lose their information. We need to carefully map the quantum circuit to the physical qubits and use noise reduction processing after running the circuit. This reduces the range of the circuits we can use at present.”

Back to Research@SMU May 2021 Issue