Coordination

Leader election

Main difference compared to classical seems to be lifting computational assumptions.

Definition a bit inferred from combining [leader_election] and [bit_escrow]

• each party $i$ decides $d_i\in [n]\cup \{\mathrm{err}\}$
• if all honest:
  • $Pr(d_i=\mathrm{err})=0$
  • $Pr(d_i=i)=\frac{1}{n}$
• if player $i$ (NB in [bit_escrow] there are only two) is honest
  • $Pr(d_i=i)\le \frac{1}{n}+ϵ$

In [exact_leader_election] the outcomes are binary (i.e., me or not me), which may make more sense compared to [leader_election] as it doesn’t need to coordinate necessarily.

Note

Uniqueness of the leader with cheaters seems to be swept under the rug in [leader_election].

Quantum Leader Election

[leader_election]

Idea:

• use tournament with weak quantum coin (e.g., [bit_escrow])
• NB I’m not sure how they ensure tournament consistency

[FairAndUnbiasedLE]

Consensus

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

Algorithms based on secret sharing

See secret sharing.

Algorithm for quantum byzantine agreement

[FastBFT]

• constant expected number of rounds compared for the randomized (adaptive adversary)
• Assumptions:
  • adaptive full information adversary
  • failure models: Byzantine / crash faults
• 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

[ImprovedConsensusFull]

• Assumptions:
  • adaptive full information adversary
  • failure models: Byzantine / crash faults
• requires fewer Bell pairs by using some kind of gossip protocol

Note

The arity of entanglement is still $O(n)$

Algorithms based on quantum signatures

Quantum signatures are to a large degree also based on correlated lists):

Beating the fault-tolerance bound for byzantine agreement

[Beating]

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

Simulations / physical realization

Netsquid-based:

• Resource-aware System Architectural Model for Implementation of QBA [ResourceQBA]

  Proposes specific circuit implementation for the Ben-Or’s algorithm

• [Beating]

  • The algorithm is from the same paper

  • All the quantum part is done in a lab using “four-intensity decoy-state BB84 key generation process”

Lower bounds

• number of faults:

  • according to [DBAMajorities], $f<n/3$ holds for quantum channels and private coins

  • [EasyImpossibility]: impossibility proofs for classical synchronous consensus

    Note

    Probabilistic Byzantine agreement (Crusader agreement) also requires $f<n/3$, see decentralized-thoughts

  • [MinimalPrimitives]:

    • $f<n/3$ also for randomized algorithms
    • seems to give different bounds based on the number of nodes that a given primitive affects

  • [BcastAndPseudoSigs]

• number of rounds:

  • [LowerBoundRandom]: $\Theta (t/\sqrt{n\log n})$

Detectable Byzantine agreement (DBA)

Note

Apparently, for DBA none of the algorithms below maintain quantum state, hence the size and decoherence time of quantum memory are irrelevant.

As per [DBAMajorities]:

• 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

As per [QDBAEPR]:

• Correctness If all generals are loyal, protocol achieves Byzantine Agreement
• Consistency All loyal generals either follow the same order or abort.
• Validity If the commanding general is loyal, then either of the two:
  • all loyal lieutenants follow the commander’s order
  • all loyal lieutenants abort

Further problem decomposition is presented in [DBAMajorities] 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

Protocols based on correlated lists

A Quantum solution to the Byzantine agreement problem

[QuantumSolution]

• 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

[ExperimentalBA]

Explicitly 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:

[QDBABlockchain]

• 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

[QBADishonest]

• trusted quantum source
• States: ${\sum }_j|j⟩\otimes |j+i_1\text{ mod }d⟩\otimes \dots |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

[QDBAEPR]

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

Note

Completeness (see above) is probabilistic here

Simulations / physical realization

• [NoiseAwareDBA]:

  • filter batches of EPR-pairs testing fidelity and dropping those with the fidelity below the threshold
  • noise-mitigation techniques

• [InSilicoDBA]:

  • uses proprietary simulator
  • focus is on the epr algorithm

Oblivious transfer

Classical case

[RabinOT]

Quantum case

[EfficientQOT]

[QBCImpossibility]

[FlexibleQuantumQueries]

Other works

• [QDC]: not quite a “consensus” as the outcome is _always random
• [CompPowerWvsGHZ]: Computational power of W vs. GHZ states in anonymous setting

Simulations / physical realization

• [BenchmarkingProtocols] evaluating the following algorithms with NetSquid:

  • quantum coin (i.e., smth that can be emitted and later verified)
  • anonymous qubit transmission via $W$-state
  • verifiable blind quantum computation
  • quantum digital signature

  Common sources of noise:

  • noisy operations
  • noisy memory
  • noisy channels

They have implementation.