zlib × Lean
Machine-checked Lean 4 proofs about a statement-by-statement translation of zlib: every documented public function of the default x86_64 Linux build is safe, with no undefined behaviour, no memory error, no leak, and termination, under the premises each theorem states.
Results
The first three are the safety results; the fourth is a functional result. Each one is done or not done.
- 1done
inflateis safe on every input: no undefined behaviour, no memory error, no leak, and it terminates, for every sequence of calls on a stream and every split of the buffers.statements:
inflate_safety·inflate_sequence_safety - 2done
deflateis safe on every input, for every sequence of calls on a stream.statements:
deflate_safety·deflate_sequence_safety - 3done
Every other documented public function is safe:
compress*anduncompress*, the other stream functions, the checksums, the gzip file interface and the callback decoderinflateBack.statements:
compress_safety·uncompress_safe·gz_sequence_safety·gz_refusal·inflate_back_sequence_safety· the goal of every function - 4done
The round trip of the default zlib stream:
uncompress(compress(x)) = x, and compressing withdeflateInitat the default level anddeflatecalls with any flush value, finished bydeflate(Z_FINISH)calls, and then decompressing withinflateInitgives back the input, for every split of the buffers.statements:
compress_uncompress_roundtrip·stream_roundtrip_total
Done: a Lean theorem whose statement is exactly the goal exists and passes every check of the project. Not done: there is no such theorem.
That the translation and the runtime model match the C is reviewed and tested, not proved: see the trusted base. The conditions a call must meet are in the deviations. What a done result rests on is in its own page.
Read zlib first
- A complete codec: LZ77 and Huffman
A complete small codec: repeated passages, Huffman codes, how the rules are transmitted, and how decoding ends. It starts from
ABABABABand rebuilds the core of DEFLATE. - Implementing and optimizing zlib
How zlib actually implements and tunes deflate and inflate: window, hash chains, match search, table lookup and copying. The deepest article.
- Extending zlib: streams and integrity
Streaming, dictionaries, wrappers, Adler-32, CRC-32 and the application interface: why complete buffers are not enough.
Reference
- Status of the results: done or not done, for each result and each function
- Specifications: safety goals, API contracts, formats, trusted base and deviations
- Proofs: method and the argument for each component
- Glossary