Coordination

Consensus

In the Byzantine setting the focus is often on detectable agreement.

• algorithm for quantum byzantine agreement:

  • constant expected number of rounds compared for the randomized (adaptive adversary)
  • States: ${\sum }_{a=1}^{n^3}|a,\dots ,a⟩$
  • Byzantine needs verifiable (can agree that secret can be recovered) secret sharing for random numbers

• Improved Consensus in Quantum Networks

  • somehow requires fewer Bell pairs

Detectable Byzantine agreement (DBA)

Classical presentation is given in:

• Correctness all honest players commonly accept or reject the protocol. If all accept, then the protocol achieves broadcast
• Completeness if no player is corrupted, all accept
• Fairness if any honest player rejects, then the adversary gets no information about the sender's input

Further problem decomposition is presented in Detectable Byzantine Agreement Secure Against Faulty Majorities introducing

Detectable Precomputation:

• Correctness: all honest players commonly accept or reject the protocol. If all accept, then strong broadcast will be achievable
• Completeness if no player is corrupted, all accept
• Independence any honest player's input value need not be known

Quantum solutions

Protocols based on correlated lists:

• A Quantum solution to the Byzantine agreement problem

  • for weak agreement (or detectable broadcast), where a single faulty player may force everyone to abort
  • States: $|A⟩=|0,1,2⟩+|1,2,0⟩+|2,0,1⟩-|0,2,1⟩-|1,0,2⟩-|2,1,0⟩$ (Aharonov tri-partite qutrit states)
  • N = 3, f = 1

• Experimental demonstration of a quantum protocol for Byzantine agreement and liar detection says that the key is to construct secret and correlated lists

  • Based on the list $l_A$, $l_B$, and $l_C$ that are correlated and are produced from 4-qubit entangled states
  • States: $|{\Psi }^{(4)}{⟩}_{\mathrm{abcd}}=2|0011⟩-|0101⟩-|0110⟩-|1001⟩-|1010⟩+2|1100⟩$
  • N = 3, f = 1

• Quantum detectable Byzantine agreement for distributed data trust management in blockchain:

  • a lot of pairwise interaction among the lieutenants and the general
  • States: $|000⟩\pm |111⟩$, $|010⟩\pm |101⟩$, $|011⟩\pm |100⟩$ (GHZ-like)
  • N > f + 1

• Quantum Byzantine Agreement for Any Number of Dishonest Parties

  • trusted quantum source
  • States: ${\sum }_j|j⟩\otimes |j+i_1\text{ mod }d⟩\otimes ...|j+i_n\text{ mod }d⟩$ (multi-partite qudits)
  • N > f + 1
  • gives counterexamples for two other works (not listed here) to be incorrect

• A Quantum Detectable Byzantine Agreement Protocol using only EPR pairs

  • States: $|00⟩+|11⟩$ (EPR pairs)
  • N > f + 1

Protocols based on quantum signatures (which are to a large degree also based on correlated lists):

• Beating the fault-tolerance bound for byzantine agreement

  • Recusrive algorithm, similar to the one in LSP
  • Unlike LSP, signatures cannot be verified by all the parties
  • N > 2 f

Other works

• Quantum Distributed Consensus: not quite a "consensus" as the outcome is _always random