Byzantine Agreement Secure Against General Adversaries in the Dual Failure Model

Bernd Altmann, Matthias Fitzi, and Ueli Maurer

International Symposium on Distributed Computing — DISC '99, Lecture Notes in Computer Science, Springer-Verlag, vol. 1693, pp. 123–137, Sep 1999.

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} \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 $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},
}