Lean Kernel Soundness Bug #14576 Fixed After AI-Assisted "Disproof" of Collatz Conjecture

Discovery and Fix of Kernel Bug

A soundness bug, identified as #14576, in the Lean theorem prover's kernel was reported and subsequently fixed during the week of July 27. The issue gained visibility across various platforms, including Zulip and social media. The fix was implemented swiftly, within an hour of the bug's report, and new patch releases are now available.

How the Bug Was Exploited

On July 25, Ramana Kumar published a repository containing an AI-assisted "disproof" of the Collatz conjecture. This proof was not valid because it exploited the kernel bug. The bug specifically involved the kernel's handling of nested inductive types, where phantom parameters could disappear, allowing an ill-typed argument to be accepted as a proof of False. The vulnerability was only accessible through metaprogramming, as the frontend typically checks arguments and prevents such issues.

Nanoda's Role and Coincidental Bugs

The original Collatz repository also passed a week-old version of nanoda, an independent Lean kernel implemented in Rust. It was discovered that two distinct bugs were involved: the official Lean kernel's missing check in nested inductive type support, and a separate bug in nanoda where it did not verify the type name in a projection node. The nanoda bug was reported and fixed a week before the Lean kernel bug was reported. This situation highlights that while independent checking remains effective, users need current versions of both the main kernel and external checkers to ensure soundness.

Impact and Resolution

The kernel bug is an implementation flaw, not a fundamental hole in Lean's meta-theory. The rapid identification and resolution of the bug, along with the release of new patch versions, reinforce the integrity of the Lean theorem proving environment. Users of lean4lean are also affected by this kernel bug due to its handling of inductives, necessitating updates to ensure continued reliability.