Paper 2022/698

State Machine Replication under Changing Network Conditions

Andreea B. Alexandru, University of Maryland, College Park
Erica Blum, University of Maryland, College Park
Jonathan Katz, University of Maryland, College Park
Julian Loss, CISPA Helmholtz Center for Information Security

Protocols for state machine replication (SMR) are typically 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 the 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 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 maintained. We show that purely asynchronous proactive secret sharing is impossible without some form of synchronization between the parties, ruling out a natural approach to proactively secure network-agnostic SMR protocols. 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 even under arbitrarily changing network conditions.

Note: Full version of paper appearing at ASIACRYPT 2022.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
State machine replicationConsensusProactive Security
Contact author(s)
aandreea @ umd edu
erblum @ umd edu
jkatz2 @ gmail com
lossjulian @ gmail com
2023-05-07: last of 2 revisions
2022-06-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andreea B. Alexandru and Erica Blum and Jonathan Katz and Julian Loss},
      title = {State Machine Replication under Changing Network Conditions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/698},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.