Fast Quantum Byzantine Agreement: Difference between revisions

no edit summary
No edit summary
Line 1: Line 1:
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.


The classical problem of Byzantine agreement [[Quantum Byzantine Agreement#References|(8)]] is about reaching agreement in a network of <math>n</math> players out of which <math>t</math> players may be faulty. Each player starts with an input bit <math>b_i</math> and the goal is for all correct players to output the same bit <math>d</math> [[agreement]], under the constraint that <math>d = b_i</math> at least for some node <math>i</math> [[validity]]. The [[hardness]] of this task depends on the [[failure model]] of the faulty (sometimes called [[adversary]]) players. In Byzantine agreement, the faulty players are assumed to show the most severe form of failure known as Byzantine failures. In this model, faulty players behave arbitrarily, can collude and even act maliciously trying to prevent correct players from reaching agreement. Byzantine agreement is an important problem in classical distributed systems, used to guarantee consistency amongst distributed data structures.


'''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
'''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:''' [[Synchronous]] and [[asynchronous]] setting 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) Byzantine node failures are assumed. Byzantine failures 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). [[Link failures]] 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|50px|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 most strong model requires constant expected number of rounds, whereas a classical lower bound of <math>{\Omega}(\sqrt{n / \log(n)})</math> is known.]]
[[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 protocol by Ben-Or [[Quantum Byzantine Agreement#References|(3)]] that solve 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 value/decision (a valid message) to every other player and then collaborate to determine what a majority of honest players proposed. In the case where adversaries 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. More precisely, the protocol is outlined as follows. Each round consists of the following steps:
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 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.


* Each player transmits its input to every other player. If one player receives more than 2/3 of the same values from the other players (including his own), then he changes his input also to this value (if that player already did not have the same choice). Otherwise, the same player executes a Quantum Oblivious Common Coin subroutine and sets his input to the outcome of this routine.
* 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>.
* Then each player sequentially executes two classical subroutines to bias the agreement value towards <math>0</math> or <math>1</math> (outcomes of a coin flip). This guarantees that if the non-faulty players are in agreement, then they will terminate and successfully output the correct agreement value <math>d</math> (not an outcome of coin flip).
</br>
</br>


'''[[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 a least probability value (called the [[fairness]]) <math>0</math> or <math>1</math>. Intuitively, this subroutines tosses a common coin, where all players get either heads or tails, each with fairness probability, but there may be executions 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).
'''[[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
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).


==Notations Used==
==Notation==
**<math>n:</math> number of nodes
*<math>n:</math> number of nodes
**<math>t:</math> number of failures
*<math>t:</math> number of failures
**<math>p:</math> fairness of the Oblivious Common Coin
*<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>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>d:</math> the agreement value at the end of the protocol
*<math>d:</math> the agreement value at the end of the protocol


===Relevant Parameters===
===Relevant Parameters===
Write
262

edits