In formal verification, there is a fundamental tension between expressiveness and automation. Interactive proof assistants (IPAs) like Lean and Isabelle allow mathematicians and software engineers to write highly expressive, foundationally secure proofs. These systems rely on a tiny, meticulously checked "kernel" to validate every logical step. However, manually guiding a proof assistant through thousands of tedious subgoals is incredibly slow.
To scale verification, modern toolchains delegate these computational burdens to high-performance automated solvers, such as Satisfiability Modulo Theories (SMT) solvers, SAT solvers, and specialized domain verifiers. This delegation creates a critical vulnerability known as the solver-to-kernel verification gap.
While the core logic of an IPA is formally verified, the external solvers it calls upon are massive, highly optimized C/C++ programs containing hundreds of unverified heuristics and rewrite rules. If an external solver contains a bug, it can silently validate an incorrect proposition, completely undermining the absolute certainty that formal verification aims to provide.
To resolve this recursive trust issue, researchers are developing mechanisms to bridge the gap between high-performance automation and foundational kernels.
The Anatomy of the Trust Gap
The vulnerability introduced by external solvers is not merely theoretical; it stems from several concrete architectural layers within automated reasoning pipelines.
Unverified Internal Simplifications
Modern SMT solvers rely on hundreds of algebraic and logical rewrite rules to simplify complex formulas before solving them. As Hanna Lachnitt et al. demonstrate in their work on IsaRare: Automatic Verification of SMT Rewrites in Isabelle/HOL, these rules are frequently implemented without formal verification. If a single rewrite rule is mathematically unsound, the solver can generate an invalid proof certificate that an unverified checker might still accept, rendering the final output untrustworthy.
The Translation Gap
Before an external solver can process a problem, the problem must be translated into a format the solver understands. For example, pseudo-Boolean (PB) constraints are often translated into the Conjunctive Normal Form (CNF) used by standard SAT solvers. Stephan Gocht et al. point out in Certified CNF Translations for Pseudo-Boolean Solving (Extended Abstract) that even if a SAT solver produces a certified proof log of its reasoning, errors introduced during the initial translation step can invalidate the entire solution.
Unverified Runtimes and Checkers
Even if a system's high-level mathematical logic is fully verified, it must ultimately execute on physical hardware via compilers, garbage collectors, and runtime environments. As Jared Davis et al. argue in A Verified Runtime for a Verified Theorem Prover, an unverified runtime system represents a massive, hidden expansion of the trusted computing base (TCB). Similarly, if the independent software used to check a solver's proof certificates contains defects, the validity of the entire proof chain remains compromised.
Mechanism 1: Native Proof Reconstruction
The most robust way to eliminate the solver trust gap is proof reconstruction. Instead of blindly trusting an external solver's "yes" or "no," the proof assistant forces the solver to output a detailed certificate of its execution steps. The proof assistant then attempts to replay and translate these steps back into its own native logical calculus, validating them directly within its trusted kernel.
[Proof Goal] ──> (Translation) ──> [External Solver (e.g., cvc5)]
│
(Proof Certificate)
│
▼
[Trusted Kernel] <── (Reconstruction) <── [Tactic Layer]
This approach is exemplified by tools like "hammers"—automated bridges between interactive and automated theorem provers. For instance, Yicheng Qian et al. developed Lean-Auto: An Interface Between Lean 4 and Automated Theorem Provers, which uses a novel monomorphization algorithm to translate Lean's complex dependent type theory into simpler first-order logic for SMT solvers.
Crucially, the ultimate goal of frameworks like Lean-Auto and lean-smt: An SMT Tactic for Discharging Proof Goals in Lean (developed by Abdalrhman Mohamed et al.) is to reconstruct the solver's output into machine-verified proof terms.
However, native reconstruction is exceptionally difficult. As Thomas Zhu et al. note in Premise Selection for a Lean Hammer, external solvers often optimize away fine-grained logical steps or use internal calculi that do not align with the proof assistant's kernel. When this alignment fails, the reconstruction tool cannot bridge the gap, and the proof fails to verify natively.
Mechanism 2: Formally Verified Checkers and Toolchains
When full proof reconstruction inside a proof assistant's kernel is computationally prohibitive or logically impossible, researchers turn to an alternative strategy: formally verifying the external tools themselves.
If a verification condition generator relies on an external solver, we can achieve end-to-end certainty by verifying the certificate checker down to the machine code. As Chung-Kil Hur et al. demonstrate with AliveInLean: A Verified LLVM Peephole Optimization Verifier, building the verification tool directly within a formal environment ensures that the verifier cannot incorrectly approve a buggy optimization.
To scale this to complex domains like graph theory, Stephan Gocht et al. developed an end-to-end verified toolchain for subgraph solving in End-to-End Verification for Subgraph Solving. By leveraging the CakeML ecosystem, the authors formally verified both the proof checker and the translation layers. This approach guarantees correctness from the high-level graph problem statement all the way down to the executable x86 machine code, successfully bypassing the need for native kernel reconstruction while maintaining absolute mathematical certainty.
A similar paradigm is emerging in deep neural network (DNN) verification. Because DNN verifiers are prone to numerical instability and implementation bugs, frameworks like the one proposed by Hai Duong et al. in Generating and Checking DNN Verification Proofs introduce verifier-independent proof formats. By checking these certificates with minimal, easily auditable, or formally verified checkers, developers can catch real-world bugs in state-of-the-art, unverified verifiers.
Achieving End-to-End Trust
As formal methods are increasingly applied to safety-critical domains—ranging from compiler optimization to machine learning systems (Daniel Selsam et al., Developing Bug-Free Machine Learning Systems With Formal Mathematics)—managing the trusted computing base becomes paramount.
The research direction outlined across these works shows that high-performance automation does not have to come at the expense of foundational trust. By developing sophisticated proof reconstruction tactics, verifying translation steps, and certifying proof checkers down to machine code, the formal methods community is successfully closing the gap between external solvers and trusted kernels.
Key Foundational Work
A Verified Runtime for a Verified Theorem Prover (2011) — contributed 3 concept elements to this direction.
A Model Checker for Verifying ConGolog Programs (2002) — contributed 1 concept elements to this direction.