Quantum Byzantine Agreement
Encyclopedia
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 we describe the quantum version of the Byzantine protocol, which works in constant time.
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.
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 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.
The algorithm works in two phases:
The protocol relies on two other algorithms to work correctly
There are two types of coin flipping protocols
Protocol QuantumCoinFlip for player
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). 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.
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).
Byzantine fault tolerance
Byzantine fault tolerance is a sub-field of fault tolerance research inspired by the Byzantine Generals' Problem, which is a generalized version of the Two Generals' Problem....
protocols are algorithms that are robust to arbitrary types of failures in distributed algorithms
Distributed algorithms
A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in many varied application areas of distributed computing, such as telecommunications, scientific computing, distributed information processing,...
. With the advent and popularity of the Internet
Internet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
, 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 we describe the quantum version of the Byzantine protocol, which works in constant time.
Introduction
The Byzantine AgreementByzantine fault tolerance
Byzantine fault tolerance is a sub-field of fault tolerance research inspired by the Byzantine Generals' Problem, which is a generalized version of the Two Generals' Problem....
protocol
Communications protocol
A communications protocol is a system of digital message formats and rules for exchanging those messages in or between computing systems and in telecommunications...
is a protocol in distributed computing
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
.
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:
- Each General is either loyal or a traitor to the Byzantine stateByzantineByzantine usually refers to the Roman Empire during the Middle Ages.Byzantine may also refer to:* A citizen of the Byzantine Empire, or native Greek during the Middle Ages...
. - All Generals communicate by sending and receiving messages.
- There are only two commands: attack and retreat.
- All loyal Generals should agree on the same plan of action: attack or retreat.
- A small linear fraction of bad Generals should not cause the protocol to fail (less than a
fraction).
(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.
- All loyal Lieutenants carry out the same order.
- If the commanding General is loyal, all loyal Lieutenants obey the order that he sends.
- A strictly less than
fraction including the commanding General are traitors.
Byzantine Failure and Resilience
Failures in an algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
or protocol
Communications protocol
A communications protocol is a system of digital message formats and rules for exchanging those messages in or between computing systems and in telecommunications...
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 failure where the algorithm randomly fails 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
Byzantine fault tolerance
Byzantine fault tolerance is a sub-field of fault tolerance research inspired by the Byzantine Generals' Problem, which is a generalized version of the Two Generals' Problem....
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
Byzantine fault tolerance
Byzantine fault tolerance is a sub-field of fault tolerance research inspired by the Byzantine Generals' Problem, which is a generalized version of the Two Generals' Problem....
protocol.
Sketch of the Algorithm
We will sketch here the asynchronous algorithmThe algorithm works in two phases:
- Phase 1 (Communication phase):
- All messages are sent and received in this round.
- Phase 2 (Computation phase):
- This Phase begins only after the first phase has ended. All the messages received are processed.
The protocol relies on two other algorithms to work correctly
Coin flipping protocol
- A quantum coin flipping protocol,:
- A coin flipping protocol is a procedure that allows two parties A and B that do not trust each other to toss a coin to win a particular object.
There are two types of coin flipping protocols
-
- weak coin flipping protocols : The two players A and B initially start with no inputs and they are to compute some value
and be able to accuse anyone of cheating. The protocol is successful if A and B agree on the outcome. The outcome 0 is defined as A winning and 1 as B winning. The protocol has the following properties:
- If both players are honest (they follow the protocol), then they agree on the outcome of the protocol
with 
for 
. - If one of the players is honest (i.e., the other player may deviate arbitrarily from the protocol in his or her local computation), then the other party wins with probability at most
. In other words, if B is dishonest, then 
, and if A is dishonest, then 
.
- If both players are honest (they follow the protocol), then they agree on the outcome of the protocol
- A strong coin flipping protocol: In a strong coin flipping protocol, the goal is instead to produce a random bit which is biased away from any particular value 0 or 1. Clearly, any strong coin flipping protocol with bias
leads to weak coin flipping with the same bias.
- weak coin flipping protocols : The two players A and B initially start with no inputs and they are to compute some value
Verifiable secret sharing.
- A verifiable secret sharingVerifiable secret sharingIn cryptography, a secret sharing scheme is verifiable if auxiliary information is included that allows players to verify their shares as consistent. More formally, verifiable secret sharing ensures that even if the dealer is malicious there is a well-defined secret that the players can later...
(VSS) protocol: A (n,k) secret sharingSecret sharingSecret sharing refers to method for distributing a secret amongst a group of participants, each of whom is allocated a share of the secret. The secret can be reconstructed only when a sufficient number of shares are combined together; individual shares are of no use on their own.More formally, in a...
protocol allows a set of n players to share a secret, s such that only a quorum of k or more players can discover the secret. The player sharing (distributing the secret pieces) the secret is usually referred to as the dealer. A verifiable secret sharing protocol differs from a basic secret sharing protocol in that players can verify that their shares are consistent even in the presence of a malicious dealer.
Protocol QuantumCoinFlip for player 
- Round 1 generate the state
on n qubits and send the kth qubitQubitIn quantum computing, a qubit or quantum bit is a unit of quantum information—the quantum analogue of the classical bit—with additional dimensions associated to the quantum properties of a physical atom....
to the kth player keeping one part - Generate the state
on n qubits, an equal superposition of the numbers between 1 and 
.Distribute the n qubits between all the players - 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
qubits received in round I. Select the player with the highest leader value (ties broken arbitrarily) as the "leader" of the round. Measure the leader’s coin in the standard base. - Set the output of the QuantumCoinFlip protocol:
= measurement outcome of the leader’s coin.
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 chose its ownrandom 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). 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.Grade-cast protocol
A grade-cast protocol has the following properties using the definitions inInformally, 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
outputs a pair such that the following properties hold:
- If D is honest, then
= v and 
= 2 for every honest player 
. - For any two honest players
and 
. - (Consistency) For any two honest players
and 
, if 
and 
,then 
.
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).