💻 computer science

What does it take to certify a conversion checker?

This paper argues that injectivity properties, rather than normalization, are the crucial and sufficient foundation for certifying decision procedures for definitional equality in dependent type theory, including for fully untyped conversion checkers.

Original authors: Meven Lennon-Bertrand

Published 2026-07-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Meven Lennon-Bertrand

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a digital fortress, a place where you can write down mathematical proofs and be absolutely certain they are true. To keep this fortress safe, you need a tiny, super-strict guard at the gate called a "proof assistant." This guard's only job is to check if the proofs you hand in are valid. If the guard makes a mistake, the whole fortress could crumble, so we need to be 100% sure the guard is doing its job correctly. This is the world of dependent type theory, a branch of computer science and logic where types (like "number" or "list of numbers") can depend on specific values, making them incredibly powerful but also incredibly tricky to manage.

The core problem the guard faces is called conversion checking. Imagine you have two sentences that look different on the surface, like "2 + 2" and "4." To the guard, these need to be recognized as the exact same thing. In the complex world of dependent types, figuring out if two things are "the same" is like trying to untangle a knot of infinite strings. Usually, to prove the guard is working, mathematicians try to prove that the strings will eventually untangle themselves completely (a property called normalization). However, there's a famous rule in logic (Gödel's second incompleteness theorem) that says you can't prove a system is safe from the inside if that proof requires the system to be perfect. It's like trying to lift yourself up by your own bootstraps. So, the big question has been: Can we certify the guard without needing to prove that impossible "perfect untangling"?

This paper, written by Meven Lennon-Bertrand from the University of Cambridge, answers that question with a resounding "yes," but with a twist. Instead of relying on the heavy, often impossible task of proving that everything eventually untangles, the author shows that the guard only needs to be really good at one specific trick: injectivity.

Think of injectivity like a master detective who can look at a complex disguise and instantly know the ingredients. If the guard sees a "function" (a machine that takes an input and gives an output) and two of them look the same, injectivity guarantees that their internal parts (the inputs and the rules) must also be the same. It's the difference between seeing two identical-looking robots and knowing for a fact that they were built with the exact same blueprints, not just that they happen to look alike. The paper proves that if the guard is certified to be a perfect detective for these parts (injectivity), it is enough to certify that the guard is trustworthy for almost everything, even without proving the impossible "perfect untangling."

The author also explores a second, more chaotic version of the guard: one that doesn't look at the "types" (the labels) at all, just the raw shapes of the terms. It's like a guard who ignores the name tags on people and just checks if their shoes and hats match. Surprisingly, the paper finds that this "untyped" guard can also be certified, provided it follows the same detective rules, though the rules for the "shoes and hats" need to be slightly different depending on whether the items are simple or complex.

The paper doesn't just suggest this; it provides a formal, computer-checked proof (using a tool called Rocq) that these ideas work. It shows that by focusing on these "detective" properties (injectivity) rather than the "untangling" properties (normalization), we can build a certified, trustworthy guard. This is a big deal because it means we don't need to solve the unsolvable problem of proving the system is perfectly consistent to have a safe proof assistant. We just need to prove the guard is good at spotting the right ingredients. The paper also notes that while this works for most standard types, there are some very weird, "unit-like" types where things get messy, and the guard might need extra help, but for the vast majority of cases, the detective approach is the key to unlocking certified software.

Technical Summary: What does it take to certify a conversion checker?

Problem Statement
The certification of proof assistant kernels (the core components responsible for checking proofs) is a critical challenge in dependent type theory. While the "de Bruijn criterion" allows trust to be placed in a small kernel, certifying the kernel itself is difficult because dependent type theories rely on complex invariants. Specifically, proving the correctness of a conversion checker (which decides definitional equality, $\sim=$ ) traditionally requires proving the system's normalisation (termination of reduction). However, due to Gödel's second incompleteness theorem, a system cannot prove its own consistency or normalisation. Consequently, full certification of a dependently-typed kernel within the system itself is unfeasible. The paper seeks to identify the minimal meta-theoretic properties required to certify conversion checkers without relying on a full normalisation proof, aiming for "graceful failure" where the checker is certified based on weaker, provable properties.

Methodology
The authors adopt a modular approach, separating the meta-theory (the "opaque toolbox" of properties like injectivity and normalisation) from the algorithmic certification (the implementation of the checker).

Formal System: The work is formalized in the Rocq proof assistant (formerly Coq) for a version of Martin-Löf Type Theory (MLTT) featuring dependent function ( $\Pi$ ) and pair ( $\Sigma$ ) types, inductive types (empty, natural numbers, identity), and a universe, all with large elimination.
Algorithms: Two conversion checking algorithms are implemented and certified:
- Typed Conversion: A type-directed, bidirectional algorithm similar to those in Coq and Agda, which maintains type information throughout the check.
- Untyped Conversion: A term-directed algorithm similar to those in Rocq and Lean, which does not maintain type information during the reduction of terms but relies on a typed specification for correctness.
Certification Framework: The algorithms are implemented using McBride's free recursion monad (via PartialFun) to handle partiality. The authors define preconditions (invariants) and postconditions for the algorithms. Correctness is decomposed into:
- Positive Soundness: If the algorithm returns "yes," the terms are convertible.
- Negative Soundness: If the algorithm returns "no," the terms are not convertible.
- Termination: The algorithm always halts.

Key Contributions
The paper's primary contribution is the identification and demonstration that injectivity properties of type and term constructors are the crucial and sufficient meta-theoretic properties to certify the soundness of conversion checkers, largely independent of normalisation.

Injectivity as the Core Requirement: The authors show that injectivity of type constructors (e.g., if $\Pi x:A.B \sim= \Pi x:A'.B'$ , then $A \sim= A'$ and $B \sim= B'$ ) and no-confusion (e.g., $\Pi x:A.B$ cannot be convertible to $N$ ) are sufficient to prove positive soundness.
Term-Level Injectivity: To prove negative soundness, the authors demonstrate that injectivity properties for term constructors (specifically for natural numbers and $\Pi$ types) and the completeness of neutral comparison (ensuring that convertible neutrals can be structurally compared) are required.
Untyped vs. Typed Equivalence: The paper presents a novel certification of an untyped conversion checker against a typed specification. It clarifies that "untyped" conversion is effectively "term-directed typed conversion," where type information is implicit in the invariants rather than explicit in the reduction steps.
Dependency Analysis: By using type classes in Rocq, the authors provide a fine-grained dependency map (Figure 1 in the paper) showing exactly which meta-theoretic properties (Injectivity, Normalisation, etc.) are needed for each algorithmic property (Soundness, Termination).

Results
The formalization (adding ~10k lines of code to the existing Rocq base) yields the following specific results:

Positive Soundness: Proven for both typed and untyped algorithms using only the injectivity of type constructors. This property does not imply logical consistency and can be proven in a meta-theory weaker than the object theory.
Negative Soundness: Proven using injectivity of type and term constructors plus the completeness of neutral comparison.
- For the typed algorithm, completeness of neutral comparison is only required at positive types (Property 9).
- For the untyped algorithm, completeness is required at all types (Property 7), due to the lack of type information guiding the $\eta$ -expansion of negative types.
Termination: Proven for both algorithms assuming deep normalisation (Property 11). This property is the only one that implies logical consistency and requires a meta-theory stronger than the object theory.
Equivalence: The authors prove that the typed and untyped algorithms are equivalent (Propositions 22 and 24). The proof relies on strengthening (removing irrelevant variables from the context) and normalisation. The untyped algorithm is shown to be a valid implementation of the typed specification.

Significance and Claims
The paper claims that the "keystone" of certifying a type checker is not the full normalisation proof, but rather the injectivity properties of the type system.

Graceful Failure: The authors argue that even if normalisation cannot be proven (due to Gödelian limitations), one can still certify the soundness of a checker. This allows for the certification of complex, optimized implementations (like those in Rocq or Lean) by assuming injectivity as an axiom or proving it in a weaker meta-theory.
Modularity: The work advocates for a "meta-theory as a black box" approach. The certification of the algorithm should depend only on a small set of axiomatized properties (injectivity, completeness of neutrals) rather than a monolithic proof of the entire type theory.
Untyped Certification: The paper demonstrates that certifying term-directed (untyped) checkers is feasible and that the distinction between typed and untyped conversion is less about the absence of types and more about the direction of the algorithm (term-directed vs. type-directed).
Limitations: The authors modestly note that their work covers a simplified version of MLTT. They acknowledge that features like definitional unit types (where all inhabitants are convertible) or strict propositions (proof irrelevance) complicate the completeness of neutral comparison, requiring specific strategies (like re-inferencing types or universe tracking) in real-world kernels. They also note that extensional and cubical type theories present further challenges regarding strengthening and neutral completeness.

In summary, the paper provides a roadmap for certifying conversion checkers by isolating injectivity as the sufficient condition for soundness, thereby decoupling the certification of the algorithm from the difficult task of proving full normalisation.

Technical Summary: What does it take to certify a conversion checker?

More like this