1. Synchronous Byzantine Agreement with Expected O(1) Rounds, Expected O(n2) Communication, and Optimal Resilience 2019 FinancialCryptography
    Ittai Abraham, Srinivas Devadas, Danny Dolev, Kartik Nayak, and Ling Ren
    [View PDF on eprint.iacr.org]
    [Show BibTex Citation]

    @misc{cryptoeprint:2018:1028,
    author = {Ittai Abraham and Srinivas Devadas and Danny Dolev and Kartik Nayak and Ling Ren},
    title = {Synchronous Byzantine Agreement with Expected $O(1)$ Rounds, Expected $O(n^2)$ Communication, and Optimal Resilience},
    howpublished = {Cryptology ePrint Archive, Report 2018/1028},
    year = {2018},
    note = {\url{https://eprint.iacr.org/2018/1028}},
    }

We present new protocols for Byzantine agreement in the synchronous and authenticated setting, tolerating the optimal number of f faults among n=2f+1 parties. Our protocols achieve an expected O(1) round complexity and an expected O(n2) 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.

  1.