AlphaProof Code: DeepMind's Lean proofs of Signal's PQXDH and Triple Ratchet code

Google DeepMind says its new AlphaProof Code system has produced machine-checked proofs about the security of Signal's messaging protocol, tied to the compiled code that runs on a device rather than to a paper description of the design. The work, announced on 10 November 2026, covers Signal's post-quantum PQXDH handshake and its Triple Ratchet for one-to-one chats, and took about four weeks according to DeepMind. It comes with a long list of stated assumptions, and it is worth reading what is and is not proved before treating it as a seal of approval for the Signal app.

Key points

• DeepMind's AlphaProof Code, a multi-agent framework using Gemini Carbon agents, produced Lean proofs about Signal's PQXDH handshake and Triple Ratchet, announced 10 November 2026.
• The proofs target a specific binary: libsignal-cli built from unmodified libsignal v0.105.4 and spqr v1.6.0, per the project's repository.
• The agents wrote about 6.5 million lines of Lean (DeepMind's blog says "over six million"); about 26,000 lines of specifications and machine semantics must be trusted, and Lean's kernel checks the rest.
• Key generation is not verified, group messaging is future work, and the computational proof covers only classical (non-quantum) attackers.
• DeepMind says the work took about four weeks; it calls this the first formal verification of a widely deployed protocol's implementation by any method, a claim we have not independently confirmed.

What happened

On 10 November, Google DeepMind published a post by Pushmeet Kohli and Swarat Chaudhuri introducing AlphaProof Code, which it describes as an agentic framework for formal verification: mathematically proving that code does what a specification says. Humans decide what is to be proved. Agents then do the proofs in Lean, a proof assistant whose small kernel checks every step.

DeepMind describes three stages. First, researchers used a mix of models to translate Signal's security goals into formal specifications, and human experts reviewed every one. Second, agents powered by Gemini Carbon generated the proofs. Third, an audit step flagged the parts needing human review, which DeepMind puts at about one percent of the codebase, while Lean checks the rest automatically.

The Register, which covered the announcement, says the verified material is Signal's PQXDH handshake and Triple Ratchet, and that the properties checked include forward secrecy, authentication, post-compromise security and handshake secrecy. DeepMind's own example is keeping messages protected before and after a device is temporarily compromised.

To test whether the system could catch real mistakes, DeepMind says the team reintroduced two real, previously fixed bugs into an isolated copy of Signal's code. In both cases the system produced a machine-checked proof that the buggy version was insecure. The post does not name the bugs and does not report any new bugs found in Signal.

Signal's chief technology officer, Ehren Kret, is quoted on DeepMind's page as saying that using AI agents to translate live code into valid Lean theorems is "a major breakthrough."

Background

Formal verification of security software is old and expensive. The Register compares the effort with the seL4 microkernel, which took about 20 person-years, and the CompCert compiler, which took six years. Proofs about a design on paper are different from proofs about the code that ships, and that gap is what this work targets.

In April 2026 the Beneficial AI Foundation and the Lean FRO announced "Signal Shot", a challenge to the community to formally verify the Signal protocol and app, at the Software Verification in Lean workshop in Paris, according to a post by the security firm Cryspen. The Register describes DeepMind's work as a step toward that challenge. Cryspen said it would take part, together with the team behind Aeneas, a Rust-to-Lean translation tool.

We have covered related proof-checking work: Anthropic's FlashProve and a Lean-checked proof claim on the Aaronson-Ambainis conjecture.

How it works

The project's repository, published by DeepMind, is more precise than the blog about what was proved.

The target. The proofs are about libsignal-cli, an AArch64 Linux executable built with stock rustc 1.98.1 from unmodified libsignal v0.105.4 and spqr v1.6.0, statically linked with musl. The theorems cover the init, send and recv operations. The repository says plainly that keygen is not verified: the theorems take the parties' keys as part of their setup.

Two proofs. There is a symbolic proof, in the Dolev-Yao style, with ten theorems, and a computational proof. The symbolic one covers a quantum attacker who breaks Diffie-Hellman after the handshake. The computational one covers only classical adversaries.

What must be trusted. Because the proofs are about machine code, the Rust source and the compiler are not trusted. What is trusted is Lean's kernel, about 18,000 lines of Lean specifications, and about 8,000 lines of AArch64 semantics and symbol names (the repository puts the semantics itself at 7,578 lines covering 467 instructions and 31 system calls), for roughly 26,000 trusted lines. It also trusts contracts for 37 "hooked" routines, including the cryptographic primitives (SHA-2 compression, AES-256-CBC, X25519, Kyber1024, ML-KEM-768 and HMAC), some libc routines and file writers. The roughly 6.5 million lines of generated proof are untrusted because Lean checks them. The team tested its machine semantics against the Unicorn emulator, the Sail Armv9.4-A model and qemu-aarch64.

Assumptions. The symbolic proof assumes idealised primitives: hashes and message authentication codes do not collide, secrets do not repeat and signatures cannot be forged without keys. The computational proof relies on standard hardness assumptions such as Gap-DH and XEdDSA unforgeability, along with an authentic public-key infrastructure with pinned identity keys.

What it means

For people who build secure messaging, the main change is the cost. Years of expert effort became about four weeks for a team that Register puts at five people (DeepMind's page credits nine authors), plus a large amount of model compute. If that holds up for other code, formal verification stops being something only a few flagship projects can afford. DeepMind itself suggests medical device firmware and power grid software as later targets, and says scaling "requires continued research."

Chaudhuri told The Register that the next frontier is not proof but specification. That is the right place to look: the 26,000 trusted lines are exactly the part where a mistaken statement of "secure" would pass unnoticed, which is why humans reviewed them.

For Signal users, nothing changes today, and the result is not a statement that the app is unbreakable. The proofs are about one build of a command-line client, on one CPU architecture, for two-party sessions. The repository says Android and iOS apps are assumed to behave like the tested binary but are not verified.

What we don't know yet

• Independent review. The proofs are machine-checked, but the specifications, semantics and hooked contracts are trusted. We have not seen outside reviewers' assessment of them.
• How much was automated. DeepMind says the agents wrote the proofs and about one percent of the codebase needed human audit, but the figures for human hours are not in the sources we read.
• Whether the "first" claim holds. DeepMind says this is the first time AI has verified a widely deployed cryptographic protocol at this depth, and the first formal verification of a widely deployed protocol's implementation by any method. Those are the company's claims.
• Real-world findings. The post reports only the two reintroduced bugs. It does not say whether the process uncovered anything new.
• Known gaps. The repository lists replay-based loss of forward secrecy as not ruled out, one-time Kyber prekeys as not covered, and multi-device state as out of scope.

What to watch next

Watch for outside review of the repository and the technical paper "Formal Verification of Signal", for the extension to group messaging, which the repository calls future work, and for how the Signal Shot challenge responds. Also watch whether Signal adopts the specifications in its own testing, and whether other projects apply the same approach to their code.

Sources

• Google DeepMind: Introducing AlphaProof Code (primary)
• DeepMind code-verification project page and repository
• The Register: Google DeepMind melds humans and AI agents to vet Signal's secure messaging techniques
• Cryspen: Software Verification in Lean 2026