Detectable {B}yzantine {A}greement Secure Against Faulty Majorities
Matthias Fitzi and Daniel Gottesman and Martin Hirt and Thomas Holenstein and Adam Smith
It is well-known that $n$ players, connected only by pairwise secure
channels, can achieve Byzantine agreement only if the number $t$ of
cheaters satisfies $t<n/3$, even with respect to computational
security. However, for many applications it is sufficient to achieve
\db}. With this primitive, broadcast is only guaranteed when all
players are non-faulty (``honest''), but all non-faulty players always
reach agreement on whether broadcast was achieved or not. We show that
\db can be achieved regardless of the number of faulty players (i.e.,
for all $t<n$). We give a protocol which is unconditionally secure, as
well as two more efficient protocols which are secure with respect to
computational assumptions, and the existence of quantum channels,
respectively.
These protocols allow for secure multi-party computation tolerating
any $t<n$, assuming only pairwise authenticated channels. Moreover,
they allow for the setup of public-key infrastructures that are
consistent among all participants — using neither a trusted party
nor broadcast channels.
Finally, we show that it is not even necessary for players to begin
the protocol at the same time step. We give a ``detectable Firing
Squad'' protocol which can be initiated by a single user at any time
and such that either all honest players end up with synchronized
clocks, or all honest players abort.