When we use formal verification to prove that a self-driving car will not crash, or that a cryptographic protocol is secure, a fundamental question arises: Why should we trust the verification software itself?
Theorem provers, model checkers, and static analyzers are large, complex pieces of software. If a verification tool contains a single implementation bug, it might mistakenly approve a flawed system, rendering its safety guarantees worthless. As Barrett et al. demonstrated in their work on CVC Lite, completely redesigning a verification system from the ground up to streamline its architectural complexity can shrink a codebase to one-third of its original size. This reduction highlights a core insight in modern computer science: to maximize trust, we must minimize the Trusted Computing Base (TCB)—the critical core of code that must be correct for the system's output to be reliable.
To achieve a minimal TCB, researchers have converged on a powerful architectural paradigm: separating the complex process of finding a proof from the simple process of checking it. By routing all final logical steps through a tiny, highly scrutinized microkernel, we can eliminate the need to trust massive automation engines.
Eliminating Axiom Schemata via Uniform Substitution
Historically, one of the largest sources of code bloat and soundness bugs in theorem provers has been the management of variables and axioms. In traditional logic systems, provers rely on axiom schemata—infinite templates where placeholders are replaced with concrete formulas. For example, a standard schema might state that if $\phi$ is true, then $\psi \rightarrow \phi$ is true, for any arbitrary formulas $\phi$ and $\psi$.
The danger lies in the implementation. To ensure that substituting a formula into a template does not accidentally cause variables to clash or get captured by a quantifier (a notorious source of soundness bugs), the theorem prover must execute complex, hard-coded "side-condition checkers." Every new axiom schema requires its own custom side-condition logic, causing the TCB to expand continuously.
In a series of foundational papers, Platzer introduced a solution to this problem: the Uniform Substitution Calculus. Instead of using infinite axiom templates with complex side-conditions, the prover is restricted to a finite set of concrete axioms and a single, centralized uniform substitution engine.
Traditional Approach (Bloated TCB):
[Axiom Schema 1] -> [Custom Side-Condition Checker 1] \
[Axiom Schema 2] -> [Custom Side-Condition Checker 2] +---> Inside the TCB
[Axiom Schema N] -> [Custom Side-Condition Checker N] /
Uniform Substitution Approach (Minimal TCB):
[Finite Concrete Axioms] -> [Single Uniform Substitution Engine] ---> Inside the TCB
As detailed in A Uniform Substitution Calculus for Differential Dynamic Logic and its complete extension, A Complete Uniform Substitution Calculus for Differential Dynamic Logic, this architecture centralizes the variable-binding logic into a single engine. To ensure this mechanism remains performant without sacrificing safety, Platzer introduced a "one-pass" uniform substitution algorithm in Uniform Substitution at One Fell Swoop. By utilizing "taboo sets" to track variable dependencies, the algorithm replaces expensive, recursive admissibility checks with a single-pass mechanism that operates in linear time.
By applying this paradigm across different logics—including recent work by Platzer et al. on Differential Refinement Logic—the core logic of a theorem prover can be shrunk by orders of magnitude into a sound-critical microkernel.
The LCF Approach: Building Usability on Top of a Microkernel
If the core kernel is kept minimal, how can a theorem prover support the complex, high-level reasoning required for real-world verification? The answer lies in the LCF approach, named after the landmark Logic for Computable Functions system.
In an LCF-style architecture, the microkernel exposes a small set of primitive logical inferences as an abstract data type. High-level automation features, user interfaces, and proof search strategies (often called "tactics") sit entirely outside the kernel. If a high-level tactic contains a bug, it might fail to find a proof, but it can never generate an invalid proof, because every inference must ultimately be validated by the primitive rules of the microkernel.
This architecture scales to extraordinary heights. For instance, Hales et al. utilized this exact approach in A FORMAL PROOF OF THE KEPLER CONJECTURE. By routing a massive, computer-aided mathematical proof involving thousands of pages and complex datasets through the minimal kernels of HOL Light and Isabelle, the trust model was shifted away from fallible human peer review to a tiny, highly scrutinized set of logical axioms.
Similarly, Mitsch demonstrated in Implicit and Explicit Proof Management in KeYmaera X how user conveniences like lemmas, parametric proofs, and delayed substitutions can be built as high-level layers. The underlying safety-critical code remains completely untouched.
As analyzed by Mitsch et al. in the ARCH-COMP18 Category Report, this architectural choice involves a deliberate trade-off:
| Architecture | TCB Size | Performance on Simple Tasks | Robustness & Extensibility |
|---|---|---|---|
| Monolithic / Large Rule Sets | Large (Bloated) | Fast (Direct execution) | Low (High risk of soundness bugs) |
| Minimal Kernel / LCF | Small (Lean) | Slower (Overhead of kernel routing) | High (Mathematically sound foundation) |
Shifting Trust via Proof Certificates and Reductions
For many verification domains, such as industrial model checking or Satisfiability Modulo Theories (SMT) solving, rewriting the entire tool into an LCF-style microkernel is computationally impractical. These solvers rely on highly optimized, volatile heuristics to traverse massive search spaces.
To minimize the TCB in these domains, researchers use independent certificate verification. Instead of trusting the solver to declare a result true, the solver is required to output a lightweight, independently verifiable mathematical "certificate" of its findings.
+-----------------------------------+
| Complex, Unverified Solver |
| (Optimized heuristics, volatile) |
+-----------------------------------+
|
v
[ Lightweight Certificate ]
|
v
+-----------------------------------+
| Minimal, Verified Kernel |
| (Independently validates) |
+-----------------------------------+
|
v
[ Sound Result ]
This strategy is highly effective for complex probabilistic systems. Schäffeler et al. applied this to Markov Decision Processes (MDPs) in Fixed Point Certificates for Reachability and Expected Rewards in MDPs. Rather than trusting a large-scale MDP model checker, they designed a system where the checker emits elementary fixed-point certificates. These certificates are then independently validated by a small, formally verified kernel generated inside a proof assistant.
A major challenge arises when certificates become too complex for a simple checker to process. For example, SMT solvers handle intricate domain-specific theories (like network topology or hardware bit-vectors) that standard propositional logic checkers cannot understand. Creating specialized, theory-aware proof checkers would bloat the TCB all over again.
To bypass this bottleneck, Hu et al. introduced a reduction technique in DRAT Proofs of Unsatisfiability for SAT Modulo Monotonic Theories. By transforming complex, theory-specific lemmas into simple Horn approximations, they allowed complex SMT results to be expressed as pure propositional proofs. This breakthrough enables standard, theory-unaware, mechanically verified propositional proof checkers (such as DRAT checkers) to validate the results, keeping the TCB remarkably small.
In-Kernel Domain Customization
A final, elegant strategy for minimizing the TCB is to embed domain-specific verification tools directly inside an existing, highly trusted proof assistant like Lean, Coq, or PVS.
By implementing a verifier as a program inside the proof assistant's environment, developers can use the assistant's native capabilities to prove the verifier's internal logic correct. This approach was successfully executed by Hur et al. in AliveInLean: A Verified LLVM Peephole Optimization Verifier. Instead of relying on a standalone, unverified tool to check LLVM compiler optimizations, the authors built the verifier inside Lean. As a result, the TCB immediately shrinks to just Lean's core kernel; if Lean's kernel is sound, the optimization verifier is guaranteed to be sound.
Similarly, Xu et al. demonstrated in Generically Automating Separation Logic by Functors, Homomorphisms and Modules that complex memory-reasoning frameworks can be formalized using abstract algebra within a proof assistant. By certifying the automation engine itself, the derived reasoning rules are mathematically sound by construction, requiring the user to trust nothing more than the foundational proof assistant.
Whether applied to hybrid systems, hardware verification, or compiler design, the underlying philosophy remains identical: by engineering systems that isolate logical correctness from algorithmic automation, we can construct verification tools that are both profoundly powerful and fundamentally trustworthy.
Key Foundational Work
A Uniform Substitution Calculus for Differential Dynamic Logic (2015) — contributed 1 concept elements to this direction.
Reconstructing Trust Management (2004) — contributed 1 concept elements to this direction.
CVC Lite: A New Implementation of the Cooperating Validity Checker Category B (2004) — contributed 1 concept elements to this direction.