[Resource Topic] 2002/053: Extended Validity and Consistency in Byzantine Agreement

Welcome to the resource topic for 2002/053

Extended Validity and Consistency in Byzantine Agreement

Authors: Matthias Fitzi, Martin Hirt, Thomas Holenstein, Jürg Wullschleger


A broadcast protocol allows a sender to distribute a value among a set of
players such that it is guaranteed that all players receive the same
value (consistency), and if the sender is honest, then all players
receive the sender’s value (validity). Classical broadcast protocols for
n players provide security with respect to a fixed threshold t<n/3,
where both consistency and validity are guaranteed as long as at most t
players are corrupted, and no security at all is guaranteed as soon as
t+1 players are corrupted. Depending on the environment, validity or
consistency may be the more important property.

We generalize the notion of broadcast by introducing an additional
threshold t^+\ge t. In a {\em broadcast protocol with extended
validity}, both consistency and validity are achieved when no more than
t players are corrupted, and validity is achieved even when up to t^+
players are corrupted. Similarly, we define {\em broadcast with extended
consistency}. We prove that broadcast with extended validity as well as
broadcast with extended consistency is achievable if and only if
t+2t^+<n (or t=0).
For example, six players can achieve broadcast when at most one player is
corrupted (this result was known to be optimal), but they can even
achieve consistency (or validity) when two players are corrupted.

Furthermore, our protocols achieve {\em detection} in case of failure,
i.e., if at most t players are corrupted then broadcast is achieved,
and if at most t^+ players are corrupted then broadcast is achieved or
every player learns that the protocol failed. This protocol can be
employed in the precomputation of a secure multi-party computation
protocol, resulting in {\em detectable multi-party computation}, where up
to t corruptions can be tolerated and up to t^+ corruptions can
either be tolerated or detected in the precomputation, for any t,t^+
with t+2t^+<n.

ePrint: https://eprint.iacr.org/2002/053

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .