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 3: Line 3:


'''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-resilient distributed computing




Line 21: Line 20:
* 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>


Line 38: Line 37:
*<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==
==Hardware Requirements==
*Network stage: [[:Category:Fully Quantum Computing Network Stage|(Fault-tolerant) Quantum computing network stage]][[Category:Fully Quantum Computing Network Stage]]
*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. 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.
*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==
Line 58: 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).


==Protocol Description==
==Pseudo Code==
This pseudocode is based on the reference [[Quantum Byzantine Agreement#References|(1)]].
See Algorithm 1 and Algorithm 2 in [[Quantum Byzantine Agreement#References|(1)]] for a precise pseudo code.
 
====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==
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"