CreuSAT: a SAT solver whose answers come with a proof

The verdict is the product, not just the answer

Most SAT solvers are trusted on reputation and on test coverage. CreuSAT takes a different position: the answer is not the deliverable, the answer plus a machine checked proof of it is.

The claim in the project documentation is that if the solver states a formula is satisfiable, that result is proven, and likewise for unsatisfiable. The reasoning behind this is that the solver itself is formally verified using Creusot, a verifier for Rust programs, so the properties the solver relies on to reach its conclusion are themselves checked rather than trusted. The same verification pass is what establishes that the solver is statically proven free of runtime panics, so it cannot crash while you are waiting for an answer.

That is a much stronger guarantee than most software offers, and it is worth being precise about what it does and does not cover. The guarantee is about the correctness of the reasoning and the absence of panics. It is not a claim about how fast the solver is, and the repository itself is careful with the speed claim, which appears in a thesis title rather than in a benchmark table.

The solver is written in Rust and the whole project is a Cargo workspace, so the standard toolchain handles the build.

A CDCL core with the usual feature list and no extras

The feature list is short and specific, which is what a verified solver needs to be. Clause analysis with clause learning is there, along with unit propagation. The conflict analysis loop uses two watched literals with blocking literals and circular search, and the decision heuristic is the variable move to front, or VMTF, strategy. Phase saving keeps a variable's last polarity across restarts, and the trail is backtracked to the asserting level when a conflict is reached.

Restarts are driven by exponential moving averages, and clauses can be deleted, with the documentation noting there is no garbage collection. The absence of garbage collection is a real limitation rather than an oversight in the description: the clause database grows, and in a long running instance that growth is unbounded.

Comparing this with an industrial solver, the gap is obvious. There is no clause vivification, no on the fly hyper binary resolution, no learned clause reduction, no target phases, no LBD based decisions. The repository makes the same point from the other direction by keeping an unverified solver, JigSAT, in the tree specifically for experimenting with optimizations that have not been verified yet.

The performance angle, then, is that CreuSAT is a research and teaching artifact. A team that needs to solve hard industrial instances in a production pipeline should look at a mature solver instead, because the gap between a verified research solver and a tuned one is measured in orders of magnitude on the benchmark families that matter.

Building and running on a DIMACS CNF file

The toolchain is Rust, and the workflow is the standard Cargo one. Three commands cover the whole life of the code:

cargo build

bash

cargo test

bash

cargo run -- --file [PATH_TO_FILE]

bash

The third one takes a single file argument and the input has to be a correctly formatted DIMACS CNF file, which is the standard text encoding of a CNF formula used across the SAT literature. The path placeholder is literal in the command as the project documents it, so in practice you point it at your own file.

One warning is worth repeating because it is easy to hit. The documentation asks you to add the --release flag, as in cargo test --release [TEST_TO_RUN], because without it the code is built in debug mode, which the author describes as slow. That is a plain consequence of Rust's default debug profile, and the release profile in the workspace manifest is tuned hard: fat link time optimisation, a single codegen unit, opt-level 3, debug assertions off, overflow checks off, incremental off, and panic set to abort.

The panic abort setting is worth noticing in a project about panic freedom. It means any panic would end the process rather than unwind, which is consistent with the verified claim that panics do not occur, and it is also a reminder that a solver in this design is expected to either produce a result or terminate.

Reproducing the proof needs Creusot, and the shipped recipe is broken

The verification story is the heart of the project and the part with the roughest edges. To check the proofs yourself you need Creusot installed, which the documentation points at the Creusot repository for user installation instructions.

The supported route is to move into the directory of the solver you want to verify and run cargo creusot why3 ide, which generates the configuration and opens the Why3 IDE:

cargo install --force cargo-make

bash

Once the IDE appears, you select the root node and press 3, and the various verification conditions are dispatched to SMT solvers, with each condition ending up marked with a green checkmark if the proof goes through.

The convenience wrapper is where things break. The project uses Cargo Make to make building easier, installable with:

cargo install --force cargo-make

bash

and the intended single command is:

cargo make prove-CreuSAT

bash

The documentation states plainly that the Cargo Make setup is currently broken and that the author has not fixed it, so the manual cd plus cargo creusot why3 ide route is what you have to use for now. That admission matters for anyone evaluating the project, because the proof is the selling point and the shortest path to reproducing it does not work.

Even on the manual path the result depends on your machine. The author reports everything being proved in about five minutes on a 2019 MacBook Pro, and suggests tweaking why3.conf, which is checked into the repository, if your hardware is slower.

Three solvers in one workspace, two of them simpler

The repository is a workspace with several members, and the interesting part is that it does not contain only one solver. The Cargo manifest lists CreuSAT, Robinson, Friday, JigSAT, Scratch, tests and NewDB as members, with CreuSAT, Robinson and Friday set as the default members for the Creusot metadata.

Friday is described as a fully verified and super naive SAT solver, and Robinson as a fully verified DPLL based solver. Both are pointed at as easier to understand, both algorithmically and proof-wise, which makes them the sensible starting point for learning Creusot. A reader trying to understand what a verified solver looks like would struggle more with CreuSAT's CDCL machinery and more with Friday's deliberately naive approach.

JigSAT is the unverified solver, described as being based on CreuSAT and used for experimenting with optimizations. That is a coherent division of labour: you try an optimisation in the unverified solver, and only move it into the verified one once you are confident and willing to pay for the proof.

The other directories are support structures. NewDB is a playground for ironing out the clause database design, Scratch is a temporary space for experimenting with proof machinery, mlcfgs holds generated configuration and Why3 session output, prelude is a copy of the Creusot prelude included so that cargo make works, and tests holds the test directory.

There is also a StarExec target, where the cargo make commands produce a creusat.zip or a jigsat.zip ready for upload to the StarExec clusters, which is the route to running large scale experiments on distributed infrastructure.

A thesis project with no release stream

CreuSAT is the code that came out of a master thesis, and the repository is organised around that fact. The thesis PDF is listed first among the interesting directories, the citation block gives both BibLaTeX and BibTeX forms, and both cite the University of Oslo thesis record. The thesis is also offered as the recommended introduction to Creusot, program verification and SAT solving together, for anyone who wants the reasoning rather than just the artefact.

The licence is MIT, which is permissive for academic code and appropriate if you want to build on the solver or reuse the verification structure in your own Rust project.

What is missing is release engineering. The repository publishes no GitHub releases, and the last push was on 2026-08-20. There is no versioned artifact to depend on, no changelog, and no stability statement about the verification setup, so adopting CreuSAT means tracking a branch and pinning a commit, with the proof obligations changing underneath you when the upstream Creusot standard library moves. The workspace pins creusot-std to a specific git revision of the Creusot repository, which is a hint that this coupling is already a real maintenance concern rather than a hypothetical one.

The upshot is that CreuSAT is a good artefact to read, study and prototype with, and a poor dependency to bet a production pipeline on.

Editorial conclusion

Adopt CreuSAT if you need a SAT solver whose verdict you can defend to a reviewer, for instance in a program verification pipeline where an UNSAT result is being used as evidence, or as a teaching artifact for Creusot. Do not adopt it if you need a fast production solver, a documented CLI contract, or a maintained release stream, because the feature set is a classic CDCL core with no releases published and the last push was on 2026-08-20. Before you build on it, run cargo test --release on your own hardware, and reproduce the proof yourself with cargo creusot why3 ide rather than trusting the thesis claim of the fastest deductively verified solver.

Frequently asked questions

Official sources

1. Issues
2. License: MIT
3. README
4. sarsko/CreuSAT on GitHub