R038 · AI-built software and its verification › Formal methods for AI-written code

AlphaProof Code: agents formally verify Signal's protocol implementation

Read the original

formal-verificationai-built-softwaremulti-agenthuman-oversighttest-oracles

Sources: Elvis Saravia's LinkedIn post; DeepMind blog, 2026-11-10; technical report and Lean development (Chaudhuri, Ferraiuolo, Kovsharov, Chajed, Schlesinger, Seth, Katz, Sutton, Kohli); paper PDF; code.

In one paragraph

Google DeepMind used a multi-agent framework, AlphaProof Code, to prove security properties of libsignal (Signal's Rust reference implementation) against the compiled AArch64 binary, not the source or a protocol model. Agents built on Gemini 4 Carbon produced about 6.5 million lines of Lean proof resting on about 26,000 lines of trusted specification and machine semantics. A team of five did the proof work in four weeks; seL4, the usual comparison, took about twenty person-years. The proofs cover the post-quantum PQXDH handshake composed with the Triple Ratchet, in both a symbolic and a computational model: forward secrecy, authentication, post-compromise security and handshake secrecy. When two previously fixed Signal bugs were reintroduced into an isolated copy, the system produced machine-checked proofs that the buggy versions were insecure. The authors claim it is the first proof linking protocol-level guarantees to the unmodified code of a widely deployed crypto implementation.

The core idea: specs are trusted, proofs are not

The design rests on one split. The specification (Lean theorem statements plus every definition they depend on, including the machine semantics and contracts for hooked routines) is trusted and cannot be checked automatically, so a flaw there silently weakens the guarantee. The proof is untrusted: Lean's kernel rejects any logical error, so the reliability of the result does not depend on the reliability of the agents that wrote it. The paper's claim is that proof writing is no longer the bottleneck; specification engineering is, and that is where humans stay.

Architecture

What is and isn't covered

Tradeoffs and open questions

Why it matters for engineering teams

Checklist if you want to apply the pattern

Connections

See R038 on the knowledge map

Part of the Research notes on nowucca.com. Figures and claims are the source's own unless the summary says otherwise.