Quantum Byzantine Agreement - Sketch of The Algorithm

Sketch of The Algorithm

We will sketch here the asynchronous algorithm The algorithm works in two phases:

• Phase 1 (Communication phase):

All messages are sent and received in this round.:A coin flipping protocol is a procedure that allows two parties A and B that do not trust each other to toss a coin to win a particular object.

There are two types of coin flipping protocols

• • weak coin flipping protocols: The two players A and B initially start with no inputs and they are to compute some value and be able to accuse anyone of cheating. The protocol is successful if A and B agree on the outcome. The outcome 0 is defined as A winning and 1 as B winning. The protocol has the following properties:
    • If both players are honest (they follow the protocol), then they agree on the outcome of the protocol with for .
    • If one of the players is honest (i.e., the other player may deviate arbitrarily from the protocol in his or her local computation), then the other party wins with probability at most . In other words, if B is dishonest, then, and if A is dishonest, then .
  • A strong coin flipping protocol: In a strong coin flipping protocol, the goal is instead to produce a random bit which is biased away from any particular value 0 or 1. Clearly, any strong coin flipping protocol with bias leads to weak coin flipping with the same bias.