A week to prove zlib: verification stops being the expensive half

An AI-assisted translation of the C compression library zlib into Lean, carrying a machine-checked proof that compressing data and then decompressing it returns the original input, was completed in roughly a week, according to a full interview transcript with Lean's creator published on dev.to ^[1][3][4]. The interesting number is not the week; it is that the proof stopped being the expensive half of the job, since the same interview puts the historical cost of writing and maintaining proofs by hand at around ten times the cost of writing the program ^[9].

The project was started by Kim Morrison, described in the interview as a colleague of the host. The brief was to move zlib into Lean, pass the original test suite, and prove the round-trip property ^[3]. What remains, per the same account, is performance work, and that work is fenced: the optimizations must not break the existing proofs ^[4]. That fence is the actual deliverable. A test suite tells you the cases someone thought of still pass, and corner cases can still be missing ^[5]; a proof covers every input, which is what turns rewriting a hot loop from a gamble into a mechanical exercise. The interview makes that point directly: with a property proof underneath, engineers stop fearing aggressive rewrites, because equivalence can be proved or a counterexample produced ^[17].

The reusable trick here is the specification strategy. Rather than formalising the format from a standards document, you take a slow but obviously correct implementation as the spec, then have the model generate the fast version and prove the two equivalent ^[7]. That relocates the hard part. You are no longer buying a formal description of DEFLATE; you are declaring a reference implementation to be the definition of correct and paying for equivalence. The interview is candid that the effort of writing a good spec varies substantially from program to program ^[21], and that is where the residual cost now sits.

There is industrial precedent for treating Lean as ordinary engineering infrastructure. The interview describes an internal AWS compiler for an AI accelerator running to roughly 500,000 lines of Lean, used mainly as a programming language with property proofs as a by-product ^[11], and names Jane Street among firms investing in verification, alongside the full verification of the seL4 microkernel ^[8].

Two caveats an operator should hold. First, the trust base: Lean's shipped kernel is not itself verified, though Mario Carneiro built a kernel in Lean called Lean for Lean and proved it consistent with Lean's semantics, and third-party kernels exist in Rust and other languages ^[14]. A high-performance kernel runs about 5,000 lines, small enough to rewrite, and external kernels can print each proved theorem with its full dependency list ^[15]. "Proven" means a proof term type-checks against something that small, not that the artifact is beyond suspicion. Second, this is one interview transcript; it names no public repository and reports no benchmark figures for the Lean zlib ^[23].

For scale calibration, the same source describes a separate result: OpenAI produced an informal proof of the unit distance conjecture, Morrison posted it as a formalization challenge, and OpenAI's Boris Kusolovic completed a roughly one-million-line Lean formalization in under two weeks ^[18], an average of at least about 71,000 lines a day ^[22].

What to watch: whether the optimized zlib lands with its proofs intact and with published timings against the C original; whether the slow-spec-plus-equivalence pattern holds for code whose correctness is not a clean round trip; and the cost curve, given that the labs only began putting Lean verification into their reinforcement learning pipelines in the last year or two ^[19].