# Generalized Communication and Security Models in {B}yzantine 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 wide\-ly accepted standard models have
established, distinguishing between as\-pects 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 where\-by $n$ denotes the number of players
and $t$ the number of cheaters among the players.

\paragraph{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$.

\paragraph{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$.

\paragraph{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 $\tval$ and $\tcons$:
if at most $\tval$ players cheat then the ``validity condition'' of BA is achieved
and, if at most $\tcons$ players cheat then the ``consistency condition'' of BA is
achieved. We show that two-threshold BA is achievable if and only if both
$\tval+2\tcons<n$ and $2\tval+\tcons<n$, or $\tval=0$, or $\tcons=0$.