CS Paper Radar

Fully Fluctuating Sleepy Consensus from Minimal Assumptions

Javier Nieto, Yuval Efron, Joachim Neu, Ling Ren

cs.DC ·submitted 2026-09-02 18:36 UTC · v1
published

Abstract

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.

DOI
10.4230/LIPIcs.DISC.2026.44

Closest papers

Nearest neighbours by meaning across the whole index.

PoVD: Efficient Consensus Protocol based on Verifiable Delay Function

cs.DC ·2026-09-18 ·Rui Jiang, Xintong Ling, Bin Cao, Jiaheng Wang, Xiqi Gao +1 more
similarity 0.67
Abstract

Consensus protocols ensure the robustness and scalability of blockchains and decentralized applications built on them. However, existing consensus mechanisms often impose high computational cost or require heavy communication overhead. To address these challenges, we propose proof of verifiable delay (PoVD), a lightweight consensus protocol based on the verifiable delay function (VDF). We present the detailed protocol of PoVD, including the block mining and verification rules, and illustrate how PoVD can flexibly adjust the block time distribution according to the network condition. Through mathematical proof, we point out that, under a relatively weak network assumption, PoVD can achieve a lower fork rate than PoW while maintaining the same throughput. Our experiments verify that PoVD exhibits low computation and communication complexity and can also improve the blockchain consistency, making it particularly suitable for resource-constrained nodes and bandwidth-limited networks.

0.16

Security Limits of Mining Before Validation in Nakamoto Consensus

cs.CR cs.DC ·2026-09-24 ·Yifan Zhou, Jiang Xiao, Kaihua Qin
similarity 0.66
Abstract

Mining before validation allows miners to extend a newly received block before completing its validity checks, giving them a head start in the race for the next block reward. This head start, however, comes with a security risk: rejecting one invalid block also discards the honest work built on it, an effect missed when validation is treated as instantaneous. We quantify this risk in a model of Nakamoto consensus with bounded network delay and a validation-time bound independent of processing load. We establish an explicit threshold on adversarial mining power below which honest miners' fully validated chains continue to grow and agree on a stable history with high probability over any fixed observation period. We also construct an attack that repeatedly draws honest mining onto invalid branches. When the adversary produces more than one block on average during the allowed validation time, the attack can eventually remove a target block at any fixed initial confirmation depth. Combined with ordinary private mining, this attack yields a matching asymptotic bound in the fully decentralized regime, where each honest miner has negligible mining power. The results show how validation latency limits the security of mining before validation, beyond the constraint imposed by network delay.

0.21

STAKE: Preventing a colluding majority from double spending

cs.GT ·2026-10-01 ·Zahra Naderi, Vincent Gramoli
similarity 0.63
Abstract

Blockchains typically operate in open networks where it is hard to control the delay of messages. While classic blockchain protocols assumed synchrony, newer protocols try to remain secure despite unexpected network delays. Unfortunately, in the traditional model where $n$ participants can either be honest or Byzantine, we need a supermajority, or $\lfloor 2n/3\rfloor + 1$, of them to be honest. Recent work have explored the question of reducing the number of needed honest nodes in a game theory model to a majority sometimes by introducing $k$ rational players and $t$ Byzantine players. Yet, to our knowledge, no blockchain protocol managed to reduce it further. In this paper, we offer a blockchain protocol called Secure and Tolerant Algorithm through ($k,t$)-robust Equilibrium (STAKE) that works with only $\lfloor n/3\rfloor + 1$ honest players. STAKE requires each consensus participant to stake a sufficiently large amount $s$ compared to their liquidity $\ell$. We show that the probability that a coalition manages to execute $ζ$ double spending attacks (we call them a $ζ$-uple attack) drops exponentially fast with $ζ$. This allows us to demonstrate that STAKE reaches a ($k,t$)-robust equilibrium, or that rational players do not collude with Byzantine, even with a relatively low $s/\ell$ ratio.

0.12

Slow and Steady: Preventing MEV with Verifiable Delays

cs.CR ·2026-08-13 ·Zeta Avarikioti, Dimitris Karakostas, Karl Kreder, Shreekara Shastry
similarity 0.62
Abstract · A revised version is accepted for publication at the 10th International Workshop on Cryptocurrencies and Blockchain Technology (CBT 2026)

Our work presents a defense mechanism against Maximal Extractable Value (MEV) opportunities in distributed ledgers. The mechanism relies on the idea of enforcing a verifiable delay when generating transactions, such that a block creator cannot react to the appearance of a MEV opportunity without breaking liveness. We present positive results both in the Byzantine setting and in a game theoretic model of rational participants. We additionally present negative bounds that outline the limitations of this line of defense. Finally, we explore real-world implementation details of verifiable delays and show that, based on historical MEV data, our mechanism could realistically help prevent most existing MEV threats.

0.13

Fresh-Challenge VDF Attestations for Model-Relative Response Latency

cs.CR ·2026-09-11 ·Ansar Yesmukhanov, Aruzhan Tlessova
benchmarktheory similarity 0.61
Abstract · 9 pages, 1 figure

Can a finite verifier obtain public, model-relative evidence about response latency for sequential computation? Verifiable delay functions (VDFs) make this possible in principle: evaluation requires T sequential steps, whereas verification is efficient in the security parameter and polylogarithmic in the numerical value of T for standard constructions. Thus a delay can be astronomically large to evaluate yet succinctly represented and feasibly checked. A VDF proof for a chosen message alone is insufficient because it may be precomputed. We specify and analyze Fresh-Challenge VDF Attestations (FCLA), a protocol composition that binds a VDF to an unpredictable public challenge, a message, and independently auditable release and receipt records. Under explicit assumptions about VDF sequentiality, the challenge source, witness logs, and a calibrated upper bound on an adversary's sequential evaluation rate, an accepted FCLA transcript is inconsistent with post-challenge generation by an adversary in that bounded model. The result neither identifies a named claimant nor excludes relaying, outsourcing, or a faster unmodeled machine. A benchmark of the public reference implementation confirms the expected empirical separation between evaluation and verification on one documented machine. Our contribution is a protocol/design analysis and benchmarked reference implementation layer, not a new VDF construction or cryptographic primitive.

0.45

Vigil: Accountable Liveness against Selective Silence

cs.DC cs.CR ·2026-09-16 ·Jiawei Cheng, Huiping Sun, Rui Zhou, Jinjue Zhou, Zhong Chen
theory similarity 0.60
Abstract · 20 pages, 8 figures

BFT accountability is well understood for safety violations, and recent work attributes global liveness violations; \emph{recipient-selective} silence remains unresolved. A selectively silent adversary withholds messages from some honest nodes while behaving correctly toward others. It can stall consensus yet evade every existing mechanism. We initiate a systematic study of accountability against selective silence. Negatively, a lone attacker silent toward at most $f$ honest nodes is indistinguishable from an honest node, yielding a universal lower bound $K_{\mathrm{SI}} \ge f{+}1$ on the \emph{silence identification threshold}; moreover, any feedback-free repair after a silence-induced violation costs $Θ(n^3)$. Positively, \textsc{Vigil}, a Tendermint variant, matches these bounds with attack-adaptive forwarding, via bitmap cross-attestation, core-based membership, and challenge--response auditing. It pays $O(n)$ authenticators per node when no selective silence occurs (plus $Θ(n^2)$ bitmap metadata bits per node), relays in proportion to the attack's width (sub-threshold silence can force up to $n^3/27$ relays per view, a cost we price exactly), and majority-accuses any node silent toward more than a tunable resilience $τ_A$ of honest peers ($K_{\mathrm{SI}} = τ_A{+}1$, optimal at $τ_A = f$). We also price the residual sub-threshold griefing surface exactly and extend identification to $x$-partial synchrony. Real-network experiments on a three-region WAN, together with a simulator held to exact equality with every closed form, confirm each threshold and cost: at $2\%$ loss, an $f{+}1$ accusation bar falsely accuses $91.2\%$ of honest nodes, while our majority bar accuses $0.002\%$.

0.19

Asynchronous Verifiable and Complete Secret Sharing: From Design Patterns to System-Level Trade-offs

cs.CR ·2026-10-27 ·Joachim Bruneau-Queyreix, Martin Zivojinovic, Leo Mendiboure, Tom Claudel, Laurent Réveillère
similarity 0.60
Abstract

Modern secret sharing protocols promise robust secret sharing in fully asynchronous Byzantine systems, but their practical costs remain difficult to compare across papers, assumptions, and workloads. The difficulty is not merely experimental: protocols with similar asymptotic guarantees often place very different work on the critical path through their choices of dissemination, verification, batching, and recovery. This paper turns that fragmented research landscape into a corpus-backed designspace analysis and systems evaluation of asynchronous verifiable and complete secret sharing. We derive a design sieve, select seven representative protocols, and implement them in a common Rust framework. In our experiments on the Grid'5000 platform, we evaluate honest-dealer and faulty-dealer stress executions using latency, throughput, message count, bandwidth, and aggregate CPU-time. The results show that message complexity alone poorly predicts latency, that optimistic paths can be dominated by recovery cost, and that batching or packing helps only when verification stays off the critical path. These findings turn protocol-by-protocol comparisons into design-to-cost guidance for choosing, implementing, and extending asynchronous verifiable and complete sharing protocols.

0.28

Beyond Leaderless: Randomized Consensus Against Mobile Crashes

cs.DC ·2026-10-31 ·Ittai Abraham, Kaya Alpturer, Pranav Garimidi, Joachim Neu, Tim Roughgarden +1 more
similarity 0.59
Abstract · 32 pages, 6 figures

Many consensus protocols fail to terminate under attack from an adversary that has the power to move between replicas and repeatedly crash one of them, even in synchrony. We present Multi-Leader Fixed-View Simplex (ML-FVS) to defend against such an adversary while keeping the simple structure and good-case latency of Simplex consensus. Our protocol extends fixed-view Simplex with multiple leaders, each of which may broadcast a proposal. At the voting deadline, each replica votes on the set of proposals it has seen so far. A hidden threshold beacon revealed after the votes gives a priority order on the multiple leaders, resolving each vote to its highest-priority proposal. Our model combines permanent adaptive Byzantine faults with mobile crashes. For a constant crash budget and $Δ$-delayed Byzantine corruption, we obtain $O(Δ)$ expected latency over repeated views whose leaders start honest. With immediate Byzantine corruptions, the protocol still achieves liveness. We also evaluate the protocol under random network delays and stochastic faults, finding that multiple leaders reduce view failures even when rational leaders delay their proposals to increase rewards.

0.19