Cryptology ePrint Archive: Report 2018/1028

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

Ittai Abraham and Srinivas Devadas and Danny Dolev and Kartik Nayak and Ling Ren

Abstract: 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(n^2)$ 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.

Category / Keywords:

Original Publication (with minor differences): Financial Cryptography and Data Security 2019

Date: received 22 Oct 2018, last revised 5 Mar 2019

Contact author: renling8 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190306:054018 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]