Minimal Trusted Kernels for Formal Verification

This direction is split into other directions: trusted computing base minimization. Its last version stays readable and citable here.

Version 1 of 136 papers48 conceptsfrozen 2026-10-04

When a computer checks a mathematical proof or verifies the safety of a self-driving car, we are essentially asking one piece of software to vouch for another. This creates a "who watches the watchmen" problem: if the verification software itself contains a bug, the "proven" safety claim is worthless.

To solve this, researchers have converged on a specific architectural pattern: the Minimal Trusted Kernel. Instead of trusting a million lines of complex code, the system is designed so that every logical conclusion must pass through a tiny, auditable core of just a few hundred lines.

The Soundness Gap

In traditional automated verification, the "Trusted Computing Base" (TCB)—the set of all code that must be correct for the result to be valid—is often massive. For example, early computer-aided proofs of the Kepler conjecture were met with skepticism because they relied on thousands of lines of custom code that no human could fully audit.

As Thomas C. Hales and John Harrison demonstrated in the Flyspeck project, the solution is to shift the trust model. By routing all inferences through a small logical kernel (using systems like HOL Light or Isabelle), they transformed a controversial computer result into a machine-checked mathematical certainty. The validity of the proof no longer depends on the entire search algorithm, but only on the integrity of the core logical primitives.

The Microkernel Architecture

This philosophy, often called the LCF (Logic for Computable Functions) approach, separates the "brains" of the system from the "judge."

  1. Tactics and Automation: These are complex, high-level programs that search for proofs. They can be messy, aggressive, and even buggy.
  2. The Kernel: This is the only part of the system allowed to declare a theorem "proven." It only understands a few fundamental rules of logic.

Jeremy Avigad highlights this in his work on the foundations of interactive theorem provers. By isolating the kernel, researchers like Stefan Mitsch can develop advanced user interfaces and automated debugging tools without risking the underlying logical correctness. If a high-level tactic makes a mistake, the kernel simply rejects the resulting step.

Uniform Substitution: Shrinking the Core

A major challenge in keeping kernels small is the use of "axiom schemata"—templates that represent infinite sets of rules. Implementing these templates safely is difficult because of "variable capture," a subtle bug where variables in a proof accidentally clash with variables in a rule.

André Platzer introduced a breakthrough mechanism to solve this: Uniform Substitution. In papers like Uniform Substitution at One Fell Swoop, Platzer shows that you can replace hundreds of complex, template-based rules with a small set of concrete axioms and a single, highly-optimized substitution operator.

This architectural shift allows for "microkernels" in theorem provers like KeYmaera X. By centralizing the logic for preventing variable capture into one pass, the trusted core can be reduced by orders of magnitude, making it feasible to formally verify the prover's own kernel.

Beyond Pure Mathematics

The minimal kernel approach is now being applied to safety-critical engineering:

  • Neural Networks: To trust a Deep Neural Network (DNN), Hai Duong and colleagues developed APTPchecker, an 800-line tool that independently validates the massive outputs of complex DNN verifiers.
  • Compilers: Chung-Kil Hur and Nuno P. Lopes built AliveInLean, which verifies LLVM compiler optimizations by reducing them to the core kernel of the Lean theorem prover.
  • Security Monitors: In hardware security, the Sanctorum project by Ilia A. Lebedev uses a ~1,000-line software layer to create secure enclaves on RISC-V processors, offloading complex resource management to an untrusted OS while keeping the security-critical isolation logic minimal and auditable.

By shrinking the source of truth to a minimal, verifiable kernel, these systems achieve a level of certainty that human peer review or traditional testing cannot match. Whether proving the Prime Number Theorem or securing blockchain scaling foundations, the goal remains the same: reduce the world's complexity to a few hundred lines of undeniable logic.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_minimal_trusted_kernels_for_formal_verif_91b39c63,
  title = {Minimal Trusted Kernels for Formal Verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimal-trusted-kernels-for-formal-verification/rdr_91b39c6327884e6ab08a4304c3ab6a3d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_minimal_trusted_kernels_for_formal_verif_91b39c63_v1,
  title = {Minimal Trusted Kernels for Formal Verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimal-trusted-kernels-for-formal-verification/rdr_91b39c6327884e6ab08a4304c3ab6a3d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}