Byzantine Fault Tolerance on General Hybrid Adversary Structures
Klaus Kursawe, Felix C. Freiling
Adversary structures are a generalization of the classical ``at most
t-out-of-n'' threshold failure model which is used in many published
Byzantine-tolerant protocols. An adversary structure basically lists all
coalitions of parties whose corruption the protocol should tolerate. Using
adversary structures it is possible to encode dependent failure models,
such as ``either all Linux machines fail or all Windows machines but not
both at the same time''. We describe a general technique that allows to
transform an algorithm designed for the threshold model into an algorithm
that works for general adversary structures. Our technique is based
on several (partly informal) rules which describe how the algorithm
and its proof must be augmented so that general adversary structures
can be tolerated. We demonstrate the applicability of our approach
by transforming an asynchronous Byzantine-tolerant reliable broadcast
protocol into one that tolerates Byzantine adversary structures. We also
consider similar transformations for hybrid failures (combinations of
different fault models) and discuss ways to map adversary structures to
the real world and manage them efficiently.