AlphaProof Code Proves Signal Properties Down to Machine Code

Google DeepMind's AlphaProof Code generated about 6.5 million lines of Lean proof covering roughly 140,000 AArch64 instructions in a four-week effort. A team of five did the proof work, and none of its members wrote proof code. Agents powered by Gemini 4 Carbon produced that code.

DeepMind's paper compares the effort with verifying the seL4 microkernel, which took 20 person-years. The company did not disclose the compute cost.

DeepMind introduced the multi-agent framework on Tuesday to prove four security properties in libsignal, the reference implementation of the Signal protocol. The proof reaches the machine code that runs on devices. The protocol also protects messages in Signal and, in variant forms, WhatsApp, Messenger and Google Messages.

What did the system prove?

The guarantee spans Signal's post-quantum PQXDH handshake and its Triple Ratchet. Four security properties sit within that guarantee.

• Forward secrecy.
• Authentication.
• Post-compromise security, meaning messages stay protected after a device is temporarily compromised.
• Handshake secrecy.

DeepMind says these are the first proofs connecting protocol-level security guarantees to unmodified code in a widely used cryptographic implementation. Signal chief technology officer Ehren Kret said: "Using AI agents to translate live code into valid Lean theorems is a major breakthrough." He added that earlier formal verification covered smaller portions of the code.

The result links four stated properties to the executable code, rather than certifying the entire messaging service.

How did five people handle millions of proof lines?

The team compiled unmodified libsignal v0.105.4 and the spqr v1.6.0 crate with the standard Rust compiler into AArch64 Linux machine code. They linked the result into a small command-line harness and loaded the executable into Lean alongside a formal model of AArch64.

Specification-writing agents worked with people to adapt published Signal security models into Lean. Agents powered by Gemini 4 Carbon and Claude Opus 5.5 drafted and reviewed those models, and people approved each one.

Teams of prover agents powered by Gemini 4 Carbon then wrote the proofs. A gatekeeper accepted them only when Lean's kernel checked each proof against a held-out copy of the approved specification.

A reader must still trust about 18,000 lines of specifications and about 8,000 lines of AArch64 semantics. The agents also flagged roughly one percent of the codebase for human review, according to DeepMind's blog.

Humans approved the specifications, while agents produced the proofs and identified the code needing closer review.

Did the system catch real bugs?

The researchers reintroduced two previously fixed libsignal bugs to test whether the specifications would detect real flaws. One involved weak state, while the other omitted a small-subgroup check from the PQXDH responder.

The team then proved in Lean that binaries containing those defects violated the security theorem. The paper reports no new vulnerabilities in libsignal.

Writing the specifications also exposed errors in published analyses, including 15 gaps or bugs in a computational analysis of the Double Ratchet. Those findings concern the earlier analyses, not a fresh weakness in the library.

The test showed that the specifications reject known failure modes, but the paper found no new libsignal vulnerability.

What does the proof leave unresolved?

The guarantees cover one-to-one sessions only. Group messaging remains for later, and the work did not verify key generation or side channels.

The symbolic proofs assume perfect cryptography, and the computational bounds offer no guarantee against a quantum adversary. The ratchet theorems show that the Triple Ratchet is no weaker than the Double Ratchet, but they do not prove the post-compromise healing that SPQR adds.

The results also depend on trusting Lean's kernel, the cryptographic primitives, and contracts for some routines that the executable calls. That trust boundary leaves the underlying assumptions outside the automated proof.

The guarantee covers specific one-to-one properties under stated assumptions, not the whole application or every threat.

What changes for cryptographic verification?

Academic researchers previously verified the PQXDH protocol design with automated tools in 2024. The new work applies formal proofs to the compiled libsignal implementation rather than only the design.

DeepMind has published the complete Lean development, specifications and proofs at google-deepmind.github.io/code-verification. The project follows other DeepMind work that applied AI agents and Lean to security and science, including cheaper attacks on legacy 1024-bit RSA and Lean-checked savings in quantum algorithms.

The next competitive test is whether this workflow can extend to group messaging, which the team has left for later.