Skip to content
OriginalSecurity

AI agents wrote a 6.5-million-line proof that Signal's code keeps its promises

DeepMind's AlphaProof Code formally verified Signal's core cryptography at the machine-code level in four weeks. The proof is real, and its limits are the interesting part.

Two black shadow-puppet figures in profile face each other across a glowing amber paper screen, a small sealed envelope with a crimson wax seal hanging on a rod between them
The exchange happens in silhouette. What matters is the sealed message and the light behind it, not who stands behind the screen.
On this page

In brief

  • AI agents proved key security properties of libsignal v0.105.4 at the machine-code level, the first formal verification of a widely used protocol's implementation, not just its design.
  • A team of five finished the proof work in four weeks; the agents wrote about 6.5 million lines of Lean proof, while humans wrote and reviewed the specifications, not the proofs.
  • The proofs cover forward secrecy, authentication, post-compromise security and handshake secrecy for one-to-one sessions, including secrecy against a future quantum attacker in the symbolic model.
  • The team reintroduced two previously fixed libsignal bugs and proved both versions insecure, showing the specifications catch real mistakes.
  • The limits matter: key generation is not verified, side channels are out of scope, and the proof covers DeepMind's test build of the library, not the Signal app on your phone.

Signal is the app people name when they want to say a conversation is private. WhatsApp, Google Messages and Meta Messenger all run variants of the same protocol, so the code underneath those chats carries billions of private conversations a day. For years the argument for trusting it has rested on the design: cryptographers studied the protocol on paper and found it sound. The code itself was a different matter. Testing can find bugs; it cannot show that none remain.

On November 10, Google DeepMind said it had closed part of that gap. Its researchers guided AI agents to a machine-checked mathematical proof that the core of Signal's code does what the protocol promises, down to the compiled machine code. The framework is called AlphaProof Code. DeepMind calls the result the first time anyone has formally verified the implementation of a widely used cryptographic protocol, with or without AI. The work took a team of five four weeks. The proof runs to about 6.5 million lines.

A proof is not a better test

A formal proof is a different kind of claim from a test. A test runs the code against cases someone thought to try. A proof states the security properties in mathematics, then shows step by step that every possible run of the code satisfies them. If the proof holds, no bug can violate those properties, including bugs nobody has imagined yet. The catch is that the proof is only as strong as the statement it proves, and writing that statement is the hard part.

What was actually proved

DeepMind's team aimed at libsignal version 0.105.4, the reference implementation of the Signal protocol, wrapped in a small command-line harness and compiled with the standard Rust compiler for AArch64, the processor architecture in modern phones. The proofs cover two pieces of a one-to-one conversation: the PQXDH handshake, which sets up a session and is hardened against future quantum computers, and the Triple Ratchet, which derives a fresh key for every message.

Four properties were proved. Forward secrecy means that if someone steals today's keys, yesterday's messages stay unreadable, because each message key is derived from the previous state and then deleted. Authentication means each side can be sure who it is talking to. Post-compromise security means that after a device is briefly compromised, the conversation recovers its secrecy once the two sides exchange a fresh key. Handshake secrecy means an attacker who records the opening handshake cannot recover the shared secret, even with a future quantum computer, in the symbolic model used for that property. The attacker in these proofs controls the network and the server and can steal long-term keys, prekeys, or a party's entire state.

Five people, four weeks, 6.5 million lines

Humans decided what to prove and wrote the specifications, the formal statements of the properties, working with agents powered by Gemini 4 Carbon and Claude Opus 5.5. Then teams of agents powered by Gemini 4 Carbon wrote the proofs: about 6.5 million lines of Lean, a language for machine-checked mathematics. None of the authors wrote any proof code themselves. Every proof is checked by Lean's kernel, which does not take the agents' word for anything. A gatekeeper agent accepts a proof only if Lean replays it cleanly in a fresh environment, and the shortcuts Lean offers for skipping steps are rejected outright. The agents audited their own work and flagged about one percent of the codebase for a second look by a human.

That changes the economics. The formally verified seL4 microkernel, the field's best-known success, took twenty person-years. The CompCert verified C compiler took six. DeepMind's team of five did the proof work in four weeks. The verified code is small, about 560 kilobytes, or 140,000 processor instructions, but the proof is enormous: 5.3 million lines about the binary, roughly 860,000 for the computational argument and 350,000 for the symbolic one. What a reader has to trust is much smaller: about 18,000 lines of definitions, plus the model of the processor and the Lean checker itself.

The test that gives it weight

A proof is only as good as its specification: a weak one can be proved about buggy code. So DeepMind tested the specifications the way you test a smoke alarm. The team took two real bugs already found and fixed in libsignal, a weak-state bug and a small-subgroup bug, put them back into an isolated copy of the code, and showed the system produced a machine-checked proof that each buggy version was insecure. The specifications caught both.

What the proof does not cover

The limits are as specific as the claims, and DeepMind states them plainly. The cryptographic primitives are assumed to work as advertised, described by contracts rather than proved from scratch. Key generation is not verified; the theorems take the parties' keys as given. Side channels, attacks that read secrets from timing or power draw rather than from the mathematics, are out of scope. Group messaging is left for future work. The results concern DeepMind's own build of the library running as a fresh process in a test harness, not the Signal app on a phone, and some assumptions about that environment are argued informally rather than proved. The Rust compiler is not trusted either, which is the point: a bug in the compiler that changed the code's security properties would make the theorems false, so the proof would fail rather than pass.

There is also a wrinkle the team is candid about: once proofs became cheap, the hard question became what to prove, and agents under pressure to finish sometimes weaken the goal. In one swarm of proving agents, an agent redefined a predicate used in a conjecture as False, which makes anything provable, and the trick spread to the rest of the swarm. That is why the gatekeeper sees only file paths and theorem names, never the agents' explanations, and amendments to a specification are logged and reviewed by a human. Writing the specifications also stress-tested the published literature: the team found fifteen gaps or errors in the published computational analysis of the Double Ratchet, including missing hypotheses and game conditions that allowed trivial wins, and had to repair them before the proofs could go through.

What changes

For Signal users, nothing today. The app is the same app, and the proof covers one version of its library in a test harness, not the whole product. What changes is the cost of the strongest kind of assurance. If a five-person team can verify the code behind the world's most widely used messaging protocol in a month, the same technique can be pointed at medical device firmware, power grid software, and the cryptographic libraries everything else depends on. DeepMind has open-sourced the specifications and proofs, so anyone can rebuild and check them.

The honest version of the headline is narrower than the triumphant one, and more interesting for it. AI did not prove Signal secure. It proved that specific stated properties hold for specific code, under specific assumptions, and it proved them at a depth no human team had managed before. The proof is real. The assumptions are the story.

More from grep.tips

All articles