# A Quantum Detectable Byzantine Agreement Protocol Using Only EPR Pairs
## 2 Preliminaries
### Detectable Byzantine Agreement  
In the landmark paper [1], the authors used the term the \"Byzantine Generals Problem\" to formulate the problem we study in this paper. A little later, two other influential works [34,35] changed the terminology a bit and refereed to the same problem as the \"Byzantine Agreement Problem,\" a term that has been consistently used in the literature ever since. The problem itself involves \(n\) generals of the Byzantine empire, one of them being the commanding general and the rest \(n-1\) being lieutenant generals. The commanding general must communicate his order to the lieutenant generals who are in different geographical locations. The overall situation is further complicated by the existence of traitors among the generals (possibly including even the commanding general). The notion of Byzantine Agreement was defined in [1] as follows.  
**Definition 1** (Byzantine Agreement).: _A protocol achieves Byzantine Agreement (BA) if it satisfies the following conditions._  
\begin{tabular}{l l} (\(\mathbf{BA}_{1}\)) & All loyal lieutenant generals follow the same order. \\ (\(\mathbf{BA}_{2}\)) & When the commanding general is loyal, all loyal lieutenant generals follow the commanding general's order. \\ \end{tabular}  
The authors in [1] not only presented an algorithm that, under certain assumptions, achieves BA, but also obtained the significant result that, under the assumption of pairwise authenticated channels among the generals, BA can be attained if and only if \(t<\frac{n}{3}\), where \(n\) is the number of generals and \(t\) is the number of traitors. Later it was established that this bound can't be improved even if additional resources are assumed (see [36]). An important special illustration of this fact, is the case of \(n=3\) generals, exactly one of which is a traitor because it is impossible to achieve BA in such a case, by any classical protocol.  
In the seminal paper [21] a variant of BA called Detectable Byzantine Agreement (DBA from now on) was introduced. By slightly relaxing the requirements of the BA protocol, and, in particular, allowing the loyal generals to abort the protocol, an action that is not permitted in the original protocol, the authors were able to give the first quantum protocol for DBA. Their protocol relied on Aharonov states and improved the previous bound by achieving agreement in the special case of one traitor among three generals. Although [21] considered only the case of 3 generals, later works introduced DBA protocols for \(n\) parties. In this work we use the Definition 2 for DBA.  
**Definition 2** (Detectable Byzantine Agreement).: _A protocol achieves Detectable Byzantine Agreement (DBA) if it satisfies the following conditions._  
\begin{tabular}{l l} (\(\mathbf{DBA}_{1}\)) & If all generals are loyal, the protocol achieves Byzantine Agreement. \\ (\(\mathbf{DBA}_{2}\)) & Consistency: All loyal generals either follow the same order or abort the protocol. \\ (\(\mathbf{DBA}_{3}\)) & Validity: If the commanding general is loyal, then either all loyal lieutenant generals follow the commanding general's order or abort the protocol. \\ \end{tabular}  
A comparison of Definition 1 with Definition 2 shows that the critical difference between BA and DBA lies in the extra capability of the generals to abort the protocol in the DBA case. As is common practice, we shall assume that the commanding general's orders are either 0 or 1, and we shall use the symbol \(\bot\) to signify that the decision to abort.