Byzantine Generals Turn to Quantum
At four, they now unmask at once two traitors among them
Type “Byzantine generals” into the Google search box, and you’ll get about 27,000,000 results as I write this article. You can imagine that most of these entries are not about historical Byzantine military personnel. Indeed, the “Byzantine generals problem”, as it was coined in 1982 in the seminal paper of Lamport et al, has wide applications in such domains as fault-tolerant computing, distributed computer systems, blockchains, finance, and cryptocurrency.
Leslie Lamport defined the problem as follows:
We imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action. However, some of the generals may be traitors, trying to prevent the loyal generals from reaching agreement.
In this Byzantine agreement, broadcast is achieved when two conditions are satisfied at the end of the decision process:
1. All loyal generals agree on a common plan of action.
2. If the commanding general is loyal, then all loyal
generals agree on the commanding general’s plan.
An important conclusion was that no classical solution with fewer than 3 ∙ m + 1 generals can cope with m traitors.
For three generals, there is no classical solution and for four generals, the classical solution allows the detection of only one traitor.
Recently, a quantum protocol based on qutrit published by Fitzi, Gisin, and Maurer solved this problem in the case of three generals coping with one traitor. This is possible thanks to the weird nature of quantum physics. In quantum computing, a unit of information, the qubit or the more exotic qutrit, can never be cloned, unlike the counterpart in classical computing, the bit or the trit, which can be copied with no limit. Instead, teleportation allows long-range transmission of quantum information, culminating in the demonstration of secure key distribution with the Quantum Experiments at Space Scale.
There is a stark analogy between a quantum solution to a Byzantine agreement and quantum key distribution (QKD), a secure cryptographic technique already in the commercial state. This is explicit in the article by Fitzi, Gisin, and Maurer:
First, the quantum states are used ”only” to distribute classical private random variables with specific correlation to the 3 players (a trit per player, each of a different value, all combination with equal probabilities). This is similar to quantum cryptography where quantum mechanics ”only” provides key distribution.
Quantum computing systems based on physical qutrits are rare today. However, it is possible to emulate qutrits using physical qubits. A four-qubit singlet state was proposed by Adán Cabello and was subject to experimental verification using four-photon entanglement. Zoltán Guba et al demonstrated this protocol on IBM Q and IonQ devices.
Similar solutions can be imagined with four parties but with different entangled states. The advantage of this extension to four generals is that the agreement is now made by majority consensus between the three lieutenants when the commanding general is the only traitor.
A five-qubit solution to the four-general agreement coping with up to two traitors is presented here, with testing on simulators and IBM Quantum online systems.
Protocol of the Quantum Solution
Let’s detail the four phases :
1. Distribute Entangled Qubits
The entanglement of qubits can be left to either party or an outside agent. This avoids the problem of an unfair umpire or an infamous enemy within. This works because the entanglement is verified by all parties in the next phase, which is the counterpart of QKD verification.
A number M of qubit-quintuplets is produced. The qubits are in the following quantum state:
For each quintuplet, the first two qubits (counting from the left in the equation) are distributed to commanding general Alice, and the three remaining qubits go to lieutenant generals Bob, Carol, and Dave. The generals measure the qubits in the Pauli-Z basis. They don’t share any results and get each an ordered list of bitstrings.
In an ideal noiseless quantum system, the four lists are correlated such that for a given index:
- When Alice holds ‘00’, all lieutenants hold ‘1’.
- When Alice holds ‘11’, all lieutenants hold ‘0’.
- When Alice holds ‘01’, one lieutenant at random holds ‘1’, and both others hold ‘0’.
- When Alice holds ‘10’, one lieutenant at random holds ‘0’, and both others hold ‘1’.
2. Check Entanglement
The parties verify that the entanglement was correct. For this purpose, they communicate through classical bidirectional channels.
Then, each party chooses an arbitrary integer from an agreed range. They communicate these integers to each other. Locally, they draw M-N bitstrings from their list, using the sum of the four integers as the seed. They place these test lists in a common register.
The four parties check that the test lists are correlated consistently with the entanglement.
If so, they estimate the expected error rates in the future game for the quantum system if it is noisy. These rates are specific to each possible pair of lieutenants. For a given lieutenant, they are higher if she/he is a traitor.
Finally, the lists composed of the bitstrings remaining after testing are transformed into integer lists of length N:
- In Alice’s list, ‘00’ becomes 0 (‘retreat’ ), and ‘11’ becomes 1 ( ‘attack’). Bitstrings ‘01’ and ‘10’ become 2 (‘ trap’).
- In the lists of the lieutenants, ‘1’ becomes 1 and ‘0’ becomes 0.
As in the three-general protocol proposed by Cabello, each of these resulting four lists is random, correlated to the other three lists, and each party knows only her/his list. Unique to quantum, the entanglement at the base of the protocol assures every general that it is indeed the case.
3. Send Orders
From here, bye-bye quantum world.
Alice separately and secretly sends the lieutenants an order, either ‘retreat’ (0) or ‘attack’ (1), and a list of corresponding indexes. The orders are the same, except if Alice is a traitor.
Each lieutenant determines for each index whether the entry mistakenly matches the order. If they see many matches, they will consider Alice’s order inconsistent and take no action: this breaks the protocol with no agreement reached. Note that the protocol is also abandoned when any lieutenant receives a list whose length is not reasonably bounded around N/3.
4. Realize Agreement
The lieutenants inform each other of the orders received. They check if they are all identical. If so, they follow Alice’s order, and broadcast is achieved.
Otherwise, there is at least one traitor among the generals. When two lieutenants report different orders, each must prove what she/he says. For this, they both embark on a turn-based game. Two games are played because all game scenarios include two pairs that signal different orders to each other.
For each game, the players draw whoever starts. They take turns sending an index whose corresponding entry in the opponent’s list must match the inverse of the order they said they received. Each player counts the errors. No index is used twice. The game ends when a player issues a stop flag indicating that her/his list of matching indexes is exhausted. And it still ends after a pre-agreed number of rounds (this justifies taking turns instead of swapping the lists in one move).
The details of how this traitor hunt works can be found in my explanatory Jupyter notebook, along with the Python code gathering the solutions for three and four generals.
Each of the scenarios achieves broadcast.
What about the more realistic case of a noisy quantum system?
At the end of a game, each lieutenant compares the number of errors x made by the opponent with the expected values. Knowing the number of rounds r, they use hypergeometric distributions to calculate the probabilities of observing x whether the adversary is a traitor or not. Or instead, they can use the distances between x/r and the two expected values (the squared Euclidean and the Jensen-Shannon distances are good candidates for this purpose).
Broadcast is therefore also achieved in a noisy system. However, longer lists are needed.
Testing the Protocol in Qiskit:
Setting up the Quantum circuit
It is a cinch using the open-source Qiskit package! In the following snippet, the state vector corresponding to the entanglement is first defined. A circuit of five qubits is initialized according to this vector. The measurement in the Pauli-Z basis follows with results in five classical registers.
Testing on simulators:
Device backend noise model simulations are a great feature of Qiskit to test if this solution can work on any of the devices accessible online in IBM Quantum. The protocol passed the test on FakeSydney in all possible scenarios.
Scenarios with one traitor on simulator:
Scenarios with two traitors on simulator:
Testing on hardware
(edited on July 7th, 2022)
The protocol was tested first on 5-qubit online systems with incorrect traitor detection in some scenarios: the depth of the quantum circuits was increased due to the lack of ancillary qubits. Access to the seven-qubit ibm-oslo system, added in mid-2022 to the IBM Quantum compute resources, solved this issue.
Scenarios with one traitor on hardware:
Scenarios with two traitors on hardware:
Prospect
The constant progress in terms of hardware and software in quantum computing allows hope for the use of the protocol in concrete situations. One can imagine more efficient dedicated systems, comprising an adequate number of qubits, including ancillaries, and a layout with judicious connections.
However, the path to real-world applications requires solving some issues and testing options. Discussing the why and how is out of the scope of this article. Mitigation methods to correct for results in noisy devices should be considered. For instance, in the protocol tested here, flipping each bitstring with an even index in the lists was effective in balancing the error rates. Another important point is to maintain secure transmission throughout the whole process.
Conclusion
The demonstration of this protocol in Qiskit goes beyond a simple thought experiment. Tests were carried out using simulation on a classical computer and online quantum systems. However, the implementation of a real-life application would represent a major technical challenge.
This quantum solution to the four-general Byzantine agreement tells us that in addition to warding off the eavesdropper Eve, quantum-based methods can help all of us, Alice, Bob, Carol, Dave, and the others, validate information while remaining safe from possible enemies within. This quantum approach can be worthy in a world where information is increasingly shared in a decentralized way, such as in transactions secured with blockchains.
I acknowledge the use of IBM Quantum services for the testing on hardware. The views expressed are those of the author, and do not reflect the official policy or position of IBM or the IBM Quantum team.
In a following article, a Bayesian solution is presented which takes into account the degree of confidence of the lieutenants between themselves and towards the commanding general.
