> your AI agent picks dependencies from memory; give it dated facts — try starlog.dev ↗ vet your agent's deps ↗ vibe-coding is fine. vibe-importing isn’t. — try starlog.dev ↗ vibe-importing isn’t fine ↗ your agent has never seen your private packages — try starlog.dev ↗ facts for private packages ↗ a linter for the dependencies your AI agent picks — try starlog.dev ↗ a linter for agent deps ↗ whois is redacted, cdns mask the rest — get the real operator — try whoisgeni.us ↗ who really runs that domain ↗ domain attribution that shows its work — full evidence chain — try whoisgeni.us ↗ domain intel w/ evidence ↗

← Back to Articles

Inside Rocq: How a 10K-Line Kernel Guards Mathematical Truth

[ View on GitHub ]

Inside Rocq: How a 10K-Line Kernel Guards Mathematical Truth

Hook

The entire correctness guarantee of the verified CompCert C compiler—used in safety-critical aerospace systems—rests on roughly 10,000 lines of OCaml code. If you're trusting your life to formally verified software, you're betting on Rocq's kernel.

Context

Proof assistants occupy a strange corner of software development: tools for writing mathematical proofs that a computer can verify mechanically. When you formalize a theorem in Rocq, you're not just writing documentation—you're constructing a proof object that gets checked by a type system so expressive it can encode arbitrary mathematical statements. The Calculus of Inductive Constructions underlying Rocq lets you represent everything from simple arithmetic facts to the four-color theorem to full functional correctness of a C compiler.

But here's the problem: proof automation is complicated, buggy code. Tactics that search for proofs, decision procedures that solve goals automatically, plugins that integrate SMT solvers—all of this is tens of thousands of lines of potentially flawed logic. Early proof assistants faced a dilemma: how do you build powerful automation without trusting it? Rocq's answer is the LCF architecture, borrowed from the ML family of provers. Every proof, no matter how it's constructed, must ultimately produce a proof term that passes through a small, auditable kernel. The tactics can be wrong, the plugins can crash, you can even integrate a large language model—but if the kernel rejects the proof term, it doesn't count.

Technical Insight

Trusted Core

proof commands

constructs

submits for validation

provides context

provides context

type matches theorem

rejects if invalid

User Proof Script

Tactics Layer

Untrusted

Proof Term

Lambda Calculus + CIC

Trusted Kernel

~10K LOC

Type Checker

Conversion Algorithm

Weak-Head Normalization

Global Environment

Definitions & Axioms

Valid Proof

System architecture — auto-generated

Rocq's architecture splits into two worlds: the untrusted outer layer where tactics live, and the paranoid inner kernel that validates everything. When you write a proof script, tactics in the outer layer manipulate proof goals and construct proof terms—λ-calculus expressions in the Calculus of Inductive Constructions. These terms then get submitted to the kernel for type-checking. If the term has the right type (which corresponds to the theorem statement), the proof is valid. Otherwise, it's rejected, no matter how clever your tactics were.

The kernel itself is remarkably simple in concept: it's a type checker for dependent types plus a conversion algorithm. Here's what a proof term looks like at the kernel level:

(* A proof that forall n : nat, n + 0 = n *)
fun (n : nat) => 
  nat_ind 
    (fun n => n + 0 = n)           (* Property to prove *)
    (eq_refl 0)                     (* Base case: 0 + 0 = 0 *)
    (fun (k : nat) (IH : k + 0 = k) => (* Inductive case *)
      eq_ind_r (fun x => S x = S k) (eq_refl (S k)) IH)
    n

This is actual kernel-level representation using de Bruijn-free names for clarity. The kernel checks that nat_ind (the induction principle for natural numbers) is applied correctly, that the types line up, and that the base and inductive cases have the right types. Critically, the kernel doesn't care how this term was generated—maybe you wrote it by hand, maybe a tactic script produced it, maybe an AI hallucinated it. Only the final type-checking matters.

De Bruijn indices replace named variables inside the actual kernel. Instead of fun n => n + 0, you'd see fun _ => #0 + 0 where #0 means "the zeroth bound variable." This makes α-equivalence (renaming) trivial—terms are equal if their de Bruijn representations are identical—but it makes debugging kernel code brutal since #0 #1 (#2 #0) is meaningless to humans. The trade-off is deliberate: the kernel prioritizes machine-checkable correctness over developer experience.

The conversion algorithm is where performance engineering meets type theory. In dependent type systems, type-checking requires comparing types for equality, but types can contain arbitrary computations. The kernel uses weak-head normal forms: it reduces terms just enough to check if they're the same constructor, without fully normalizing. For example, checking if 2 + 2 equals 4 requires reducing 2 + 2 to S (S (S (S O))) but not necessarily evaluating every subterm. The kernel maintains a conversion cache and uses universe constraints efficiently—there's a sophisticated algebraic system tracking which universes are strictly smaller than others, enabling universe polymorphism without actually generating infinite universe levels.

Here's where it gets interesting for practical verification: the kernel provides a native compilation path. You can extract verified Rocq code to OCaml, which then gets compiled to native code. This means your proofs about algorithms can become production executables:

Fixpoint insert {A : Type} (cmp : A -> A -> comparison) 
  (x : A) (l : list A) : list A :=
  match l with
  | nil => x :: nil
  | h :: t => 
    match cmp x h with
    | Lt => x :: l
    | _ => h :: insert cmp x t
    end
  end.

(* Prove it produces sorted lists *)
Theorem insert_sorted : 
  forall A cmp x l, 
    sorted cmp l -> sorted cmp (insert cmp x l).

(* Extract to OCaml *)
Extraction "insertion.ml" insert.

The extracted OCaml code drops all the proof parts—only the computational content remains. What you get is an insert function backed by a machine-checked correctness proof, compiled to native code with competitive performance. CompCert uses this extensively: the verified C compiler is extracted from Rocq proofs and runs fast enough for practical use.

The module system creates interesting kernel challenges. Rocq allows opaque constants—definitions whose bodies are hidden from type-checking for abstraction. But the kernel still needs access to the global environment to look up definitions, check module constraints, and resolve universe levels. This creates a tension: deep module hierarchies mean more environment lookups during type-checking, slowing down kernel operations. Recent work has focused on optimizing environment representation and lazy loading of module components, but fundamentally the kernel can't be stateless—it needs global context to validate proofs.

Gotcha

The LCF architecture's paranoia has a cost: proof term explosion. When tactics generate proofs automatically, they often construct massive proof objects—think megabytes for proofs that a human would write in a few lines. The kernel has to type-check all of this, which can take seconds or even minutes for heavily automated proofs. Worse, these large proof terms make caching difficult: Rocq has to recheck dependencies when files change, and if your proof terms are huge, that rechecking becomes a bottleneck. There's no magic solution because the proof terms genuinely encode all the reasoning—compression would require trusting the decompression algorithm, breaking the LCF model.

The tactic language situation remains frustrating. Ltac, the original tactic language, is dynamically scoped, interpreted, and has minimal debugging support. Writing complex tactics feels like programming in 1970s Lisp without a REPL. Ltac2 fixes many issues with lexical scoping and better performance, but adoption is slow because rewriting existing tactic libraries is a massive undertaking. Meanwhile, proof automation lags behind systems like Isabelle—there's no default hammer tool that throws multiple automated provers at your goal. You'll frequently find yourself manually breaking down proofs that would be automatic in other systems, especially for goals involving arithmetic, set theory, or routine logical reasoning. The ecosystem has tools like lia for linear arithmetic and nia for non-linear integer arithmetic, but they're not as integrated or powerful as Isabelle's Sledgehammer or Lean's omega and simp tactics.

Verdict

Use Rocq if you're building verification projects where a soundness bug would be catastrophic—aerospace software, cryptographic implementations, compiler correctness, or formalizing core mathematics where the entire edifice rests on foundations. The ecosystem is unmatched: MathComp for abstract algebra, VST for C verification, extensive formalized real analysis and topology. Choose it when you need the certainty that comes from a battle-tested kernel and a community that's been stress-testing the foundations for decades. Skip Rocq if you're doing exploratory research where iteration speed matters more than absolute guarantees—Lean 4's metaprogramming is far more ergonomic for rapid prototyping. Skip it if you need heavy automation out of the box; Isabelle will save you hours of manual proof work. Skip it if your verification needs are domain-specific and narrow; tools like F* for crypto or ACL2 for hardware provide better tailored automation. The Coq-to-Rocq rename creates temporary ecosystem confusion, but the fundamentals haven't changed: this is the proof assistant for when you absolutely, positively cannot have a soundness hole.