[Resource Topic] 2022/698: State Machine Replication under Changing Network Conditions

Welcome to the resource topic for 2022/698

State Machine Replication under Changing Network Conditions

Authors: Andreea B. Alexandru, Erica Blum, Jonathan Katz, and Julian Loss


Protocols for state machine replication (SMR) are typically differently designed for synchronous or asynchronous networks, with a lower corruption threshold in the latter case. Recent network-agnostic protocols are secure when run in either a synchronous or an asynchronous network. We propose two new constructions of network-agnostic SMR protocols that improve on existing protocols in terms of either adversarial model or communication complexity: 1. an adaptively secure protocol with optimal corruption thresholds and quadratic amortized communication complexity per transaction; 2. a statically secure protocol with near-optimal corruption thresholds and linear amortized communication complexity per transaction. We further explore efficient SMR protocols run in a network that may change between synchronous and asynchronous arbitrarily often; parties can be uncorrupted (as in the proactive model), and the protocol should remain secure as long as the appropriate corruption thresholds are always maintained. We show that proactively secure SMR using threshold cryptography is impossible without some form of synchronization between the parties. Motivated by this negative result, we consider a model where the adversary is limited in the total number of parties it can corrupt over the duration of the protocol and show, in this setting, that our SMR protocols remain secure under arbitrarily changing network conditions.

ePrint: https://eprint.iacr.org/2022/698

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .