Paper 2018/377

ALGORAND AGREEMENT: Super Fast and Partition Resilient Byzantine Agreement

Jing Chen, Sergey Gorbunov, Silvio Micali, and Georgios Vlachos

Abstract

We present a simple Byzantine agreement protocol with leader election, that works under > 2/3 honest majority and does not rely on the participants having synchronized clocks. When honest messages are delivered within a bounded worst-case delay, agreement is reached in expected constant number of steps when the elected leader is malicious, and is reached after two steps when the elected leader is honest. Our protocol is resilient to arbitrary network partitions with unknown length, and recovers fast after the partition is resolved and bounded message delay is restored. We will briefly discuss how the protocol applies to blockchains in a permissionless system. In particular, when an honest leader proposes a block of transactions, the first voting step happens in parallel with the block propagation. Effectively, after the block propagates, a certificate is generated in just one step of voting.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
blockchainproof-of-stakeconsensusByzantine agreement
Contact author(s)
georgios @ algorand com
History
2018-05-01: revised
2018-04-30: received
See all versions
Short URL
https://ia.cr/2018/377
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/377,
      author = {Jing Chen and Sergey Gorbunov and Silvio Micali and Georgios Vlachos},
      title = {ALGORAND AGREEMENT: Super Fast and Partition Resilient Byzantine Agreement},
      howpublished = {Cryptology ePrint Archive, Paper 2018/377},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/377}},
      url = {https://eprint.iacr.org/2018/377}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.