Write, autoreview, editor, reviewer
3,129
edits
Fast Quantum Byzantine Agreement: Difference between revisions
→Outline
| Line 11: | Line 11: | ||
==Outline== | ==Outline== | ||
[[File:ByzantineAgreementFig.PNG|50px|frame|Schematic representation of an execution of a Byzantine Agreement protocol with | [[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.]] | ||
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)]]. | 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: | 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: | ||
| Line 18: | Line 18: | ||
* 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). | * 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 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). | ||