U.S. flag   An unofficial archive of your favorite United States government website
Dot gov

Official websites do not use .rip
We are an unofficial archive, replace .rip by .gov in the URL to access the official website. Access our document index here.

Https

We are building a provable archive!
A lock (Dot gov) or https:// don't prove our archive is authentic, only that you securely accessed it. Note that we are working to fix that :)

NISTIR 8460 (Draft)

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.

Abstract

Keywords

atomic broadcast; Bitcoin; blockchain; Byzantine Fault Tolerance; consensus; cryptocurrency; distributed ledger technology; Ethereum; state machine replication
Control Families

None selected

Documentation

Publication:
NISTIR 8460 (Draft) (DOI)
Local Download

Supplemental Material:
None available

Document History:
04/26/23: NISTIR 8460 (Draft)

Topics

Security and Privacy
general security & privacy

Technologies
blockchain

Applications
mathematics