💻 computer science

Simplifying Safety Proofs with Forward-Backward Reasoning and Prophecy

This paper introduces an incremental safety proof framework that combines forward reasoning, backward reasoning on time-reversed systems, and prophecy steps to decompose complex inductive invariants into simpler components, thereby reducing the search space for verification and demonstrating its effectiveness on distributed consensus protocols like Paxos and Raft.

Original authors: Eden Frenkel, Kenneth L. McMillan, Oded Padon, Sharon Shoham

Published 2026-04-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Eden Frenkel, Kenneth L. McMillan, Oded Padon, Sharon Shoham

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 you are trying to prove that a complex machine (like a distributed computer network) will never break or do something bad. In the world of computer science, this is called safety verification.

Traditionally, to prove a machine is safe, you have to write a single, massive "rulebook" (called an inductive invariant) that describes every possible good state the machine can be in. The problem is, for complex systems, this rulebook becomes a tangled mess of logic—full of "ANDs," "ORs," and confusing "For all" and "There exists" statements. It's like trying to describe a city's traffic safety by writing one giant, unbreakable sentence that covers every car, every light, and every pedestrian simultaneously. It's so complex that computers (and humans) struggle to find it.

This paper proposes a new way to solve this puzzle. Instead of writing one giant rulebook, the authors suggest breaking the proof into smaller, manageable steps using three clever tricks: Forward Reasoning, Backward Reasoning, and Prophecy.

Here is how it works, using simple analogies:

1. The Problem: The Giant Tangled Knot

Imagine you are trying to prove a maze has no dead ends that lead to a trap.

The Old Way: You try to draw a single, perfect map that covers the entire maze at once, showing exactly where you can and cannot go. For a huge maze, this map is so detailed and complex that it's impossible to draw without making a mistake.

2. The Solution: Breaking the Proof into Steps

The authors say, "Don't try to draw the whole map at once. Let's build it piece by piece."

Trick A: Forward and Backward Reasoning (The Two-Way Street)

Usually, we only look at the maze from the Start (Forward). We ask, "If I start here, where can I go?"
But sometimes, it's easier to look from the Trap (Backward). We ask, "If I am in the trap, where could I have come from?"

The Analogy: Imagine trying to prove two people can never meet in a hallway.
- Forward: You watch Person A walk from the left. You see they stop at a certain point.
- Backward: You watch Person B walk from the right (in reverse). You see they stop at a different point.
- The Magic: By combining these two views, you can prove they never meet using much simpler descriptions than if you tried to track both of them simultaneously from the start. The "Forward" view handles the beginning, and the "Backward" view handles the end. When you put them together, the middle part becomes much simpler to describe.

Trick B: Prophecy (The Crystal Ball)

Sometimes, the rulebook needs to say things like, "There exists a specific key that opens this door." This "There exists" part is hard for computers to handle because they have to guess which key it is.

The Analogy: Imagine you are a detective trying to prove a crime didn't happen.
- The Hard Way: You have to prove, "There is no suspect who could have done it." You have to check every single person in the city.
- The Prophecy Way: You use a "Crystal Ball" (a Prophecy Variable). You say, "Let's assume there is a specific person, let's call him 'Witness,' who was at the scene." You don't need to know who he is yet; you just give him a name tag.
- Now, instead of searching the whole city, you just check if this specific Witness could have committed the crime. If you can prove the crime is impossible even with this specific Witness, you are done.
- The Result: You replaced a confusing "There exists" (searching the whole city) with a simple "This specific guy" (checking one name). It turns a complex search into a simple check.

3. The Synergy: Why It's a Big Deal

The paper's real breakthrough is showing that these three tricks work best when used together.

Forward-Backward reasoning simplifies the "shape" of the logic (removing complex "AND/OR" tangles).
Prophecy simplifies the "search" (removing the need to guess "There exists").
Together: They allow the computer to find a proof using very simple, clean sentences (like "All cars must stop at red lights") instead of a giant, messy paragraph.

The Real-World Test: Paxos and Raft

The authors tested this on Paxos and Raft, which are famous computer protocols used to keep data safe in systems like Google or Amazon. These protocols are notorious for having incredibly complex safety proofs.

The Result: Using their new method, they were able to prove these systems are safe using much simpler rules.
- In some cases, they reduced a proof that required 5 different layers of complex logic down to a few simple, one-line rules.
- This makes it much faster for computers to automatically verify that these critical systems are safe.

Summary

Think of this paper as a new strategy for solving a massive jigsaw puzzle.

Old Way: Try to force all the pieces together at once. It's frustrating and often fails.
New Way:
1. Look at the top edge of the puzzle (Forward).
2. Look at the bottom edge of the puzzle (Backward).
3. Use a "magic marker" to label a few key pieces so you don't have to guess where they go (Prophecy).
4. Connect the dots.

By doing this, the authors show that we can prove complex systems are safe using much simpler, easier-to-understand logic, making our digital world safer and our computers faster at checking it.

1. Problem Statement

Verifying the safety of complex distributed systems (e.g., consensus protocols like Paxos and Raft) typically relies on finding a safe inductive invariant. An inductive invariant is a property that holds in all initial states and is preserved by every system transition. If such an invariant implies the safety property, the system is safe.

However, as systems grow in complexity, the required inductive invariants often become extremely complex. This complexity manifests in three ways:

Boolean Structure: The formulas may require complex combinations of conjunctions and disjunctions (non-clausal structures).
Quantifier Complexity: The formulas may involve deep quantifier nesting.
Quantifier Alternation: The formulas may require alternating quantifiers (e.g., $\forall \exists$ ), which significantly increases the difficulty of automated synthesis and validation.

Existing modular reasoning approaches (like assume-guarantee) divide the system into components, but they do not help when a single component requires a complex proof. This paper addresses the challenge of simplifying the proof itself rather than the system structure.

2. Methodology

The authors propose an incremental proof system that decomposes a complex safety proof into a sequence of simpler steps. This system combines three distinct reasoning mechanisms:

A. Incremental Forward-Backward Reasoning

Instead of relying solely on forward induction (proving properties of reachable states), the system allows mixing:

Forward Steps: Proving an invariant holds for all states reachable from the initial state.
Backward Steps: Proving an invariant holds for all states that can reach a "bad" state (using the time-reversed system).

Key Insight: A safety proof can be constructed by accumulating properties of error traces (paths from initial to bad states). A predicate used in a backward step does not need to hold for all reachable states, only for states on potential error traces. This allows the use of simpler predicates (e.g., purely universal clauses) that, when combined via the incremental structure, imply safety. The system proves that any such incremental proof can be converted back into a single safe inductive invariant, which is a Boolean combination of the simpler auxiliary predicates used in the steps.

B. Prophecy Variables

To address quantifier nesting and alternation, the authors introduce prophecy steps.

Concept: A prophecy step introduces a fresh constant symbol (a witness) $w$ and an axiom $\phi(w)$ that "prophesies" the existence of an element satisfying $\phi$ along every trace.
Soundness: The paper formalizes the soundness of adding a prophecy as an auxiliary safety problem. Specifically, checking if a prophecy is sound is equivalent to checking the safety of a system augmented with a "history" predicate that tracks whether the prophesied property has held continuously in the past.
Synergy: Prophecy works synergistically with forward-backward reasoning. A forward step can identify a witness (e.g., a specific quorum in Paxos), which is then used as a prophecy symbol in a subsequent backward step. This allows the backward step to avoid existential quantification, replacing $\exists x$ with a fixed witness $w$ .

C. The Proof System (FBPI)

The authors define a proof system called FBPI (Forward-Backward with Prophecy Incremental) consisting of inference rules:

(Ind): Standard forward induction.
(Rev): Time-reversal to switch between forward and backward reasoning.
(Inc): Incremental strengthening (adding previously proved invariants as axioms).
(Proph): Introducing a prophecy witness, provided its soundness is proven via an auxiliary safety problem.

The system includes heuristics (e.g., Proph-Select) to automate the discovery of valid prophecies by checking specific verification conditions (e.g., a property is forward-preserved and holds initially).

3. Key Contributions

Novel Proof System: The introduction of a proof system that synergistically combines forward reasoning, backward reasoning, and prophecy variables. This is the first work to formally integrate these three techniques for safety proofs of parameterized systems.
Soundness Characterization: A rigorous characterization of prophecy soundness as an auxiliary safety problem, allowing the verification of prophecies within the same incremental framework.
Proof Power Analysis: Theoretical proofs demonstrating that:
- Incremental proofs can prove safety problems where no safe inductive invariant exists within a restricted class of formulas (e.g., purely clausal formulas).
- Forward-backward reasoning strictly increases proof power by allowing the elimination of complex Boolean structures (conjunctions/disjunctions).
- Prophecy strictly increases proof power by eliminating quantifier nesting and alternations.
Translation Mechanism: A constructive method to translate any incremental forward-backward-prophecy proof back into a standard safe inductive invariant, proving the soundness of the approach.

4. Results (Case Study)

The authors evaluated their approach on Paxos (and its variants: Flexible, Multi, Fast) and Raft.

Simplification of Boolean Structure: For many Paxos variants, standard forward proofs require invariants with complex Boolean structures (mixing $\land$ and $\lor$ ). The forward-backward approach reduced these to purely clausal (disjunctive normal form) predicates.
Elimination of Quantifier Alternation: In standard proofs, invariants often require alternating quantifiers (e.g., $\forall \exists$ ). By using prophecy to fix witnesses (e.g., a specific quorum), the authors reduced these to purely universally quantified clauses.
Performance:
- The incremental proofs significantly reduced the search space for automated invariant inference tools.
- Verification times were reduced for complex examples (e.g., Raft and Fast Paxos), dropping from seconds to sub-second ranges in some cases.
- For Raft, which previously required an invariant with 7 quantifiers and 2 alternations, the new method reduced the user-specified predicates to universally quantified clauses with 1 quantifier and 0 alternations.

Table 1 Summary (from the paper):

Forward Proofs: Often required non-clausal formulas with high quantifier alternation (e.g., $Q=7, A=2$ for Raft).
Forward-Backward: Reduced Boolean complexity to clausal forms but often retained alternation.
Forward-Backward + Prophecy: Eliminated alternation entirely ( $A=0$ ) and reduced quantifier counts, resulting in purely universal, clausal predicates.

5. Significance

Automation: By reducing the complexity of the required invariants (specifically removing non-clausal structures and quantifier alternations), this approach makes automated invariant synthesis (e.g., using tools like PDR $\forall$ or IC3) much more feasible. The search space for valid formulas becomes significantly smaller.
Theoretical Insight: It demonstrates that the "complexity" of a safety proof is not an intrinsic property of the system but can be shifted. A complex invariant can be decomposed into a sequence of simple steps using different reasoning directions and witnesses.
Practical Impact: The ability to verify complex consensus protocols (like Raft) with simpler, human-readable, and machine-verifiable invariants is a major step forward in the formal verification of distributed systems.
Synergy: The paper highlights that forward and backward reasoning are not just alternatives but complementary; backward reasoning can guide the selection of prophecy witnesses for forward reasoning, and vice versa.

In conclusion, the paper provides a powerful framework for simplifying safety proofs by breaking the monolithic requirement of a single complex invariant into a sequence of simpler, direction-specific, and witness-augmented steps, thereby overcoming major bottlenecks in automated verification.