Editing Fast Quantum Byzantine Agreement

Jump to navigation Jump to search
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then publish the changes below to finish undoing the edit.

Latest revision Your text
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.
Fast Quantum Byzantine Agreement [[Quantum Byzantine Agreement#References|(3)]] is an efficient quantum protocol that solves the classical task of [[Byzantine Agreement]] [[Quantum Byzantine Agreement#References|(8)]].  The protocol allows <math>n</math> players in a network to reach agreement in the presence of <math>t</math> faulty players. The protocol solves the task in the strongest possible failure model ([[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
'''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 resistant distributed computing
 




==Assumptions==
==Assumptions==
* '''Network:''' The network consists of <math>n</math> players that are fully identified and completely connected with pairwise authenticated classical and quantum channels.
* '''Network:''' The network consists of <math>n</math> 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.
* '''Timing:''' The [[Synchronous]] and [[asynchronous]] timing models are both considered.
* '''Message size:''' The size of messages (quantum and classical) are unbounded.
* '''Message size:''' The size of messages (quantum and classical) are unbounded.
* '''Shared resources:''' The nodes do not share any prior entanglement or classical correlations.
* '''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.
* '''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 modeled by giving a classical description of the state to the adversaries). Failures on the communication channels are not considered.
 


==Outline==
==Outline==
[[File:ByzantineAgreementFig.PNG|frame|Schematic representation of an execution of a Byzantine Agreement protocol with <math>n = 5</math> nodes and <math>t = 1</math> Byzantine failure. The red bits indicate the input value of each node, whereas the green bit represents the output. The solution shown satisfies the ''agreement'' and ''validity'' properties. The quantum Byzantine agreement protocol in the strongest possible failure model requires <math>{O}(1)</math> expected number of rounds, whereas a classical lower bound of <math>{\Omega}(\sqrt{n / \log(n)})</math> is known.]]
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)]].
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)]].
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.
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.
Line 21: Line 23:
* 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.
* 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 <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.
* 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>d</math>.
</br>
</br>


'''Quantum Oblivious Common Coin subroutine:'''  
'''[[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 <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
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
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
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
Line 35: Line 37:
*<math>k:</math> security parameter of the VQSS scheme used to implement 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>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
*<math>d:</math> the agreement value at the end of the protocol


==Requirements==
===Relevant Parameters===
*Network stage: [[:Category:Fully Quantum Computing Network Stage|(Fault-tolerant) Quantum computing network stage]][[Category:Fully Quantum Computing Network Stage]]
The number of players <math>n</math> and the number of failures <math>t</math> are previously introduced parameters of the agreement protocol. The Quantum Oblivious Common Coin protocol has a single parameter <math>k</math> (used in Verified Quantum Secret Sharing scheme), but it is unclear from the works [[Quantum Byzantine Agreement#References|(1), (3)]] how this influences the guarantees of the protocol. 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>. The Quantum Oblivious Common Coin subroutine proposed by [[Quantum Byzantine Agreement#References|(3)]] has <math>p > \frac{1}{3}</math> (synchronous case, <math>p > \frac{1}{4}</math> asynchronous case).
 
==Hardware Requirements==
*Network stage: [[:Category: Quantum Computing Network Stage|(Fault-tolerant) Quantum computing network stage]][[Category:Quantum Computing Network Stage]]
*Relevant network stage parameters: Required number of qubits <math>q</math>.
*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.
*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. Summarizing 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.
*In 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
The protocol-
* 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)]];
* 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(\sqrt{n / \log(n)})</math> is known [[Quantum Byzantine Agreement#References|(3), (6)]];
* tolerates <math>t \leq n/3</math> (synchronous) or <math>t \leq n/4</math> (asynchronous) Byzantine failures;
* tolerates <math>t \leq n/3</math> (synchronous) or <math>t \leq n/4</math> (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).
* 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 <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.
==Pseudo Code==
 
See Algorithm 1 and Algorithm 2 in [[Quantum Byzantine Agreement#References|(1)]] for a precise pseudocode.
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).
 
==Protocol Description==
This pseudocode is based on the reference [[Quantum Byzantine Agreement#References|(1)]].
 
====Fast Byzantine Agreement====
'''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>
'''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).
 
Protocol for each player <math>i</math>:
 
'''Repeat''' forever (until something is returned):
# ''Subroutine <math>P_r(b_i)</math>:'' (this flips the oblivious common coin if no 2/3 majority is reached)
## 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;
## 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''';
# ''Subroutine <math>P_0(b_i)</math>:'' (classical routine - biases towards 0 and finishes if 0 is the agreement value)
## 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;
## 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''';
# ''Subroutine <math>P_1(b_i)</math>:'' (classical routine - biases towards 1 and finishes if 1 is the agreement value)
## 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;
## 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''';
 
 
====Quantum Oblivious Common Coin (QOCC)====
'''Input:''' Each player starts with the number of players <math>n</math> and a security parameter <math>k</math>. <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>
 
Protocol for each player <math>i</math>:
 
# Prepare state <math>|{\psi}\rangle = \left(\sum_{i=1}^n |{i}\rangle \right)^{\otimes n} </math>
# 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.
# Measure each share of player <math>j</math> to obtain a random integer <math>s_{i,j}</math>.
# 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>.
# '''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>
# '''if''' <math>S_j = 0</math> for some <math>j</math>, '''then return''' 0; '''else return''' 1.


==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 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, which is based on the Verifiable Quantum Secret Sharing Scheme presented in [[Quantum Byzantine Agreement#References|(4)]]. The 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 same model of <math>\Omega(\sqrt{n \log n})</math> is proven in [[Quantum Byzantine Agreement#References|(6)]].
* 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)]].
* 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.
* 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==
==References==
# [https://arxiv.org/abs/1701.04588 TNM (2017)]
# [https://iopscience.iop.org/article/10.1088/2058-9565/aa9bb1/meta TNM (2017)]
# [https://link.springer.com/book/10.1007%2F978-3-642-15763-9 LS (2010)]
# [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?doid=1060590.1060662 BH (2005)]
Please note that all contributions to Quantum Protocol Zoo may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see Quantum Protocol Zoo:Copyrights for details). Do not submit copyrighted work without permission!

To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:

Cancel Editing help (opens in new window)

Template used on this page:

Retrieved from "https://wiki.veriqloud.fr/index.php?title=Fast_Quantum_Byzantine_Agreement"