Paper 2018/1079

Analysis of Deterministic Longest-Chain Protocols

Elaine Shi

Abstract

Most classical consensus protocols rely on a leader to coordinate nodes’ voting efforts. One novel idea that stems from blockchain-style consensus is to rely, instead, on a “longest-chain” idea for such coordination. Such a longest-chain idea was initially considered in randomized protocols, where in each round, a node has some probability of being elected a leader who can propose the next block. Recently, well-known systems have started implementing the deterministic counterpart of such longest-chain protocols — the deterministic counterpart is especially attractive since it is even simpler to implement than their randomized cousins. A notable instantiation is the Aura protocol which is shipped with Parity’s open-source Ethereum implementation. Interestingly, mathematical analyses of deterministic, longest-chain protocols are lacking even though there exist several analyses of randomized versions. In this paper, we provide the first formal analysis of deterministic, longest-chain-style consensus. We show that a variant of the Aura protocol can defend against a Byzantine adversary that controls fewer than 1/3 fraction of the nodes, and this resilience parameter is tight by some technical interpretation. Based on insights gained through our mathematical treatment, we point out that Aura’s concrete instantiation actually fails to achieve the resiliene level they claim. Finally, while our tight proof for the longest-chain protocol is rather involved and non-trivial; we show that a variant of the “longest-chain” idea which we call “largest-set” enables a textbook construction that admits a simple proof (albeit with slower confirmation).

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. MINOR revision.CSF 2019
Keywords
blockchainlongest-chain protocolsconsensusByzantine Fault Tolerance
Contact author(s)
runting @ gmail com
History
2019-05-01: revised
2018-11-09: received
See all versions
Short URL
https://ia.cr/2018/1079
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1079,
      author = {Elaine Shi},
      title = {Analysis of Deterministic Longest-Chain Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1079},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1079}},
      url = {https://eprint.iacr.org/2018/1079}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.