Fast Quantum Byzantine Agreement: Difference between revisions

From Quantum Protocol Zoo
Jump to navigation Jump to search
(Created page with " This protocol achieves the functionality of Quantum Cloning. Asymmetric universal cloning refers to a quantum cloning machine (QCM) where its output clones are not the sa...")
 
No edit summary
 
(63 intermediate revisions by 3 users not shown)
Line 1: Line 1:
This [https://dl.acm.org/citation.cfm?doid=1060590.1060662 example protocol] is an efficient solution to the classical task of [[Byzantine Agreement]].  It allows multiple players in a network to reach an agreement in the presence of some faulty players. The protocol solves the task in the strongest possible failure model (called Byzantine failures). The quantum protocol is provably faster than any classical protocol.
'''Tags:''' [[:Category: Quantum Enhanced Classical Functionality|Quantum Enhanced Classical Functionality]][[Category: Quantum Enhanced Classical Functionality]], [[:Category: Multi Party Protocols|Multi Party Protocols]] [[Category: Multi Party Protocols]],  [[:Category:Specific Task|Specific Task]][[Category:Specific Task]], consensus task, failure-resilient distributed computing


This protocol achieves the functionality of [[Quantum Cloning]]. Asymmetric universal cloning refers to a quantum cloning machine (QCM) where its output clones are not the same or in other words, they have different [[fidelities]]. Here we focus on <math>1 \rightarrow 1 + 1</math> universal cloning. In asymmetric cloning, we try to distribute information unequally among the copies. A trade-off relation exists between the fidelities, meaning if one of the copies are very close to the original state, the other one will be far from it. There are two approaches to this kind of cloning, both leading to same trade-off relation. Here we discuss the quantum circuit approach (Buzek et al., 1997) It can be also noted that the symmetric universal <math>1 \rightarrow 2</math> cloning can be considered as a special case of the asymmetric universal cloning where the information between copies has been equally distributed.


'''Tags:''' [[Category: Building Blocks]][[:Category: Building Blocks|Building Blocks]], [[Quantum Cloning]], Universal Cloning, asymmetric cloning, copying quantum states, [[:Category: Quantum Functionality|Quantum Functionality]][[Category: Quantum Functionality]], [[:Category:Specific Task|Specific Task]][[Category:Specific Task]],symmetric or [[Optimal Universal N-M Cloning|Optimal or Symmetric Cloning]], [[Probabilistic Cloning]]
==Assumptions==
==Assumptions==
* We assume that the original input qubit is unknown and the protocol is independent of the original input state (universality).
* '''Network:''' The network consists of <math>n</math> players that are fully identified and completely connected with pairwise authenticated classical and quantum channels.
* The output copies are not identical and we are able to control the likelihood (fidelity) of the output copies to the original state by pre-preparing the ancillary states with special coefficients.
* '''Timing:''' The synchronous and asynchronous timing models are both considered.
* '''Message size:''' The size of messages (quantum and classical) are unbounded.
* '''Shared resources:''' The nodes do not share any prior entanglement or classical correlations.
* '''Failure:''' At most <math>t < n/3</math> (synchronous) or <math>t < n/4</math> (asynchronous) players show Byzantine failures. The Byzantine failed players are allowed to behave arbitrarily and collude to try and prevent the honest players from reaching agreement. The most severe model is used: Byzantine failures are adaptive, computationally unbounded and have full-information (full information of quantum states is modelled by giving a classical description of the state to the adversaries). Failures on the communication channels are not considered.
 
==Outline==
==Outline==
In this protocol, there are three main stages. The first stage is a preparation stage. we prepare two ancillary states with special coefficients which will lead to the desired flow of the information between copied states. The original state will not be engaged at this stage. At the second stage the cloner circuit will act on all the three states (the original and two other states) and at the second stage the two copied state will appear at two of the outputs and one of the outputs should be discarded. The Procedure will be as following:
Here we will sketch the outline of the Fast Quantum Byzantine Agreement protocol by Ben-Or [[Quantum Byzantine Agreement#References|(3)]] that solves Byzantine Agreement using quantum resources. A very nice summary of this protocol is also presented in [[Quantum Byzantine Agreement#References|(1)]].
* Prepare two blank states and then perform a transformation taking these two states to a new state with pre-selected coefficients in such a way that the information distribution between two final states will be the desired.[[File:Asymmetriccloner.jpg|right|thumb|1000px| Graphical representation of the network for the asymmetric cloner. The CNOT gates are shown in the cloner section with control qubit (denoted as <math>\bullet</math> ) and a target qubit (denoted as <math>\circ</math> ). We separate the preparation of the quantum copier from the cloning process itself.]]
The main idea of this protocol is for each player to classically send its proposed input bit <math>b_i</math> to every other player in the network and then collaborate to determine what bit is proposed by a majority of honest players. In the case where failed players make this difficult, a 'good-enough' random coin is globally flipped  (using quantum resources, explained below), which is then classically post-processed to reach agreement among the honest parties. Let us make this more precise.
*Perform the cloner circuit. the cloner circuit consists of four CNOT gate acting in all the three input qubits. For every CNOT gate, we have a control qubit (which indicates whether or not the CNOT should act) and a target qubit (which is the qubit that CNOT gate acts on it and flips it).
 
* The two asymmetric clones will appear at two of the outputs (depending on the preparation stage) and the other output should be discarded.
The protocol consists of consecutive rounds. Initially, each player sets a decision bit to its input bit. Then in each round, the players take the following steps:
==Notations Used==
 
**<math>|\psi\rangle_{in}:</math>The original input state
* Each player transmits its current decision bit to every other player. If a player receives the same bit value from more than 2/3 of the players (including his own), then it sets his decision bit to this majority bit value. Otherwise, that player initiates a Quantum Oblivious Common Coin subroutine with all other players and sets his decision bit to the outcome of this subroutine.
**<math>\rho_{\psi_{in}}:</math> The density matrix of the input pure state equal to <math>|\psi_{in}\rangle\langle\psi_{in}|</math>
 
**<math>s_0:</math> The scaling parameter of the first clone
* Then each player sequentially executes two classical subroutines to bias the decision value towards <math>0</math> or <math>1</math>  respectively. These subroutines guarantee that if the non-faulty players are in agreement, then they will terminate and successfully output the correct agreement value.
**<math>s_12:</math> The scaling parameter of the second clone
</br>
**<math>\rho_{a}^{out}:</math> The output density matrix of the first clone (equal to <math>|\psi_{a}^{out}\rangle\langle\psi_{a}^{out}|</math> if the output state is pure)
 
**<math>\rho_{b}^{out}:</math> The output density matrix of the second clone (equal to <math>|\psi_{b}^{out}\rangle\langle\psi_{b}^{out}|</math> if the output state is pure)
'''Quantum Oblivious Common Coin subroutine:'''
**<math>\hat{I}:</math> The ``Identity" or completely mixed density matrix
The heart of this protocol comes from the quantum enhanced [[Oblivious Common Coin]]. At the end of this subroutine, each player <math>i</math> outputs a random bit <math>v_i</math>, such that with at least probability <math>p</math> (called the fairness) <math>v_i = x</math> for all players <math>i</math> and all <math>x \in \{0,1\} </math>. Intuitively, this subroutines tosses a common coin, where all players get either <math>0</math> or <math>1</math> with probability at least <math>p</math> each, but there may be executions (which occur with at most probability <math>1-2p</math>) where all players do not get the same output and no common coin is actually tossed. Since the players do not know whether the outcomes are all equal or not, this type of coin tossing is referred to
**<math>|0\rangle_{m_0} \otimes |0\rangle_{n_0} \equiv |00\rangle:</math> state of the ancillary qubits before preparation phase
as oblivious common coin tossing. In particular, using quantum resources, this task can be achieved in constant rounds (in the defined model). The implementation of this subroutine makes use of a weakened
**<math>|\psi\rangle_{m_1,n_1}:</math>  state of the ancillary qubits after the preparation
version of [[Verifiable Quantum Secret Sharing]] (VQSS).
**<math>c_j:</math> amplitudes (or coefficients) of the prepared state $|\psi\rangle_{m_1,n_1}$. These coefficients are being used to control the flow of the information between the copies before starting the cloning process.
 
**<math>P_{k,l}:</math> The CNOT gate where the control qubit is <math>k</math> and the target qubit is <math>l</math>  
==Notation==
**<math>|\psi\rangle_{out}:</math> The total output of the asymmetric cloning circuit
*<math>n:</math> number of nodes
**<math>|\Phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle):</math> Bell state
*<math>t:</math> number of failures
**<math>|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle):</math> Plus state. The eigenvector of Pauli X
*<math>p:</math> fairness of the Oblivious Common Coin
*<math>k:</math> security parameter of the VQSS scheme used to implement the Oblivious Common Coin
*<math>b_i:</math> input bit of player <math>i</math>
*<math>v_i:</math> random bit output by player <math>i</math> in the Oblivious Common Coin subroutine
*<math>d:</math> the agreement value at the end of the protocol
 
==Requirements==
*Network stage: [[:Category:Fully Quantum Computing Network Stage|(Fault-tolerant) Quantum computing network stage]][[Category:Fully Quantum Computing Network Stage]]
*Relevant network stage parameters: Required number of qubits <math>q</math>.
*Benchmark values: The number of qubits <math>q</math> required is precisely known for a finite instance of the protocol. This is calculated in [[Quantum Byzantine Agreement#References|(1)]] for <math>n = 5</math>. They pick the smallest possible security parameter <math>k = 2</math> (of the VQSS scheme) and start calculating the required resources. Summarising they find that each node requires <math>\sim 200</math> operational qubits, on which quantum circuits of depth <math>\sim 2000</math> must be run. The consumed number of Bell pairs is 648 and the total classical communication cost is 21240 bits. It is not entirely clear if these are the expected costs or the cost per round.
*In a more asymptotic sense, it is known that the required number of qubits per node grows rapidly with the number of nodes <math>n</math>, making it, therefore, demanding on qubit requirements.
 
==Knowledge Graph==
 
{{graph}}


==Properties==
==Properties==
*The protocol assumes that the original input qubit is unknown and the protocol is independent of the original input state (universality).
The protocol
*The output copies are not identical and we are able to control the likelihood (fidelity) of the output copies to the original state by pre-preparing the ancillary states with special coefficients.
* solves the problem in <math>O(1)</math> expected number of rounds, in particular independent of <math>n</math> and <math>t</math>, whereas classically a lower bound of <math>\Omega\left(\sqrt{n / \log(n)}\right)</math> is known [[Quantum Byzantine Agreement#References|(3), (6)]];
*Claims for General case:
* tolerates <math>t \leq n/3</math> (synchronous) or <math>t \leq n/4</math> (asynchronous) Byzantine failures;
**Following inequality holds between the scaling factors <math>s_0</math> and <math>s_1</math></br>
* reaches ''agreement'' (each player outputs the same bit) under the ''validity'' condition (the agreement value was proposed by at least one player) and is guaranteed to ''terminate eventually'' (infinite executions occur almost never - i.e. have probability measure zero).
<math>s_0^2 + s_1^2 + s_0 s_1 - s_0 - s_1 \leq 0</math>
 
**This elliptic inequality shows the possible value of the scaling parameters.
The Quantum Oblivious Common Coin subroutine has a single parameter <math>k</math> (used in the [[Verifiable Quantum Secret Sharing scheme]]), but it is unclear from the works [[Quantum Byzantine Agreement#References|(1), (3)]] how the parameter <math>k</math> influences the guarantees of the protocol.
**Trade-off inequality between the fidelities of the clones:</br>
 
<math>\sqrt{(1 - F_a)(1 - F_b)} \geq \frac{1}{2} - (1 - F_a) - (1 - F_b)</math>
Also note that the fairness <math>p</math> of the Quantum Oblivious Common Coin is not a parameter, but rather a result of the specific implementation of the protocol. The global Byzantine Agreement protocol can then tolerate up to <math>t < \left \lfloor{pn}\right \rfloor </math> failures. The Quantum Oblivious Common Coin subroutine proposed by [[Quantum Byzantine Agreement#References|(3)]] has <math>p > 1/3</math> (synchronous case, <math>p > 1/4</math> asynchronous case).
**Optimality is provided when the fidelities of two clones, <math>F_a</math> and <math>F_b</math>, saturate the above inequality
 
*Claims for Special case with bell state:
==Protocol Description==
**Following ellipse equation holds between the scaling factors <math>a</math> and <math>b</math></br>
This pseudocode is based on the reference [[Quantum Byzantine Agreement#References|(1)]].
<math>a^2 + b^2 + ab = 1</math>
**Following equations holds for fidelities of the clones:
<math>F_a = 1 - \frac{b^2}{2}, F_b = 1 - \frac{a^2}{2}</math>


==Pseudo Code==
====Fast Byzantine Agreement====
===General Case===
'''Input:''' Each player starts with an input bit <math>b_i</math> and the number of players <math>n</math> and a security parameter <math>k</math>. <br>
For more generality, we use the [[density matrix]] representation of the states which includes [[mixed states]] as well as [[pure states]]. For a simple pure state <math>|\psi\rangle</math> the density matrix representation will be <math>\rho_{\psi} = |\psi\rangle\langle\psi|</math>. Let us assume the initial qubit to be in an unknown state <math>\rho_{\psi}</math>. Our task is to clone this qubit universally, i.e. input-state independently, in such a way, that we can control the scaling of the original and the clone at the output. In other words, we look for output which can be represented as below:</br>
'''Output:''' Each player outputs a bit <math>d_i</math>. With high probability, <math>d_i = d</math> for all players <math>i</math> (agreement) and some <math>d \in \{b_i\}_i</math> (validity).
<math>\rho_{a}^{out} = s_0 \rho_{\psi} + \frac{1 - s_0}{2} \hat{I}</math></br>
 
<math>\rho_{b}^{out} = s_1 \rho_{\psi} + \frac{1 - s_1}{2} \hat{I}</math></br>
Protocol for each player <math>i</math>:
Here we assume that the original qubit after the cloning is “scaled” by the factor <math>s_0</math>, while the copy is scaled by the factor <math>s_1</math>. These two scaling parameters are not independent and they are related by a specific inequality.</br></br>
 
<u>'''Stage 1'''</u> Cloner State Preparation
'''Repeat''' forever (until something is returned):
# Prepare the original qubit and two additional blank qubits <math>m</math> and <math>n</math> in pure states: <math>|0\rangle_{m_0} \otimes |0\rangle_{n_0} \equiv |00\rangle</math>
# ''Subroutine <math>P_r(b_i)</math>:'' (this flips the oblivious common coin if no 2/3 majority is reached)
#Prepare <math>|\psi\rangle_{m_1,n_1} = c_1|00\rangle + c_2|01\rangle + c_3|10\rangle + c_4|11\rangle</math>, where the complex <math>c_i</math> coefficients will be specified so that the flow of information between the clones will be as desired. </br>At this stage the original qubit is not involved, but this preparation stage will affect the fidelity of the clones at the end of the process.
## Send <math>b_i</math> to all other players <math>j \neq i</math>. Receive a bit <math>b_j</math> from all other players;
#To prepare the <math>|\psi\rangle_{m_1,n_1}</math> state, a Unitary gate must be performed so that:
## Let <math>x = \sum_j b_j</math>. '''If''' <math>x < n/3</math>, '''then''' set <math>b_i = 0</math>; '''elseif''' <math>x > 2n/3</math>, '''then''' set <math>b_i = 1</math>; '''else''' set <math>b_i = QOCC(n,k)</math> '''end''';
<math>U|00\rangle = |\psi\rangle_{m_1,n_1}</math>  
# ''Subroutine <math>P_0(b_i)</math>:'' (classical routine - biases towards 0 and finishes if 0 is the agreement value)
*Use following relations to specify <math>c_j</math> in terms of <math>a</math> and <math>b</math>:</br>
## Send <math>b_i</math> to all other players <math>j \neq i</math>. Receive a bit <math>b_j</math> from all other players;
<math>c_1 = \sqrt{\frac{s_0 + s_1}{2}}</math>, <math>c_2 = \sqrt{\frac{1 - s_0}{2}}</math>, <math>c_3 = 0</math>, <math>c_4 = \sqrt{\frac{1 - s_1}{2}}</math></br>
## Let <math>x = \sum_j b_j</math>. '''If''' <math>x < n/3</math>, '''then return''' <math>0</math>; '''elseif''' <math>x > 2n/3</math>, '''then''' set <math>b_i = 1</math>; '''else''' set <math>b_i = 0</math> '''end''';
these <math>c_j</math> satisfy the scaling equations and also the normalization condition of the state <math>|\psi\rangle_{m_1,n_1}</math>. They are being used to control the flow of information between the clones</br></br>
# ''Subroutine <math>P_1(b_i)</math>:'' (classical routine - biases towards 1 and finishes if 1 is the agreement value)
<u>'''Stage 2'''</u> Cloning Circuit
## Send <math>b_i</math> to all other players <math>j \neq i</math>. Receive a bit <math>b_j</math> from all other players;
*The cloning circuit consists of four CNOT gates acting on original and pre-prepared qubits from stage 2. We call the original qubit <math>|\psi\rangle_{in}</math>, ``first qubit", the first ancillary qubit of <math>|\psi\rangle_{m_1,n_1}</math>, ``second qubit" and the second one, ``third qubit". The CNOT gates will act as follows:
## Let <math>x = \sum_j b_j</math>. '''If''' <math>x < n/3</math>, '''then''' set <math>b_i = 0</math>; '''elseif''' <math>x > 2n/3</math>, '''then return''' <math>1</math>; '''else''' set <math>b_i = 1</math> '''end''';
#First CNOT acts on first and second qubit while the first qubit is control and the second qubit is the target.
 
#Second CNOT acts on first and third qubit while the first qubit is control and the third qubit is the target.
 
# Third CNOT acts on first and second qubit while the second qubit is control and the first qubit is the target.
====Quantum Oblivious Common Coin (QOCC)====
# Forth CNOT acts on first and third qubit while the third qubit is control and the first qubit is the target.
'''Input:''' Each player starts with the number of players <math>n</math> and a security parameter <math>k</math>. <br>
*Mathematically the cloning part of the protocol can be shown as:</br>
'''Output:''' Each player outputs a random bit <math>v_i</math>. With at least probability <math>p</math>, <math>v_i = x</math> for all <math>i</math> and all <math>x \in \{0,1\}.</math>
<math>|\psi\rangle_{out} = P_{3,1} P_{2,1} P_{1,3} P_{1,2} |\psi\rangle_{in} |\psi\rangle_{m_1,n_1}</math></br></br>
 
<u>'''Stage 3'''</u> Discarding ancillary state
Protocol for each player <math>i</math>:
*Discard one of the extra states. The output states will be the first and second (or third) output.</br></br>
 
===Special case with bell state:===
# Prepare state <math>|{\psi}\rangle = \left(\sum_{i=1}^n |{i}\rangle \right)^{\otimes n} </math>
<u>'''Stage 1'''</u> Cloner state preparation
# Share and verify <math>|{\psi}\rangle</math> with a VQSS scheme (with security parameter <math>k</math>). During the verification phase, use a (classical) gradecast scheme instead of a broadcast scheme (this change is named GradedQSV in [[Quantum Byzantine Agreement#References|(1)]]). Let <math>FP</math> denote the set of players that were caught cheating as a dealer.
# Prepare the original qubit and two additional blank qubits <math>m</math> and <math>n</math> in pure states: <math>|0\rangle_{m_0} \otimes |0\rangle_{n_0} \equiv |00\rangle</math>
# Measure each share of player <math>j</math> to obtain a random integer <math>s_{i,j}</math>.
# Prepare <math>|\psi\rangle_{m_1,n_1} = a|\Phi^{+}\rangle_{m_1,n_1} + b|0\rangle_{m_1} |+\rangle_{n_1}</math>, where <math>|\Phi^{+}\rangle</math> is a [[Bell state]] and <math>|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)</math>. In this case, the density matrix representation of the output states will be:</br>
# Use gradecast to share the numbers <math>s_{i,j}, j=1,...,n</math>. Add the dishonest players in the gradecast scheme to <math>FP</math>. Receive <math>s_{l,j}</math>, from each player <math>l=1,...,n, l \neq i</math>.
<math>\rho_{a}^{out} = (1 - b^2) |\psi\rangle\langle\psi| + \frac{b^2}{2} \hat{I}</math></br>
# '''if''' <math>j \in FP</math> '''then''' set <math>S_j = \perp</math> '''else''' set <math>S_j = \sum_{l \notin FP} s_{lj} \mod n</math>
<math>\rho_{b}^{out} = (1 - a^2) |\psi\rangle\langle\psi| + \frac{a^2}{2} \hat{I}</math></br>
# '''if''' <math>S_j = 0</math> for some <math>j</math>, '''then return''' 0; '''else return''' 1.
<u>'''Stage 2'''</u> Cloning Circuit
* The cloning circuit is exactly the same as the general case. after the cloning circuit, the output state will be:</br>
<math>a|\psi\rangle_{in} |\Phi^+\rangle_{m,n} + b|\psi\rangle_m |\Phi^+\rangle_{in,n}</math>
The reduced density matrix of two clones A and B can be written in terms of their fidelities:</br>
<math>\rho_{a}^{out} = F_a |\psi\rangle\langle\psi| + (1 - F_a)|\psi^{\perp}\rangle\langle\psi^{\perp}|</math></br>
<math>\rho_{b}^{out} = F_b |\psi\rangle\langle\psi| + (1 - F_b)|\psi^{\perp}\rangle\langle\psi^{\perp}|</math></br>
<u>'''Stage 3'''</u> Discarding ancillary state
* The same as the general case.


==Further Information==
==Further Information==
* The protocol [[Quantum Byzantine Agreement#References|(3)]] is based on the classical protocol of [[Quantum Byzantine Agreement#References|(7)]], where the classical Oblivious Common Coin is replaced by a quantum version. This Quantum Oblivious Common Coin is based on the Verifiable Quantum Secret Sharing Scheme presented in [[Quantum Byzantine Agreement#References|(4)]].
* The classical protocol of [[Quantum Byzantine Agreement#References|(7)]] also runs in constant expected time, but can only deal with limited-information adversaries. This means that the adversaries can not read communication between honest parties and read their internal state.
* The classical lower bound in the full-information Byzantine failure model of <math>\Omega\left(\sqrt{n / \log(n)}\right)</math> is proven in [[Quantum Byzantine Agreement#References|(6)]].
* The work [[Quantum Byzantine Agreement#References|(3)]] also provides a protocol in a weaker failure model known as fail-stop failures. Here the nodes will crash and stop working indefinitely (stop responding). Another protocol in the same model is presented in [[Quantum Byzantine Agreement#References|(2)]].
* Another weakened version of the problem, known as detectable byzantine agreement, is solved with quantum resources in [[Quantum Byzantine Agreement#References|(5)]] (and following works). In detectable byzantine agreement, the protocol is also allowed to abort (upon detecting failures) instead of reaching agreement.
==References==
# [https://arxiv.org/abs/1701.04588 TNM (2017)]
# [https://link.springer.com/book/10.1007%2F978-3-642-15763-9 LS (2010)]
# [https://dl.acm.org/citation.cfm?doid=1060590.1060662 BH (2005)]
# [https://dl.acm.org/citation.cfm?id=510000 CGS (2002)]
# [https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.87.217901 FGM (2001)]
# [https://dl.acm.org/citation.cfm?id=277733 JB (1998)]
# [https://dl.acm.org/citation.cfm?id=262544 FM (1997)]
# [https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf LSP (1982)]
<div style='text-align: right;'>''*contributed by Bas Dirke''</div>
<div style='text-align: right;'>''*contributed by Bas Dirke''</div>
<div style='text-align: right;'>''*edited by Shraddha Singh''</div>

Latest revision as of 15:19, 16 October 2019

This example protocol is an efficient solution to the classical task of Byzantine Agreement. It allows multiple players in a network to reach an agreement in the presence of some faulty players. The protocol solves the task in the strongest possible failure model (called Byzantine failures). The quantum protocol is provably faster than any classical protocol.


Tags: Quantum Enhanced Classical Functionality, Multi Party Protocols, Specific Task, consensus task, failure-resilient distributed computing


Assumptions[edit]

  • Network: The network consists of players that are fully identified and completely connected with pairwise authenticated classical and quantum channels.
  • Timing: The synchronous and asynchronous timing models are both considered.
  • Message size: The size of messages (quantum and classical) are unbounded.
  • Shared resources: The nodes do not share any prior entanglement or classical correlations.
  • Failure: At most (synchronous) or (asynchronous) players show Byzantine failures. The Byzantine failed players are allowed to behave arbitrarily and collude to try and prevent the honest players from reaching agreement. The most severe model is used: Byzantine failures are adaptive, computationally unbounded and have full-information (full information of quantum states is modelled by giving a classical description of the state to the adversaries). Failures on the communication channels are not considered.

Outline[edit]

Here we will sketch the outline of the Fast Quantum Byzantine Agreement protocol by Ben-Or (3) that solves Byzantine Agreement using quantum resources. A very nice summary of this protocol is also presented in (1). The main idea of this protocol is for each player to classically send its proposed input bit to every other player in the network and then collaborate to determine what bit is proposed by a majority of honest players. In the case where failed players make this difficult, a 'good-enough' random coin is globally flipped (using quantum resources, explained below), which is then classically post-processed to reach agreement among the honest parties. Let us make this more precise.

The protocol consists of consecutive rounds. Initially, each player sets a decision bit to its input bit. Then in each round, the players take the following steps:

  • Each player transmits its current decision bit to every other player. If a player receives the same bit value from more than 2/3 of the players (including his own), then it sets his decision bit to this majority bit value. Otherwise, that player initiates a Quantum Oblivious Common Coin subroutine with all other players and sets his decision bit to the outcome of this subroutine.
  • Then each player sequentially executes two classical subroutines to bias the decision value towards or respectively. These subroutines guarantee that if the non-faulty players are in agreement, then they will terminate and successfully output the correct agreement value.


Quantum Oblivious Common Coin subroutine: The heart of this protocol comes from the quantum enhanced Oblivious Common Coin. At the end of this subroutine, each player outputs a random bit , such that with at least probability (called the fairness) for all players and all . Intuitively, this subroutines tosses a common coin, where all players get either or with probability at least each, but there may be executions (which occur with at most probability ) where all players do not get the same output and no common coin is actually tossed. Since the players do not know whether the outcomes are all equal or not, this type of coin tossing is referred to as oblivious common coin tossing. In particular, using quantum resources, this task can be achieved in constant rounds (in the defined model). The implementation of this subroutine makes use of a weakened version of Verifiable Quantum Secret Sharing (VQSS).

Notation[edit]

  • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n:} number of nodes
  • number of failures
  • fairness of the Oblivious Common Coin
  • security parameter of the VQSS scheme used to implement the Oblivious Common Coin
  • input bit of player
  • random bit output by player in the Oblivious Common Coin subroutine
  • the agreement value at the end of the protocol

Requirements[edit]

  • Network stage: (Fault-tolerant) Quantum computing network stage
  • Relevant network stage parameters: Required number of qubits Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} .
  • Benchmark values: The number of qubits required is precisely known for a finite instance of the protocol. This is calculated in (1) for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 5} . They pick the smallest possible security parameter (of the VQSS scheme) and start calculating the required resources. Summarising they find that each node requires Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sim 200} operational qubits, on which quantum circuits of depth must be run. The consumed number of Bell pairs is 648 and the total classical communication cost is 21240 bits. It is not entirely clear if these are the expected costs or the cost per round.
  • In a more asymptotic sense, it is known that the required number of qubits per node grows rapidly with the number of nodes , making it, therefore, demanding on qubit requirements.

Knowledge Graph[edit]

Properties[edit]

The protocol

  • solves the problem in expected number of rounds, in particular independent of and , whereas classically a lower bound of is known (3), (6);
  • tolerates (synchronous) or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t \leq n/4} (asynchronous) Byzantine failures;
  • reaches agreement (each player outputs the same bit) under the validity condition (the agreement value was proposed by at least one player) and is guaranteed to terminate eventually (infinite executions occur almost never - i.e. have probability measure zero).

The Quantum Oblivious Common Coin subroutine has a single parameter (used in the Verifiable Quantum Secret Sharing scheme), but it is unclear from the works (1), (3) how the parameter influences the guarantees of the protocol.

Also note that the fairness of the Quantum Oblivious Common Coin is not a parameter, but rather a result of the specific implementation of the protocol. The global Byzantine Agreement protocol can then tolerate up to failures. The Quantum Oblivious Common Coin subroutine proposed by (3) has (synchronous case, asynchronous case).

Protocol Description[edit]

This pseudocode is based on the reference (1).

Fast Byzantine Agreement[edit]

Input: Each player starts with an input bit and the number of players and a security parameter .
Output: Each player outputs a bit . With high probability, for all players (agreement) and some (validity).

Protocol for each player :

Repeat forever (until something is returned):

  1. Subroutine : (this flips the oblivious common coin if no 2/3 majority is reached)
    1. Send to all other players . Receive a bit from all other players;
    2. Let . If , then set ; elseif , then set ; else set end;
  2. Subroutine : (classical routine - biases towards 0 and finishes if 0 is the agreement value)
    1. Send to all other players . Receive a bit from all other players;
    2. Let . If , then return ; elseif , then set ; else set end;
  3. Subroutine : (classical routine - biases towards 1 and finishes if 1 is the agreement value)
    1. Send to all other players . Receive a bit from all other players;
    2. Let . If , then set ; elseif , then return ; else set end;


Quantum Oblivious Common Coin (QOCC)[edit]

Input: Each player starts with the number of players and a security parameter .
Output: Each player outputs a random bit . With at least probability , for all and all

Protocol for each player :

  1. Prepare state
  2. Share and verify with a VQSS scheme (with security parameter ). During the verification phase, use a (classical) gradecast scheme instead of a broadcast scheme (this change is named GradedQSV in (1)). Let denote the set of players that were caught cheating as a dealer.
  3. Measure each share of player to obtain a random integer .
  4. Use gradecast to share the numbers . Add the dishonest players in the gradecast scheme to . Receive , from each player .
  5. if then set else set
  6. if for some , then return 0; else return 1.

Further Information[edit]

  • The protocol (3) is based on the classical protocol of (7), where the classical Oblivious Common Coin is replaced by a quantum version. This Quantum Oblivious Common Coin is based on the Verifiable Quantum Secret Sharing Scheme presented in (4).
  • The classical protocol of (7) also runs in constant expected time, but can only deal with limited-information adversaries. This means that the adversaries can not read communication between honest parties and read their internal state.
  • The classical lower bound in the full-information Byzantine failure model of is proven in (6).
  • The work (3) also provides a protocol in a weaker failure model known as fail-stop failures. Here the nodes will crash and stop working indefinitely (stop responding). Another protocol in the same model is presented in (2).
  • Another weakened version of the problem, known as detectable byzantine agreement, is solved with quantum resources in (5) (and following works). In detectable byzantine agreement, the protocol is also allowed to abort (upon detecting failures) instead of reaching agreement.

References[edit]

  1. TNM (2017)
  2. LS (2010)
  3. BH (2005)
  4. CGS (2002)
  5. FGM (2001)
  6. JB (1998)
  7. FM (1997)
  8. LSP (1982)
*contributed by Bas Dirke