Source-linked AI summary
Fully Fluctuating Sleepy Consensus from Minimal Assumptions
Javier Nieto, Yuval Efron, Joachim Neu, Ling Ren
TL;DR
Fully fluctuating participation raises whether sleepy consensus can avoid PoW, VDFs, and hardware assumptions. This paper answers yes with a PKI-, VRF-, and graded-wakeness-based protocol, extending it to uncorruption while leaving practical optimization open.
Problem
The paper asks whether consensus under fully fluctuating participation can be achieved without hardware assumptions such as PoW or VDFs.
Method
The protocol uses only PKI and VRFs, with graded wakeness implemented through interactive challenge-response to support agreement under fluctuating participation.
Results
The paper presents consensus secure under fully fluctuating participation and extends the protocol to uncorruption with a mild additional VRF unpredictability assumption for liveness.
Takeaways & Limitations
Fully fluctuating sleepy consensus is feasible without PoW, VDFs, or hardware assumptions, using PKI and VRFs.
Takeaways & Limitations
The work focuses on feasibility and leaves latency, round complexity, and message complexity optimization for future work.
Abstract
from arXiv · showhide
Bitcoin's proof-of-work (PoW)-based protocol is remarkable for how little it asks of its participants. Not only can miners take breaks from work whenever they please, but it is almost unique in offering a path of contrition: corrupt miners can reclaim honest status simply by resuming mining on the longest chain. The protocol only requires that honest miners hold the majority of computational power at any given time. Analogous proof-of-stake (PoS) protocols, usually formalized via the sleepy model of Pass and Shi (2017), have fallen short of matching this robustness. In fact, sleepy consensus protocols in the plain PKI model must heavily restrict fluctuations in adversarial participation over time. The recent work of Efron, Neu, and Pitassi (2025) enables fully fluctuating participation in the sleepy model by introducing the external adversary model. Their protocol, however, relies on verifiable delay functions (VDFs), a strong cryptographic primitive that somewhat resembles PoW, by assuming that the adversary cannot compute sequential work significantly faster than honest nodes. In this work, we design a sleepy consensus protocol for fully fluctuating participation with an external adversary under an honest majority, from minimal assumptions: a public key infrastructure (PKI) and a verifiable random function (VRF). In particular, we make no VDF or hardware assumptions. Our key technique is graded wakeness, a novel primitive that allows nodes to form consistent opinions on which other nodes are awake. We further extend our protocol to handle uncorruption, where corrupt nodes return to honesty. This extension requires only a mild additional assumption on the unpredictability of VRF outputs for liveness.
1 Introduction
The paper asks whether consensus with fully fluctuating participation can avoid PoW, VDFs, and other hardware assumptions, and answers affirmatively using PKI, VRFs, and graded wakeness. It extends the model to uncorruption, while leaving practical protocol optimization for future work.
- Motivation: Fully fluctuating participation allows honest and adversarial nodes alike to alternate between participation and breaks.The model captures the flexibility observed in Bitcoin, where participation can rise or decline and corrupt miners may also stop working.
- Motivation: Prior external-adversary consensus achieves fully fluctuating participation with VDFs, leaving open whether hardware assumptions are necessary.VDFs are described as proofs of sequential work whose speed is assumed comparable across honest and adversarial nodes.
- Contribution: The protocol answers this question using only a PKI and a VRF, without PoW, VDFs, or hardware assumptions.The paper presents this as a consensus protocol secure under fully fluctuating participation.
- Model: The external adversary model prevents the adversary from indefinitely impersonating corrupt nodes because cryptographic secrets remain external to the protocol.This supports breaks and uncorruption, unlike the conventional model in which the adversary obtains corrupt nodes’ private signing keys.
- Technical approach: Graded wakeness uses interactive challenge-response to let nodes form consistent opinions about which other nodes are participating.Fresh nonces prevent pre-signing, while multiple rounds provide transferable evidence and support graded agreement.
- Limitations: The work establishes feasibility but leaves latency, round complexity, and message complexity optimization for future work.The paper’s stated focus is showing that PoW and VDFs are not required for consensus with fully fluctuating participation.
2 Model Preliminaries
The model formalizes consensus with synchronous communication while an adversary controls communication, sleepiness, and corruption over a predefined participant set. It defines stability and admissible schedules to capture recovery, sustained participation, fluctuations, and possible uncorruption.
- Nodes: The permissioned model has a predefined set P of n nodes and a PPT adversary controlling communication, sleepiness, and corruption.The model assumes a PKI with every node’s public key known to all others.
- Communication: Communication is synchronous in lock-step rounds, with honest nodes receiving messages sent in any prior round.The formulation notes that consensus with sleepy nodes is impossible under partial synchrony.
- Sleepiness: Sleepy nodes do not send, receive, or execute protocol steps, and the adversary puts nodes to sleep only at round boundaries.Awake nodes in round t are represented by W_t.
- Corruption: The corruption set may evolve adaptively, with the immobile case restricting corruption growth and the mobile case allowing previously corrupt nodes to become honest.Uncorruption resets a node’s protocol state, leaves it asleep, and makes it behave as if waking for the first time.
- Schedules: Schedules specify awake and corrupt nodes each round, while H_t ∩ W_t captures nodes honest and awake throughout an interval.The model uses these interval sets to characterize participation stability.
- Stability: A node is t-stable when it remains honest and awake through t+T_s, and t-very-stable when it also remained so throughout the preceding T_r rounds.T_r models recovery from sleep, while T_s captures the sustained period needed to count toward the honest set.
3 Consensus in the Fully Fluctuating Sleepy Model
The protocol builds consensus for fully fluctuating sleepy participation from graded wakeness and graded agreement, culminating in a Byzantine agreement protocol with stated safety, validity, liveness, and totality guarantees.
- 3.3 Byzantine Agreement: The Byzantine agreement protocol uses sequential views, each invoking three-grade graded agreement, and achieves safety, validity, liveness, and totality in the specified model.The protocol’s theorem covers (Tr = 13, Ts = 13, ρ = 1), while the supporting lemmas establish output validity, agreement, eventual output, and propagation across later views.
- 3.1 Graded Wakeness: Graded wakeness lets nodes form nested views of which nodes are awake, with graded delivery, asleep exclusion, and all-or-nothing honest inclusion.Three grades support forwarding across multiple rounds while excluding nodes asleep at the protocol start.
- 3.1 Graded Wakeness: The GW3 protocol exchanges nonce challenges and acknowledgments, then outputs graded wakeness sets after forwarding and acknowledgment rounds.Nodes sample nonce challenges, forward them for two rounds, acknowledge them in round 3, and output grades from round 4 onward.
- 3.2 Graded Agreement: Two-grade graded agreement satisfies graded delivery, consistency, validity, and integrity under very-stable input when Ts ≥6 and ρ ≥1.Theorem 15 applies to schedules admissible in the fully fluctuating sleepy model with gmax = 2.
4 Consensus in the Fully Fluctuating Sleepy Model with Uncorruption
Uncorruption creates challenges for distinguishing fresh messages and preserving leader-election liveness. The protocol addresses these with value-bound nonce acknowledgments and an unpredictability assumption on VRF outputs.
- Challenge 1: Pre-Signed Equivocation: Uncorruption can make honest nodes appear equivocating because previously corrupt nodes may have pre-signed input messages.This undermines validity and can prevent a majority from forming for one input.
- Challenge 1: Pre-Signed Equivocation: Graded wakeness resolves pre-signed equivocation by attaching values to nonce acknowledgments and counting messages only for freshly acknowledged values.A pre-signed input lacks a fresh nonce acknowledgment, so it counts neither as input nor as equivocation evidence.
- Challenge 2: Biased Leader Election: Uncorruption lets the adversary pre-compute VRF outputs for every node, potentially predicting every leader election and preventing liveness.The issue arises because nodes can be corrupted and later uncorrupted before elections.
- Challenge 2: Biased Leader Election: A node is unpredictable for view v when it is 13(v −1)-stable and has not queried the VRF oracle for v before round 13(v −1).The adversary then cannot know whether that node will win the election.
- Guarantee: Theorem 28 establishes Byzantine agreement for admissible fully fluctuating sleepy schedules having at least nλ views with an unpredictable node.Liveness follows because, except with negligible probability, an unpredictable node eventually has the highest VRF output.
5 Related Work
Related work studies sleepy participation, reconfiguration, player replaceability, churn, and mobile Byzantine faults, but these settings differ in their treatment of participation and corruption changes.
- Sleepy Consensus: The original sleepy model assumes a fixed corrupt set, while later variants allow corruption to grow but not shrink.These later protocols therefore do not support fully fluctuating participation.
- Sleepy Consensus: The external adversary model enables fully fluctuating participation, with recent protocols using VDFs to achieve consensus.This work’s related-work context distinguishes those approaches from protocols without hardware assumptions.
- Reconfiguration: Reconfiguration changes which nodes may participate, whereas the sleepy model allows the participating subset to fluctuate within a static membership set.The two dimensions are orthogonal, although some works consider both.
- Player Replaceability: Algorand uses VRF-based sortition and player replaceability but assumes a fixed threshold of honest, awake nodes and does not tolerate adversarially controlled sleepiness.Its requirement is closer to traditional models with a super-majority of honest and awake nodes.
- Other Fault Models: Mixed fault models combine crash and Byzantine faults but do not allow a majority of nodes to crash, while churn-based storage primitives require a known churn threshold.These restrictions differ from arbitrary participation changes in the sleepy setting.
- Mobile Byzantine Faults: Mobile Byzantine fault models study corruption moving between nodes, distinguishing constrained from unconstrained mobility and whether cured nodes detect prior corruption.These dimensions concern corruption mobility rather than sleepy participation alone.
6 Conclusion
The paper presents consensus for fully fluctuating sleepy participation without PoW or VDF hardware assumptions. Its approach uses graded wakeness and extends to uncorruption with an additional mild assumption.
- Conclusion: The protocol achieves consensus in the fully fluctuating sleepy model without hardware assumptions such as PoW or VDFs.The construction assumes cryptographic tools rather than a hardware-bound resource.
- Conclusion: Graded wakeness is implemented through several rounds of a simple interactive challenge-response protocol.It upgrades graded agreement to tolerate fully fluctuating participation.
- Conclusion: Without uncorruption, the agreement protocol requires no additional assumption; with uncorruption, it requires a minor protocol change and an additional mild assumption.The paper leaves round and message complexity optimization for future work.