Abstract Reaching agreement in the presence of arbitrary faults is a fundamental problem in distributed computation, which has been shown to be unsolvable if one-third of the processes can fail, unless signed messages are used. In this paper, we propose a solution to a variation of the original BA problem, called Detectable Byzantine Agreement (DBA), that does not need to use signed messages. The proposed algorithm uses what we call Q-correlated lists, which are generated by a quantum source device. Once each process has one of these lists, they use them to reach the agreement in a classical manner. Although, in general, the agreement is reached by using
m+1 m + 1 rounds (where m is the number of processes that can fail), if less than one-third of the processes fail it only needs one round to reach the agreement.
We exhibit that, when given a classical Byzantine agreement protocol designed in the private-channel model, it is feasible to construct a quantum agreement protocol that can effectively handle a full-information adversary. Notably, both protocols have equivalent levels of resilience, round complexity, and communication complexity. In the classical private-channel scenario, participating players are limited to exchanging classical bits, with the adversary lacking knowledge of the exchanged messages. In contrast, in the quantum full-information setting, participating players can exchange qubits, while the adversary possesses comprehensive and accurate visibility into the system's state and messages. By showcasing the reduction from quantum to classical frameworks, this paper demonstrates the strength and flexibility of quantum protocols in addressing security challenges posed by adversaries with increased visibility. It underscores the potential of leveraging quantum principles to improve security measures without compromising on efficiency or resilience. By applying our reduction, we demonstrate quantum advantages in the round complexity of asynchronous Byzantine agreement protocols in the full-information model. It is well known that in the full-information model, any classical protocol requires
Ω(n) rounds to solve Byzantine agreement with probability one even against Fail-stop adversary when resilience
t=Θ(n). We show that quantum protocols can achieve
O(1) rounds (i) with resilience
t0, therefore surpassing the classical lower bound.