Generalized Communication and Security Models in Byzantine Agreement
Matthias Fitzi
Byzantine agreement (BA) is a primitive of fundamental importance for fault-tolerant distributed computing and cryptographic protocols. BA among a set of $n$ players allows them to reach agreement about a value even if some of the players are malicious and try to prevent agreement among the non-faulty players by distributing false information.
Since the initial statement of the BA problem, a small number of widely accepted standard models have established, distinguishing between aspects such as what means of communication are given among the players or how powerful the faulty players are. Both in research on Byzantine agreement and its applications, these standard models are obstinately followed.
Besides a selective overview on some standard models in Byzantine agreement, this thesis gives a broader view on the problem by considering natural generalizations of these models and generalizations of the problem definition itself. Thereby the main focus is on synchronous networks and active adversaries. It turns out that some of these generalizations, without restricting the adversarial power, allow for BA protocols that achieve a level of security that is provably unachievable in their corresponding standard models. The main contributions are described in the following paragraphs whereby $n$ denotes the number of players and $t$ the number of cheaters among the players.
Security. Standard BA provides either unconditional or computational security. Unconditionally secure protocols for BA are provably secure but can only tolerate a relatively small number of cheaters, typically $t<n/3$. Computationally secure ones often tolerate any number of cheaters, $t<n$, but their security is based on unproven intractability assumptions. So far, every previous computationally secure protocol from the literature has the property that, in case its underlying intractability assumption is false, it does not withstand one single cheater, $t=0$. In contrast, we show that computational and unconditional security can be combined by presenting protocols computationally secure against some large number $t_1$ of cheaters but, at the same time, still unconditionally secure against some smaller number $t_0>0$ of cheaters. It is shown that BA of this flavor is achievable if and only if $2t_0+t_1<n$ and $t_1\geq t_0$.
Communication. Standard communication models assume either pairwise authenticated or pairwise secure channels among the players. In these models, unconditional BA is achievable if and only if $t<n/3$. A natural generalization of these models is to assume partial broadcast among the players to be possible, i.e., that for some number $b\geq2$, broadcast is achievable among each set of $b$ players. It is shown that for any $b$, $2\leq b\leq n$, BA is achievable if and only if $t<\frac{b-1}{b+1}n$.
New threshold paradigm. The security of standard BA is defined with respect to one threshold $t$ meaning that BA is achieved in the presence of up to $f\leq t$ cheaters but that no security is guaranteed at all if $f>t$. In particular, unconditionally secure protocols are completely insecure in the presence of $f\geq n/3>t$ cheaters. However, in reality, nothing would really guarantee that $f\leq t$ and thus the usefulness of non-fully resilient protocols is questionable. Preferably, a non-fully resilient protocol should guarantee BA for some threshold $t$ — but in case that more than $t$ players are cheating, $f>t$, and BA cannot be achieved, it should be guaranteed that all players safely abort the protocol in unison. We show that this is possible if and only if $t=0$. More generally, we introduce the notion of two-threshold BA, involving two different thresholds $t_v$ and $t_c$: if at most $t_v$ players cheat then the “validity condition” of BA is achieved and, if at most $t_c$ players cheat then the “consistency condition” of BA is achieved. We show that two-threshold BA is achievable if and only if both $t_v+2t_c<n$ and $2t_v+t_c<n$, or $t_v=0$, or $t_c=0$.
BibTeX Citation
@phdthesis{Fitzi03,
author = {Matthias Fitzi},
title = {Generalized Communication and Security Models in {B}yzantine Agreement},
year = {2003},
month = {3},
note = {Reprint as vol.~4 of {ETH Series in Information Security and Cryptography}, {ISBN} 3-89649-853-3, {H}artung-{G}orre {V}erlag, {K}onstanz, 2003},
school = {{ETH Zurich}},
}