State Machine Replication and Consensus with Byzantine Adversaries

Date Published: April 26, 2023
Comments Due: September 1, 2023
Email Comments to: ir8460-comments@nist.gov

Author(s)

Michael Davidson (NIST)

Announcement

Most applications on the internet are run by centralized service providers that are a single point of failure: if the provider crashes or is malicious, users may lose access to the application, or it may return erroneous or inconsistent results. Consensus algorithms and state machine replication enable a set of mutually distrusting parties to emulate a centralized service in a fault-tolerant and distributed manner. Although the study of these algorithms began in the 1980s, research has accelerated dramatically since the advent of Bitcoin in 2008.

This document provides a survey on consensus algorithms, state machine replication, and distributed ledger technology for readers who already possess a high-level understanding of distributed ledgers, such as that provided by NIST IR 8202, Blockchain Technology Overview. After introducing the properties of these systems, the models they operate in, and the subprotocols used to implement them, this document provides a detailed look at many of the most prominent permissioned and permissionless algorithms in the literature with a focus on performance and security considerations. Finally, a variety of related topics are discussed, including state machine design, interoperability, scalability mechanisms such as sharding and "layer 2" technologies, and how incentives can impact system security.

Control Families

None selected