Byzantine fault tolerant protocols are algorithms that are robust to arbitrary types of failures in distributed algorithms. With the advent and popularity of the Internet, there is a need to develop algorithms that do not require any centralized control that have some guarantee of always working correctly. The Byzantine agreement protocol is an essential part of this task. In this article the quantum version of the Byzantine protocol, which works in constant time is described.
Contents
Introduction
The Byzantine Agreement protocol is a protocol in distributed computing. It takes its name from a problem formulated by Lamport, Shostak and Pease in 1982, which itself is a reference to a historical problem. The Byzantine army was divided into divisions with each division being led by a General with the following properties:
(See for the proof of the impossibility result). The problem usually is equivalently restated in the form of a commanding General and loyal Lieutenants with the General being either loyal or a traitor and the same for the Lieutenants with the following properties.
Byzantine Failure and Resilience
Failures in an algorithm or protocol can be categorized into three main types:
- A failure to take another execution step in the algorithm: This is usually referred to as a "fail stop" fault.
- A random failure to execute correctly: This is called a "random fault" or "random Byzantine" fault.
- An arbitrary failure where the algorithm fails to execute the steps correctly (usually in a clever way by some adversary to make the whole algorithm fail) which also encompasses the previous two types of faults; this is called a "Byzantine fault".
A Byzantine resilient or Byzantine fault tolerant protocol or algorithm is an algorithm that is robust to all the kinds of failures mentioned above. For example, given a space shuttle with multiple redundant processors and some of the processors give incorrect data, which processors or sets of processors should be believed? The solution can be formulated as a Byzantine fault tolerant protocol.
Sketch of the Algorithm
We will sketch here the asynchronous algorithm The algorithm works in two phases:
There are two types of coin flipping protocols
Verifiable secret sharing.
Protocol QuantumCoinFlip for player P i {\displaystyle P_{i}}
- Round 1 generate the state
| C o i n i ⟩ = 1 2 | 0 , 0 , … , 0 ⟩ + 1 2 | 1 , 1 , … , 1 ⟩ on n qubits and send the kth qubit to the kth player keeping one part - Generate the state
| L e a d e r i ⟩ = 1 n 3 / 2 ∑ a = 1 n 3 | a , a , … , a ⟩ on n qubits, an equal superposition of the numbers between 1 andn 3 - Receive the quantum messages from all players and wait for the next communication round, thus forcing the adversary to choose which messages were passed.
- Round 2: Measure (in the standard base) all
L e a d e r j - Set the output of the QuantumCoinFlip protocol:
v i
The Byzantine protocol.
To generate a random coin assign an integer in the range [0,n-1] to each player and each player is not allowed to choose its own random ID as each player
At the end of this phase players agree on which secrets were properly shared, the secrets are then opened and each player
Grade-cast protocol
A grade-cast protocol has the following properties using the definitions in Informally, a graded broadcast protocol is a protocol with a designated player called “dealer” (the one who broadcasts) such that:
- If the dealer is good, all the players get the same message.
- Even if the dealer is bad, if some good player accepts the message, all the good players get the same message (but they may or may not accept it).
A protocol P is said to be achieve graded broadcast if, at the beginning of the protocol, a designated player D (called the dealer) holds a value v, and at the end of the protocol, every player
- If D is honest, then
v a l u e i c o n f i d e n c e i P i - For any two honest players
P i P j , | c o n f i d e n c e i − c o n f i d e n c e j | ≤ 1 . - (Consistency) For any two honest players
P i P j c o n f i d e n c e i > 0 andc o n f i d e n c e j > 0 ,thenv a l u e i = v a l u e j
For
Remarks
In 2007, a quantum protocol for Byzantine Agreement was demonstrated experimentally using a four-photon polarization-entangled state. This shows that the quantum implementation of classical Byzantine Agreement protocols is indeed feasible.