Write
262
edits
Fast Quantum Byzantine Agreement: Difference between revisions
→Pseudo Code
| Line 53: | Line 53: | ||
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). | 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). | ||
== | ==Pseudocode== | ||
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>. <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). | |||
'''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)</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>. <br> | |||
'''Output:''' Each player outputs a random bit <math>r_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). | |||
==Further Information== | ==Further Information== | ||