Byzantine Agreement Secure Against General Adversaries in the Dual Failure Model
Bernd Altmann, Matthias Fitzi, and Ueli Maurer
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 ${\mathcal Z}$ of pairs $(A,F)$ of subsets of $P$ where the adversary may select an arbitrary such pair $(A_i,F_i)$ from ${\mathcal 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 ${\mathcal 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 ${\mathcal Z}$ we have $A_i\cup A_j\cup A_k\cup (F_i\cap F_j\cap F_k)=P$. Achievability is demonstrated by efficient protocols. Moreover, for a slightly stronger condition on ${\mathcal 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 protocols that are substantially more efficient than all previous protocols for these two settings.
Key words: Broadcast, Byzantine agreement, unconditional security, active adversary, fail-corruption.
BibTeX Citation
@inproceedings{AlFiMa99,
author = {Bernd Altmann and Matthias Fitzi and Ueli Maurer},
title = {{B}yzantine Agreement Secure Against General Adversaries in the Dual Failure Model},
editor = {Prasad Jayanti},
booktitle = {International Symposium on Distributed Computing --- DISC~'99},
pages = 123--137,
series = {Lecture Notes in Computer Science},
volume = 1693,
year = 1999,
month = 9,
publisher = {Springer-Verlag},
}