Google DeepMind's AlphaProof Code Formally Verifies Signal's libsignal

Proof instead of testing

Testing and audits can show that no flaw was found, but not that none exists. Formal verification instead proves, as with a theorem, that code cannot violate certain properties. The method is notoriously expensive: verifying the seL4 operating system kernel, completed in 2009, took the equivalent of twenty person-years.

Here, human experts defined what to prove, drawing on academic work about Signal, and the agents, running on Gemini 4 Carbon, wrote about 6.5 million lines of proof in the Lean language, whose checker validates every step automatically. According to the researchers, none of them wrote a line of proof themselves.

The proofs target the "ratchet", the mechanism that constantly renews encryption keys. They establish that an attacker who steals the keys stored on a phone cannot read earlier messages, since each key is derived from the previous one and then erased. They also show that a conversation becomes secure again once both parties exchange new messages, and that nobody can impersonate either participant. To check the method, the team reintroduced two old, since-fixed libsignal bugs, and the system showed those versions no longer met the guarantees.

Clear limits

Signal's chief technology officer Ehren Kret called it "a major advance". Google nonetheless lists caveats: the proof covers only two-person conversations, assumes the underlying cryptographic building blocks work perfectly without verifying them, and applies to a test version running on Linux, not the mobile apps.

The authors draw a broader lesson: now that proofs are getting cheap, the hard question becomes what to prove.