This paper introduces a new adversary model for Byzantine agreement and broadcast among a set
P of players in which the adversary may perform two different types of player corruption: active (Byzantine) corruption and
fail-corruption (crash). As a strict generalization of the results of Garay and Perry, who proved tight bounds on the maximal
number of actively and fail-corrupted players, the adversary’s capability is characterized by a set
Z of pairs (
A,F) of subsets of
P where the adversary may select an arbitrary such pair (
A
i
,
F
i
) from
Z and corrupt the players in
A
i
actively and fail-corrupt the players in
F
i
.
For this model we prove that the exact condition on Z for which perfectly secure agreement and broadcast are achievable is that for no three pairs (A
i
,F
i
),(A
j
,F
j
), and (A
k
,F
k
) in Z we have A
i
∪A
j
∪A
k
∪(F
i
∩F
j
∩F
j
) = P. Achievability is demonstrated by efficient protocols. Moreover, for a slightly stronger condition on Z, which covers the previous mixed (active and fail-corruption) threshold condition and the previous purely-active non-threshold
condition, we demonstrate agreement and broadcast pro- tocols that are substantially more efficient than all previous protocols
for these two settings.
Keywords Broadcast - Byzantine agreement - unconditional security - active adversary - fail-corruption
Abstract Research supported by the Swiss National Science Foundation (SNF), SPP project no. 5003-045293