# A Quantum Detectable Byzantine Agreement Protocol Using Only EPR Pairs
## 4 The \(n\) Player EPRQDBA Protocol
### The \(n\) Player Agreement Phase
: We assume that [PERSON] is loyal and, without loss of generality, we suppose that [PERSON] conveys the command 0 to all her lieutenant generals, along with the appropriate command vectors as proof. These command vectors satisfy the properties asserted in Lemma 4. Let us consider an arbitrary loyal lieutenant general \(\mathrm{LT}_{i}\), \(0\leq i\leq n-2\). \(\mathrm{LT}_{i}\) will use the Algorithm 4 to verify the validity of the received command vector \(\mathbf{0}_{i}\). Hence, \(\mathrm{LT}_{i}\) will have accepted order 0 at the end of (\(\mathbf{Round}_{2}\)). According to the rules of the \(n\) player EPRQDBA Protocol 2, the only way for \(\mathrm{LT}_{i}\) to change his initial decision and abort is if another \(\mathrm{LT}_{j}\), \(0\leq i\
eq j\leq n-2\), sends to \(\mathrm{LT}_{i}\) his decision 1 accompanied by a valid command vector \(\mathds{1}_{j}\). Such an \(\mathrm{LT}_{j}\) would, of course, be a traitor that has in reality received the command vector \(\mathbf{0}_{j}\) during (\(\mathbf{Round}_{1}\)). Can such an \(\mathrm{LT}_{j}\) construct a convincing \(\mathds{1}_{j}\)? \(\mathrm{LT}_{i}\), having received the command vector \(\mathbf{0}_{i}\), knows the positions of all the \((n-1)\)-tuples in \(\mathbf{a}\) that contain 0 in the \(i\)th position and 1 in the \(j\)th position. \[\mathbb{T}_{j\to 1}^{i\to 0}(\mathbf{0}_{i})=\{p_{1},p_{2},\ldots,p_{t}\}\,\ \text{where}\ t\approx\frac{m}{4}. \tag{15}\]Knowing \(0_{j}\), \(\mathrm{LT}_{j}\) knows the \((n-1)\)-tuples of \(\mathsf{a}\) that contain \(0\) in their \(j\)th place, and the uncertain \((n-1)\)-tuples. Both are \(\approx\frac{m}{2}\) in number. \(\mathrm{LT}_{j}\) also knows that the \(\approx\frac{m}{2}\) uncertain \((n-1)\)-tuples contain \(1\) in their \(j\)th position and \(0\) or \(1\), with equal probability \(0.5\), in their \(i^{th}\) position. However, \(\mathrm{LT}_{j}\) cannot know with certainty if a specific uncertain \((n-1)\)-tuple contains \(0\) or \(1\) in the \(i\)th position. Therefore, when constructing \(\mathds{1}_{j}\), \(\mathrm{LT}_{j}\) can make two detectable mistakes. (\(\mathbf{M}_{1}\)) Place a \(0\) in the \(i\)th place of a wrong \((n-1)\)-tuple not contained in \(\mathbb{T}_{j\to 1}^{i\to 0}(0_{i})\). (\(\mathbf{M}_{2}\)) Place a \(1\) in the \(i\)th place of a wrong \((n-1)\)-tuple that appears in \(\mathbb{T}_{j\to 1}^{i\to 0}(0_{i})\). The situation from a probabilistic point of view resembles the probability of picking the one correct configuration out of many. The total number of configurations is equal to the number of ways to place \(\approx\frac{m}{q}\) identical objects into \(\approx\frac{m}{2}\) distinguishable boxes. Hence, the probability that \(\mathrm{LT}_{j}\) places _all_ the \(\approx\frac{m}{4}\) bits \(0\) correctly in the \(\approx\frac{m}{2}\) uncertain \((n-1)\)-tuples is

\[P(\,\mathrm{LT}_{j}\text{ places all }0\text{ correctly })\approx\frac{1}{ \left(\frac{m/2}{m/4}\right)}\, \tag{10}\]

which is practically zero for sufficiently large \(m\). Thus, the cardinality of the symmetric difference

\[\mathbb{T}_{j\to 1}^{i\to 0}(0_{i})\,\triangle\,\mathbb{T}_{j\to 1}^{i\to 0}( \mathds{1}_{j})=\left(\mathbb{T}_{j\to 1}^{i\to 0}(0_{i})\,\backslash\,\mathbb{T}_{j\to 1}^{i\to 0}( \mathds{1}_{j})\right)\,\bigcup\left(\mathbb{T}_{j\to 1}^{i\to 0}( \mathds{1}_{j})\,\backslash\,\mathbb{T}_{j\to 1}^{i\to 0}(0_{i})\right) \tag{11}\]

will be significantly greater than \(0\) from a statistical point of view. Hence, when \(\mathrm{LT}_{i}\) uses the Algorithm 5 during (**Round\({}_{3}\)**) to verify the validity of the command vector \(\mathds{1}_{j}\) sent by \(\mathrm{LT}_{j}\), he will detect inconsistencies and stick to his preliminary decision. Ergo, \(\mathrm{LT}_{i}\) and all loyal lieutenant generals will be included in \(G_{0}\) at the end of the protocol. The case where [PERSON] conveys the command \(1\) is identical. Proposition A4 studies the situation where the commanding general [PERSON] is a traitor.