Byzantine fault tolerant protocols are algorithms that are robust to arbitrary types of failures in distributed algorithms. The Byzantine agreement protocol is an essential part of this task. The constant-time quantum version of the Byzantine protocol, [1] is described below.
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, [2] 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 [3] 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.
Failures in an algorithm or protocol can be categorized into three main types:
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, if the processors give conflicting data, which processors or sets of processors should be believed? The solution can be formulated as a Byzantine fault tolerant protocol.
We will sketch here the asynchronous algorithm [1] The algorithm works in two phases:
There are two types of coin flipping protocols
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 selects a random number for every other player and distributes this using a verifiable secret sharing scheme.
At the end of this phase players agree on which secrets were properly shared, the secrets are then opened and each player is assigned the value
This requires private information channels so we replace the random secrets by the superposition . In which the state is encoded using a quantum verifiable secret sharing protocol (QVSS). [5] We cannot distribute the state since the bad players can collapse the state. To prevent bad players from doing so we encode the state using the Quantum verifiable secret sharing (QVSS) and send each player their share of the secret. Here again the verification requires Byzantine Agreement, but replacing the agreement by the grade-cast protocol is enough. [6] [7]
A grade-cast protocol has the following properties using the definitions in [6] Informally, a graded broadcast protocol is a protocol with a designated player called “dealer” (the one who broadcasts) such that:
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 outputs a pair such that the following properties hold:
For the verification stage of the QVSS protocol guarantees that for a good dealer the correct state will be encoded, and that for any, possibly faulty dealer, some particular state will be recovered during the recovery stage. We note that for the purpose of our Byzantine quantum coin flip protocol the recovery stage is much simpler. Each player measures his share of the QVSS and sends the classical value to all other players. The verification stage guarantees, with high probability, that in the presence of up to faulty players all the good players will recover the same classical value (which is the same value that would result from a direct measurement of the encoded state).
In 2007, a quantum protocol for Byzantine Agreement was demonstrated experimentally [8] using a four-photon polarization-entangled state. This shows that the quantum implementation of classical Byzantine Agreement protocols is indeed feasible.
Byzantine fault tolerant protocols are algorithms that are robust to arbitrary types of failures in distributed algorithms. The Byzantine agreement protocol is an essential part of this task. The constant-time quantum version of the Byzantine protocol, [1] is described below.
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, [2] 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 [3] 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.
Failures in an algorithm or protocol can be categorized into three main types:
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, if the processors give conflicting data, which processors or sets of processors should be believed? The solution can be formulated as a Byzantine fault tolerant protocol.
We will sketch here the asynchronous algorithm [1] The algorithm works in two phases:
There are two types of coin flipping protocols
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 selects a random number for every other player and distributes this using a verifiable secret sharing scheme.
At the end of this phase players agree on which secrets were properly shared, the secrets are then opened and each player is assigned the value
This requires private information channels so we replace the random secrets by the superposition . In which the state is encoded using a quantum verifiable secret sharing protocol (QVSS). [5] We cannot distribute the state since the bad players can collapse the state. To prevent bad players from doing so we encode the state using the Quantum verifiable secret sharing (QVSS) and send each player their share of the secret. Here again the verification requires Byzantine Agreement, but replacing the agreement by the grade-cast protocol is enough. [6] [7]
A grade-cast protocol has the following properties using the definitions in [6] Informally, a graded broadcast protocol is a protocol with a designated player called “dealer” (the one who broadcasts) such that:
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 outputs a pair such that the following properties hold:
For the verification stage of the QVSS protocol guarantees that for a good dealer the correct state will be encoded, and that for any, possibly faulty dealer, some particular state will be recovered during the recovery stage. We note that for the purpose of our Byzantine quantum coin flip protocol the recovery stage is much simpler. Each player measures his share of the QVSS and sends the classical value to all other players. The verification stage guarantees, with high probability, that in the presence of up to faulty players all the good players will recover the same classical value (which is the same value that would result from a direct measurement of the encoded state).
In 2007, a quantum protocol for Byzantine Agreement was demonstrated experimentally [8] using a four-photon polarization-entangled state. This shows that the quantum implementation of classical Byzantine Agreement protocols is indeed feasible.