Synchronous Byzantine Agreement with Expected O(1) Rounds, Expected $$O(n^2)$$ Communication, and Optimal Resilience

Conference Paper

We present new protocols for Byzantine agreement in the synchronous and authenticated setting, tolerating the optimal number of f faults among parties. Our protocols achieve an expected O(1) round complexity and an expected communication complexity. The exact round complexity in expectation is 10 for a static adversary and 16 for a strongly rushing adaptive adversary. For comparison, previous protocols in the same setting require expected 29 rounds.

Full Text

Duke Authors

Cited Authors

  • Abraham, I; Devadas, S; Dolev, D; Nayak, K; Ren, L

Published Date

  • January 1, 2019

Published In

Volume / Issue

  • 11598 LNCS /

Start / End Page

  • 320 - 334

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783030321000

Digital Object Identifier (DOI)

  • 10.1007/978-3-030-32101-7_20

Citation Source

  • Scopus