Common Contracts

Matthias Fitzi and Ueli Maurer Department of Computer Science

June 28th, 2024

• Filed
  June 28th, 2024

Abstract. This paper presents protocols for Byzantine agreement, i.e. for reliable broadcast, among a set of n players, some of which may be controlled by an adversary. It is well-known that Byzantine agreement is possible if and only if the number of cheaters is less than n=3. In this paper we consider a general adversary that is speci ed by a set of subsets of the player set (the adversary structure), and any one of these subsets may be corrupted by the adversary. The only condition we need is that no three of these subsets cover the full player set. A result of Hirt and Maurer implies that this condition is necessary and su cient for the existence of a Byzantine agreement protocol, but the complexity of their protocols is generally exponential in the number of players. The purpose of this paper is to present the rst protocol with polynomial message and computation complexity for any (even exponentially large) speci cation of the adversary structure. This closes a gap in a recent res