  Byzantine fault-tolerant consensus protocols have provable safety and
liveness properties for static validator sets. In practice, however, the
validator set changes over time, potentially eroding the protocol's security
guarantees. For example, systems with accountable safety may lose some of that
accountability over time as adversarial validators exit. As a result, protocols
must rate limit entry and exit so that the set changes slowly enough to ensure
security. Here, the system designer faces a fundamental trade-off. Slower exits
increase friction, making it less attractive to stake in the first place.
Faster exits provide more utility to stakers but weaken the protocol's
security.
  This paper provides the first systematic study of exit queues for
Proof-of-Stake blockchains. Given a collection of validator-set consistency
constraints imposed by the protocol, the social planner's goal is to provide a
constrained-optimal mechanism that minimizes disutility for the participants.
We introduce the MINSLACK mechanism, a dynamic capacity first-come-first-served
queue in which the amount of stake that can exit in a period depends on the
number of previous exits and the consistency constraints. We show that MINSLACK
is optimal when stakers equally value the processing of their withdrawal. When
stakers values are heterogeneous, the optimal mechanism resembles a priority
queue with dynamic capacity. However, this mechanism must reserve exit capacity
for the future in case a staker with a much higher need for liquidity arrives.
We conclude with a survey of known consistency constraints and highlight the
diversity of existing exit mechanisms.
