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

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

doi:10.1007/978-3-030-32101-7_20

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

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	Financial Cryptography and Data Security - 23rd International Conference, FC 2019, Revised Selected Papers
Editors	Ian Goldberg, Tyler Moore
Publisher	Springer
Pages	320-334
Number of pages	15
ISBN (Print)	9783030321000
DOIs	https://doi.org/10.1007/978-3-030-32101-7_20
State	Published - 2019
Event	23rd International Conference on Financial Cryptography and Data Security, FC 2019 - St. Kitts, Saint Kitts and Nevis Duration: Feb 18 2019 → Feb 22 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11598 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	23rd International Conference on Financial Cryptography and Data Security, FC 2019
Country/Territory	Saint Kitts and Nevis
City	St. Kitts
Period	2/18/19 → 2/22/19

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

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

Library availability

Discover UIUC Full Text

Cite this

Abraham, I., Devadas, S., Dolev, D., Nayak, K., & Ren, L. (2019). Synchronous Byzantine Agreement with Expected O(1) Rounds, Expected $$O(n^2)$$ Communication, and Optimal Resilience. In I. Goldberg, & T. Moore (Eds.), Financial Cryptography and Data Security - 23rd International Conference, FC 2019, Revised Selected Papers (pp. 320-334). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11598 LNCS). Springer. https://doi.org/10.1007/978-3-030-32101-7_20

Synchronous Byzantine Agreement with Expected O(1) Rounds, Expected $$O(n^2)$$ Communication, and Optimal Resilience. / Abraham, Ittai; Devadas, Srinivas; Dolev, Danny et al.
Financial Cryptography and Data Security - 23rd International Conference, FC 2019, Revised Selected Papers. ed. / Ian Goldberg; Tyler Moore. Springer, 2019. p. 320-334 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11598 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abraham, I, Devadas, S, Dolev, D, Nayak, K & Ren, L 2019, Synchronous Byzantine Agreement with Expected O(1) Rounds, Expected $$O(n^2)$$ Communication, and Optimal Resilience. in I Goldberg & T Moore (eds), Financial Cryptography and Data Security - 23rd International Conference, FC 2019, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11598 LNCS, Springer, pp. 320-334, 23rd International Conference on Financial Cryptography and Data Security, FC 2019, St. Kitts, Saint Kitts and Nevis, 2/18/19. https://doi.org/10.1007/978-3-030-32101-7_20

Abraham I, Devadas S, Dolev D, Nayak K, Ren L. Synchronous Byzantine Agreement with Expected O(1) Rounds, Expected $$O(n^2)$$ Communication, and Optimal Resilience. In Goldberg I, Moore T, editors, Financial Cryptography and Data Security - 23rd International Conference, FC 2019, Revised Selected Papers. Springer. 2019. p. 320-334. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-32101-7_20

Abraham, Ittai ; Devadas, Srinivas ; Dolev, Danny et al. / Synchronous Byzantine Agreement with Expected O(1) Rounds, Expected $$O(n^2)$$ Communication, and Optimal Resilience. Financial Cryptography and Data Security - 23rd International Conference, FC 2019, Revised Selected Papers. editor / Ian Goldberg ; Tyler Moore. Springer, 2019. pp. 320-334 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{196373ce5b774093a8438affeb4c123d,

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

abstract = "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.",

author = "Ittai Abraham and Srinivas Devadas and Danny Dolev and Kartik Nayak and Ling Ren",

note = "Publisher Copyright: {\textcopyright} 2019, International Financial Cryptography Association.; 23rd International Conference on Financial Cryptography and Data Security, FC 2019 ; Conference date: 18-02-2019 Through 22-02-2019",

year = "2019",

doi = "10.1007/978-3-030-32101-7_20",

language = "English (US)",

isbn = "9783030321000",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "320--334",

editor = "Ian Goldberg and Tyler Moore",

booktitle = "Financial Cryptography and Data Security - 23rd International Conference, FC 2019, Revised Selected Papers",

address = "Germany",

}

TY - GEN

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

AU - Abraham, Ittai

AU - Devadas, Srinivas

AU - Dolev, Danny

AU - Nayak, Kartik

AU - Ren, Ling

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85075582597&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85075582597&partnerID=8YFLogxK

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

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

M3 - Conference contribution

AN - SCOPUS:85075582597

SN - 9783030321000

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 320

EP - 334

BT - Financial Cryptography and Data Security - 23rd International Conference, FC 2019, Revised Selected Papers

A2 - Goldberg, Ian

A2 - Moore, Tyler

PB - Springer

T2 - 23rd International Conference on Financial Cryptography and Data Security, FC 2019

Y2 - 18 February 2019 through 22 February 2019

ER -

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

Abstract

Publication series

Conference

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this