Paper 2018/060

A Simple Reduction from State Machine Replication to Binary Agreement in Partially Synchronous or Asynchronous Networks

Abhinav Aggarwal and Yue Guo

Abstract

The recent advent of blockchains has spurred a huge interest in the research and development of numerous cryptocurrencies as well as understanding the fundamental concepts that underly this technology. At the heart of this design is the classic state machine replication protocol in which a group of n machines (out of which f are Byzantine) want to agree on an ever-growing log of transactions. In this paper, we present a simple black box reduction from state machine replication (SMR) to the classical binary agreement (BA) protocol on top of a fully decentralized network. We consider both synchronous and partially synchronous/asynchronous settings for our reduction. We also present an algorithm for a reduction from BA to SMR, thus establishing an equivalence between the two. In each of these settings, we analyze our algorithms with respect to the required security properties. Although there is prior work that establishes these reductions, our solutions are simpler (at the cost of efficiency) and useful from a pedagogical point of view.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Contact author(s)
abhiag6891 @ gmail com
History
2018-01-16: received
Short URL
https://ia.cr/2018/060
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/060,
      author = {Abhinav Aggarwal and Yue Guo},
      title = {A Simple Reduction from State Machine Replication to Binary Agreement in Partially Synchronous or Asynchronous Networks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/060},
      year = {2018},
      url = {https://eprint.iacr.org/2018/060}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.