💻 computer science

Fast Deterministically Safe Proof-of-Work Consensus

This paper introduces Sieve-MMR, the first fully-permissionless blockchain protocol that achieves both deterministic security and constant expected latency without external mechanisms by adapting a Proof-of-Stake protocol to the Proof-of-Work setting and employing a novel Sieve algorithm to mitigate time-travel attacks.

Original authors: Ali Farahbakhsh, Giuliano Losa, Youer Pu, Lorenzo Alvisi, Ittay Eyal

Published 2026-06-04

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ali Farahbakhsh, Giuliano Losa, Youer Pu, Lorenzo Alvisi, Ittay Eyal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive, global digital ledger where anyone can join or leave at any time. This is the world of permissionless blockchains (like Bitcoin). The goal is for everyone to agree on the order of transactions without a boss telling them what to do.

For a long time, these systems have had two main ways of working, both with serious flaws:

Proof of Stake (PoS): You lock up money to vote. The problem? If an attacker buys old accounts from people who left years ago, they can rewrite history cheaply. This is called a "Long-Range Attack."
Proof of Work (PoW): You solve hard math puzzles to vote. The problem? It's either incredibly slow, or it relies on "probabilistic" safety (meaning there's a tiny, non-zero chance an attacker could get lucky and rewrite history).

The authors of this paper, Sieve-MMR, have built a new system that claims to be the best of both worlds: it's fast, it's secure against history rewriting, and it doesn't need outside help (like social consensus or checkpoints) to be safe.

Here is how they did it, using some everyday analogies.

The Big Idea: Decoupling the "Voting" from the "ID Check"

Think of a consensus protocol like a town meeting.

The Consensus Logic (MMR): This is the actual voting process. "Who has the most votes? Let's agree on that." This part is fast and smart, but it was originally designed for a town where everyone has a fixed ID card and knows who is present.
The Permissionless Problem: In a permissionless system, people can join and leave instantly. Worse, a bad actor can pretend to be a person who left the town 10 years ago and bring back old votes to confuse the current meeting. This is the "Time-Travel Attack."

The authors realized they could take the fast, smart voting logic (MMR) and wrap it in a new "security guard" layer (Sieve) that handles the chaos of people joining/leaving and time-traveling.

The Villain: The Time-Traveler

In a normal meeting, if you speak, you speak now.
In a permissionless blockchain, a bad actor (Byzantine node) can do something sneaky:

They generate a bunch of "votes" (math puzzles) back in 2020.
They sit on them.
In 2026, they dump all those old votes into the current meeting, pretending they were just cast right now.

Because the system sees a flood of "votes" from the past, it gets confused about who actually has the majority today. This breaks the safety of the meeting.

The Hero: The Sieve

To stop these time-travelers, the authors invented a new filter called Sieve. Think of it like a bouncer at a club who checks IDs, but with a twist.

How the Sieve works:

The "Coffin" (Coffer): Every time a node sends a message (a vote), it must include a "coffer" (a bag) containing the messages it received from the previous round.
The Proof of Work (DPoW): To send a message, you must solve a math puzzle. The time it takes to solve it is recorded.
The Filter: When the Sieve receives a pile of messages, it looks at the "coffers."
- If a message claims to be from "Round 5," but its coffer doesn't contain the messages from "Round 4" that were just generated by honest people, the Sieve knows it's a fake.
- Analogy: Imagine someone claims they just arrived at a party in 2026. But when you look at their photo album (the coffer), the photos are from 2020, and they don't have any pictures of the party decorations that were put up yesterday. The bouncer (Sieve) says, "You're a time-traveler. You can't get in."

The Sieve filters out these "antique" messages, ensuring that only messages generated recently by people who were actually present recently get counted.

The Two Modes of the Sieve

The Sieve has two ways of working, depending on how long you've been at the party:

Online-Sieve (The Regular Guest): If you've been at the party for a while, you have a list of the last round's valid messages. You just check if the new messages fit with that list. This is fast and easy.
Bootstrap-Sieve (The New Guest): If you just joined the party, you don't have the history. You have to look at the entire history of the party from the beginning, build a giant map (a DAG) of who talked to whom, and figure out which messages are real and which are time-travel fakes.
- The Catch: This "New Guest" process is computationally heavy (it's like solving a massive puzzle). The paper admits this is a hurdle for real-world use right now, but it proves the concept works.

The Result: Sieve-MMR

By stacking the Sieve (the security guard) under the MMR (the fast voting logic), they created Sieve-MMR.

Deterministic Safety: Unlike Bitcoin, where you have to wait and hope the attacker doesn't get lucky, this system guarantees safety. If the rules are followed, the history cannot be changed.
Constant Latency: It's fast. The paper claims transactions can be finalized in a predictable, short amount of time (about 7 steps), rather than waiting for "probabilistic" confirmation.
No Long-Range Attacks: Because the Sieve filters out old messages, an attacker cannot buy old keys and rewrite history.
No External Help: It doesn't need a "social consensus" or a central checkpoint to be safe. It does it all mathematically.

The Limitations (The Fine Print)

The paper is honest about what it can't do yet:

Bandwidth: It requires everyone to talk to everyone else in every round. If the network gets huge, the traffic jams get huge (quadratic scaling).
The "New Guest" Problem: The Bootstrap-Sieve (for new nodes) requires solving a very hard math problem over the entire history of the chain. It's currently more of a theoretical proof than a ready-to-use tool for new users.
Synchronous Network: It assumes messages arrive quickly and in order, which is a bit of an idealization for the messy real-world internet.

Summary

The paper presents Sieve-MMR, a new way to run a blockchain that combines the speed and certainty of modern voting systems with the security of Proof-of-Work. It solves the "Time-Travel Attack" problem by using a clever filtering mechanism (Sieve) that ensures only fresh, recent votes count, preventing attackers from using old data to confuse the system. While it has some practical hurdles to clear before it can replace Bitcoin or Ethereum, it proves that a fast, perfectly secure, permissionless blockchain is theoretically possible.

Technical Summary: Fast Deterministically Safe Proof-of-Work Consensus

Problem Statement

Permissionless blockchains face a fundamental trade-off between security guarantees and performance. Existing protocols generally fall into two categories: Proof-of-Stake (PoS) and Proof-of-Work (PoW), both of which suffer from specific vulnerabilities:

PoS Vulnerabilities: PoS protocols are susceptible to long-range attacks, where adversaries purchase historical keys to fabricate alternate execution histories at low cost. Defending against this typically requires external mechanisms (e.g., social consensus or secure checkpoints), which undermines the self-contained nature of the system.
PoW Vulnerabilities: Traditional PoW protocols (like Bitcoin) avoid long-range attacks but rely on probabilistic safety guarantees. This leaves open the possibility of an attacker successfully creating an alternate history. Furthermore, achieving deterministic safety in PoW has historically resulted in prohibitively slow protocols (e.g., exponential latency) or required restrictive models.

The core challenge addressed by this paper is the "time-travel attack." In a fully permissionless setting, dynamically available protocols (which allow nodes to join and leave) rely on quorum intersection arguments. However, in a permissionless environment, Byzantine nodes can generate messages in the distant past, store them, and release them later to distort the perceived quorum of correct nodes in the present. This "time travel" invalidates the quorum intersection logic, rendering standard dynamically available protocols insecure without external trust assumptions.

Methodology: Sieve-MMR

The authors propose Sieve-MMR, the first fully-permissionless Proof-of-Work Total-Order Broadcast (TOB) protocol that achieves deterministic safety and constant expected latency without relying on external mechanisms. The system is built on two distinct layers:

1. The Bottom Layer: Sieve and TTRB

The primary technical contribution is Sieve, a novel algorithm that implements a new broadcast primitive called Time-Travel-Resilient Broadcast (TTRB).

Goal: TTRB ensures that messages delivered in a given round were generated in the immediately preceding round, filtering out "antique" (time-traveling) messages.
Mechanism: Sieve utilizes a deterministic Proof-of-Work (DPoW) primitive. It constructs a Directed Acyclic Graph (DAG) of DPoW evaluations where messages are vertices and edges represent inclusion in "coffers" (sets of messages from the previous round included in a new message's payload).
Filtering Policies: Sieve employs two filtering strategies to prune the DAG and identify valid messages:
- Online-Sieve: Used by nodes that were active in the previous step. It efficiently filters messages by checking if the intersection of a message's coffer and the set of valid messages from two steps prior exceeds a weighted threshold ( $1-\rho$ ).
- Bootstrap-Sieve: Used by nodes joining the system or recovering from inactivity. It performs a more computationally intensive analysis of the entire DAG history to reconstruct the valid set of messages from the previous step, ensuring the node does not accept antique messages that could confuse its view of the quorum.
Assumptions: Sieve assumes a synchronous network and that adversaries control less than half ( $\rho \le 1/2$ ) of the total DPoW computation power over any sufficiently long interval.

2. The Top Layer: MMR

The consensus logic is derived from the MMR protocol (Malkhi et al.), a fast, deterministically safe PoS protocol designed for the "dynamically available" model.

Integration: By layering MMR atop Sieve, the authors decouple the consensus logic from the permissionless participation logic. Sieve provides the message delivery guarantees (TTRB) that MMR requires to maintain quorum intersection.
Leader Election: Sieve-MMR uses a probabilistic leader election component based on the DPoW random oracle to determine which chain to vote on or commit in each step.

Key Contributions

Time-Travel-Resilient Broadcast (TTRB): A new broadcast abstraction that guarantees a messaging layer immune to time-travel attacks, ensuring that delivered messages are causally consistent with the current round.
Sieve Algorithm: A novel protocol implementing TTRB using a black-box DPoW primitive. It introduces the concept of "coffers" and DAG-based pruning to distinguish between current and antique messages.
Sieve-MMR Protocol: The first fully-permissionless TOB protocol that achieves:
- Deterministic Safety: No probabilistic failure modes regarding safety (within the Dolev-Yao model).
- Constant Expected Latency: Transactions are committed in a constant number of steps (expected 7 steps, best case 3 steps).
- No External Trust: It does not rely on social consensus or external checkpoints to prevent long-range attacks.

Results and Guarantees

Safety: Sieve-MMR guarantees consistency (all correct nodes commit compatible chains) and progress (chains eventually grow). It inherits MMR's ability to tolerate a $1/3$ -bounded adversary in the consensus layer, while Sieve itself tolerates a $1/2$ -bounded adversary in the messaging layer.
Latency: The protocol achieves constant expected latency, a significant improvement over previous deterministic PoW protocols which suffered from exponential latency relative to the number of participants.
Security Model: The security claims hold within a Dolev-Yao style model where adversaries cannot break cryptographic primitives or guess messages. The protocol assumes a synchronous network and relies on all-to-all broadcast, incurring quadratic bandwidth costs relative to the number of active nodes.

Significance and Limitations

The paper positions Sieve-MMR as a significant theoretical step toward practical, fast, and secure PoW consensus. It demonstrates that the "time-travel" vulnerability, previously thought to be a fundamental barrier to porting low-latency consensus to permissionless settings, can be mitigated through the Sieve mechanism.

However, the authors are modest regarding immediate practical deployment, noting several hurdles:

Computational Complexity: The Bootstrap-Sieve phase requires solving an exponential-time problem over the protocol's execution history. While nodes are not bound to complete this within a fixed time, they must do so before active participation, which is a significant barrier for new nodes.
Network Assumptions: The protocol assumes a synchronous network and all-to-all communication, which may not scale efficiently in real-world, asynchronous internet environments.
Verification Overhead: Verifying DPoW evaluations for all messages can be computationally expensive, though the authors suggest batch verification and cryptographic optimizations (like zero-knowledge proofs) as potential future remedies.

In conclusion, Sieve-MMR provides a theoretical bridge between the dynamically available and fully-permissionless models, proving that deterministic safety and constant latency are achievable in a permissionless PoW setting without external trust, provided the computational and network constraints can be addressed.