Verification of a DPLL Transition System in Rocq

Imagine a world where computers are constantly playing a high-stakes game of "True or False." In this game, the computer is handed a giant, tangled knot of logical statements—like a recipe that says, "If you add sugar, you must also add flour, but if you add flour, you cannot add salt." The goal is to find a way to follow the recipe without breaking any rules. This is the Satisfiability (SAT) problem. It's the digital equivalent of trying to fit a million different puzzle pieces into a box where some pieces are red, some are blue, and the instructions say, "No red next to blue."

Why do we care? Because this isn't just a logic puzzle; it's the engine behind almost everything complex in computing. From designing microchips to proving that a mathematical theorem is true, computers use SAT solvers to navigate these massive logical mazes. But here's the catch: these solvers are incredibly complex. If a tiny bug hides in the code, the computer might confidently tell you a proof is valid when it's actually nonsense. That's why mathematicians and computer scientists are obsessed with formal verification. Think of it as building a super-strict, unbreakable safety net. Instead of just hoping the computer works, they use a special kind of "mathematical microscope" (called a proof assistant) to check every single step of the logic, ensuring the machine can never lie about the answer.

The Paper's Big Adventure: Building a Trustworthy Logic Machine

In this paper, Julia Dijkstra and Benedikt Ahrens take a giant leap toward making these logic machines trustworthy. They didn't just write a program; they built a mathematically proven skeleton of a famous logic-solving method called DPLL (Davis-Putnam-Logemann-Loveland) inside a tool called Rocq.

Think of the DPLL method not as a rigid robot following a script, but as a game of "State Switching." Imagine a detective trying to solve a mystery. The detective starts with an empty notebook (no clues). They have a set of rules for how to update their notebook:

1. The "Oh, I see!" Rule (Unit Propagate): If a clue says "The butler did it OR the maid did it," and the detective already knows the maid is innocent, the notebook must update to say "The butler did it." The detective has no choice; the logic forces the move.
2. The "Pure Guess" Rule (Pure Literal): If the detective sees a clue about "The gardener" but never sees a clue about "The gardener not doing it," they can safely guess the gardener is involved without fear of contradiction.
3. The "Branching Out" Rule (Decide): If the detective is stuck, they pick a random clue (like "The butler did it") and write it down as a decision. This is a fork in the road.
4. The "Oops, Wrong Turn" Rule (Backtrack): If the detective writes down a decision and later finds a contradiction (a clue that says "The butler didn't do it"), they have to erase everything that happened after that decision, flip the decision (now the butler didn't do it), and try again.
5. The "Game Over" Rule (Fail): If they erase everything, flip the last decision, and still hit a contradiction, the game is over. The mystery is unsolvable.

The authors' main achievement is taking this entire game and writing it down in a language that the Rocq proof assistant can read and verify. They didn't just say, "This looks right." They proved three massive things:

• Correctness: If the game ends with a solution, that solution is definitely real. The computer won't hallucinate a model.
• Completeness: If a solution exists, the game will find it. The computer won't get stuck or give up when it shouldn't.
• Termination: The game will never run forever. It is mathematically guaranteed to stop, either with a solution or a "Game Over."

Adding a New Twist: The "Pure" Rule

One of the paper's cool contributions is that they added a specific rule to their game that some previous versions of this theory left out: the Pure Literal Rule. In the detective analogy, this is the moment the detective realizes, "Hey, I've never seen any evidence against the gardener, so I'll just assume the gardener is the culprit." The authors proved that adding this rule makes the game faster without breaking any of the safety guarantees. They showed that even with this extra shortcut, the logic remains airtight.

From Theory to a Real (But Simple) Robot

After proving the rules of the game work perfectly in theory, the authors asked: "Can we actually build a robot that plays this game?" They created a strategy—a set of instructions for the detective on which rule to pick next. They built a concrete version of this strategy in Rocq and then used a magical tool called extraction to turn their mathematical proof into a real computer program written in OCaml.

They tested this new robot on some simple puzzles. It worked! It solved problems correctly, including a puzzle called zebra.cnf with 155 variables and 1,135 clauses. However, the authors are very honest about the robot's limitations. It's like a proof-of-concept toy car: it drives perfectly and proves the engine works, but it's not a Formula 1 race car yet. It's slow because it uses simple lists to remember clues, whereas real-world racing cars use high-speed memory. The authors admit this version isn't ready to beat the industrial giants used by companies today, but it's a verified core. It's a tiny, unbreakable foundation upon which future, faster, and smarter solvers can be built.

What This Means for the Future

The paper doesn't claim to have solved the problem of making the world's fastest SAT solver. Instead, it claims to have built the safest possible blueprint. By proving the abstract rules in Rocq, they've created a "trusted core." Future researchers can now take this blueprint and add the fancy features of modern solvers—like "learning from mistakes" (clause learning) or "jumping back multiple steps" (non-chronological backtracking)—with the confidence that the underlying logic is still sound.

In short, Dijkstra and Ahrens didn't just build a better car; they built the blueprint for a car that can never crash, proving that the logic behind the wheels is mathematically perfect. It's a small, verified step that paves the way for much larger, more complex, and trustworthy logic machines in the future.