Fast Deterministically Safe Proof-of-Work Consensus
Ali Farahbakhsh, Giuliano Losa, Youer Pu, Lorenzo Alvisi, Ittay Eyal · 2025
Read Fast Deterministically Safe Proof-of-Work Consensus by Ali Farahbakhsh, Giuliano Losa, Youer Pu, Lorenzo Alvisi, Ittay Eyal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-19968.txt.
Introduction
Ali Farahbakhsh, Giuliano Losa, Youer Pu, Lorenzo Alvisi, and Ittay Eyal present Sieve-MMR, a blockchain consensus protocol claiming a combination previously thought out of reach. Permissionless chains let strangers join and leave freely, but proof-of-stake designs suffer long-range attacks that rewrite history cheaply, while proof-of-work designs settle for probabilistic guarantees or slowness. Their protocol aims for deterministic security with constant expected latency and no outside crutches like social consensus.
The route ports a proof-of-stake protocol, MMR, into the proof-of-work world, inheriting its latency and determinism while proof-of-work blocks long-range rewriting. The obstacle is time-travel attacks, where old work is replayed to inflate present power. A new broadcast primitive, time-travel-resilient broadcast, implemented by their Sieve algorithm over a black-box proof-of-work primitive, serves as MMR's messaging layer and defeats the replay.
Catalog record
| CREATOR | Ali Farahbakhsh, Giuliano Losa, Youer Pu, Lorenzo Alvisi, Ittay Eyal |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-19968
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fast Deterministically Safe Proof-of-Work Consensus Ali Farahbakhsh, Giuliano Losa, Youer Pu, Lorenzo Alvisi, Ittay Eyal Abstract Permissionless blockchains achieve consensus while allowing unknown nodes to join and leave the system at any time. They typically come in two flavors: proof of work (PoW) and proof of stake (PoS), and both are vulnerable to attacks. PoS protocols suffer from long-range attacks, wherein attackers alter execution history at little cost, and PoW protocols are vulnerable to attackers with enough computational power to subvert execution history. PoS protocols respond by relying on external mechanisms like social consensus; PoW protocols either fall back to probabilistic guarantees, or are slow. We present Sieve-MMR , the first fully-permissionless protocol with deterministic security and constant expected latency that does not rely on external mechanisms. We obtain Sieve-MMR by porting a PoS protocol (MMR) to the PoW setting. From MMR we inherit constant expected latency and deterministic security, and proof-of-work gives us resilience against long-range attacks. The main challenge to porting MMR to the PoW setting is what we call time-travel attacks , where attackers use PoWs generated in the distant past to increase their perceived PoW power in the present. We respond by proposing Sieve , a novel algorithm that implements a new broadcast primitive we dub time-travel-resilient broadcast (TTRB). Sieve relies on a black-box, deterministic PoW primitive to implement TTRB, which we use as the messaging layer for MMR. 1 Introduction * * footnotetext: These author contributed equally and are given in alphabetical order. Cryptocurrencies like Bitcoin and smart-contract platforms such as Ethereum aim to provide universal decentralized access to services like payments, banking, insurance, and e-commerce. They aspire to present users worldwide with an open-access, secure, and fast transaction log. Typically, a total-order broadcast (TOB) protocol implements the log abstraction, and participation in the protocol is permissionless thanks to the use of proof-of-stake (PoS) or proof-of-work (PoW). In PoW, participation requires solving expensive computational puzzles; in PoS, it requires putting cryptocurrency in escrow. PoW and PoS paradigms are vulnerable to attacks that, though paradigm-specific, share a similar goal: crafting an alternate execution history to confuse newly joining nodes who did not witness the past execution firsthand. No existing protocol, in either paradigm, has satisfactorily addressed these attacks. Long-range attacks are an instance of these attacks specific to PoS systems: they consist in purchasing keys belonging to former participants—likely cheaply, as those parties no longer have a skin in the game—and using those keys to fabricate an alternate execution history. Without mechanisms external to the system ( e.g. , secure checkpoints, social consensus, etc.), there exists no defense against such attacks [ 45 , 4 ] . PoW systems are not vulnerable to long-range attacks; however, they are either prohibitively slow [ 42 , 43 ] or rely on proof-of-work puzzles with probabilistic guarantees, which leave open the possibility that a lucky attacker may successfully create an alternate history ( e.g. , in Bitcoin, a fork of the longest chain). Even if in practice the failure probability can be made sufficiently small, proving safety for these probabilistic protocols is quite tricky; for instance, it took the community considerable effort to establish Bitcoin’s security ( e.g. , [ 22 , 15 ] ). We present Sieve-MMR, the first permissionless PoW TOB protocol with deterministic security and constant expected latency . Sieve-MMR relies on a cryptographic hash function to obtain a deterministic proof-of-work primitive DPoW. Generating a DPoW requires a fixed number of hash computations, and we assume that adversaries control a minority of the computation power. DPoW is similar to a verifiable delay function [ 7 ] , but without the requirement that the computation steps be performed serially. A key principle guides the design of Sieve-MMR: decoupling the consensus logic from the logic used to control the undesirable side-effects of permissionless participation . This separation of concerns opens an intriguing new possibility: safely deploying existing low-latency consensus protocols, originally developed under stronger models, in a fully permissionless setting. Accordingly, we design Sieve-MMR in two layers. The top layer implements consensus using a protocol inspired by what we call the MMR protocol [ 36 , Appendix A] , a fast and deterministically safe protocol in the family of dynamically available [ 32 ] PoS TOB protocols. Our main technical contributions are in the bottom layer. For the first time, this layer specifies and implements the message delivery guarantees that dynamically available protocols like MMR must rely on to maintain correctness in a fully-permissionless setting. Time travel considered harmful. Embedding dynamically available protocols in a fully-permissionless setting exposes them to an insidious new threat. Not only must they defend against adversaries using their current computing power to modify past consensus decisions, but also against adversaries leveraging their past computing power to alter consensus decisions in the present! This vulnerability stems from how dynamically available protocols implement consensus [ 21 , 37 ] : they build upon traditional quorum intersection arguments, which in turn rely on correct ( i.e. , protocol-abiding) nodes generating a sufficiently strong majority of the messages being sent. However, in a permissionless setting, nothing prevents corrupted nodes from generating messages at some point in the past, holding onto them, and sending them as if they were generated in the present, thereby distorting the quorums correct nodes perceive. TTRB and Sieve. We capture the messaging properties that MMR and similar protocols need to be immune to such time travel attacks with a new broadcast primitive: time-travel-resilient broadcast ( TTRB ). TTRB operates in rounds and provides two guarantees: ( i ) all messages TTRB-delivered in a given round were generated in the previous round; and ( ii ) all messages that correct nodes generated in the previous round are TTRB-delivered by correct nodes in the current round. We implement TTRB with the novel protocol Sieve . Like its namesake, we use Sieve to filter out “impurities”—in our case, time-traveling messages. Sieve limits the number of messages that a node can generate in a given round by augmenting each message with the DPoW evaluation of its payload. Furthermore, each message in Sieve is associated with a timestamp, which intuitively represents the round in which the message generation began. Messages carry this timestamp as an attribute, and in any given round, Sieve should only deliver messages that are timestamped from the previous round. Of course, an adversary might attempt to counterfeit the timestamp attribute, trying to pass off an earlier message as a later one. To counter this, Sieve implements a Byzantine-tolerant mechanism that can identify and discard messages with counterfeit timestamps. At the core of this mechanism is the DAG of DPoW evaluations induced by requiring correct nodes to logically include in each message they generate a “coffer” containing all messages they accepted in the previous round. By iteratively analyzing and pruning the DAG, Sieve is able to tell when a message m claiming a generation time s includes at least one message generated by a correct node at time s-1 ; inductively, this guarantees that m was generated no earlier than time s , and Sieve filters out all messages that do not pass this test. Concretely, Sieve comprises two filtering policies: Bootstrap-Sieve and Online-Sieve. Correct