Paper 2023/1507

Efficient Agreement Over Byzantine Gossip

Ran Cohen, Reichman University
Julian Loss, CISPA Helmholtz Center for Information Security
Tal Moran, Reichman University

Byzantine agreement (BA) asks for a set of parties to reach agreement in an adversarial setting. A central question is how to construct efficient BA protocols that scale well with the number of parties. In particular, the communication complexity is a critical barrier for large-scale implementations. State-of-the-art, scalable BA protocols typically work by sampling a small, unpredictable committee of parties that will send messages in each round. These messages must reach all honest parties, to allow the next round's committee to function. In practice, this is usually accomplished by propagating messages over a gossip network, implemented over a partial communication graph. Most formulations of gossip networks have an ideal guarantee that every message delivered to any honest party will be delivered to every other honest party. Unfortunately, realizing this guarantee necessarily makes the protocol vulnerable to denial-of-service attacks, since an adversary can flood the network with many messages that the protocol must deliver to all parties. In this paper, we make several contributions towards realizing the goal of efficient, scalable byzantine agreement over a gossip network: 1. We define ``gossip with abort,'' a relaxed gossip model that can be efficiently realized with minor modifications to existing gossip protocols, yet allows for significant savings in communication compared to the full point-to-point model. 2. Our protocols work in a graded PKI model, in which honest parties only have partial agreement about the set of participants in the protocol. This model arises naturally in settings without trusted setup, such as the ``permissionless'' setting underlying many blockchain protocols. 3. We construct a new, player-replaceable BA protocol in the graded PKI model. The concrete communication complexity of our protocol, for typical parameter values, is more than 25 times better than the current state-of-the-art BA protocols in the honest-majority setting.

Available format(s)
Cryptographic protocols
Publication info
byzantine agreementpermissionlessgossipgraded pkiblockchain
Contact author(s)
cohenran @ runi ac il
lossjulian @ gmail com
talm @ runi ac il
2023-10-03: approved
2023-10-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ran Cohen and Julian Loss and Tal Moran},
      title = {Efficient Agreement Over Byzantine Gossip},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1507},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.