Google says AlphaProof Code verified 6.5 million proof lines for Signal

• Selected security properties of Signal’s compiled code received 6.5 million lines of Lean proofs in four weeks, according to the reported results.
• The target was machine code, with the Rust compiler outside the trusted base, as rohanpaul_ai explains.
• AI generated the proofs; Lean checked them against human-approved specifications, following the verification workflow.
• Two reintroduced, previously fixed bugs produced machine-checked proofs of insecurity, according to the research recap.

Proof workers faced a held-out specification comparison, a clever guardrail against silently weakening the goal. Researchers also found errors in published Signal security analyses. Their machine-code model covers 467 instructions and 31 system calls.

Google DeepMind’s November 10 announcement concerns an executable built from unmodified Signal protocol code inside a small command-line harness. The published repository pins the target to:

• libsignal-protocol v0.105.4.
• The spqr v1.6.0 crate.
• Stock Rust compiler rustc 1.98.1.
• A statically linked AArch64 Linux executable.

The proofs follow execution through the protocol state machines, parsing and memory allocation, with selected routines represented by trusted contracts. Because the theorems concern emitted instructions, the Rust compiler falls outside the trusted computing base.

The guarantee belongs to the exact binary being proved, a boundary also highlighted in Hacker News discussion.

Human experts reviewed every formal specification before proof generation, according to DeepMind’s announcement. Agents subsequently flagged about 1% of the codebase for additional human scrutiny.

The technical paper separately identifies approximately 26,000 lines that readers must trust:

• About 18,000 lines of specification statements and definitions.
• About 8,000 lines of AArch64 execution semantics.

The results also depend on Lean’s kernel, assumptions about cryptographic primitives, and contracts for routines outside the verification scope. The machine semantics must faithfully describe hardware and operating-system behavior.

Specification writing used both Gemini 4 Carbon and Claude Opus 5.5, with drafts reviewed by agents from a different model family, according to Sysnote’s breakdown of the paper. The proof code was generated entirely by Carbon agent teams; the authors reported writing none themselves.

AlphaProof Code uses general-purpose coding agents configured through natural-language skill documents. The paper’s agent architecture divides responsibilities into:

• Orchestrator: decomposes work and schedules agents without editing Lean files.
• Team leads: manage longer-running goals and summarize completed lemmas, remaining obligations and blockers.
• Proof workers: solve assigned subtasks.
• Architect: designs and revises the overall proof decomposition.
• Integrator: merges verified proofs and consolidates reusable lemmas.

Team leads absorb worker conversations so the orchestrator receives compact summaries. Agents also attempt to falsify goals before spending resources proving them.

Five researchers worked for four weeks, each running agents continuously on a workstation, according to Sysnote’s account. Individual proof campaigns used 40 to 80 agents for 24 to 72 hours; most human effort went into specifications.

Google compares the four-week project with years of expert labor using earlier tools. That is a historical comparison, not a measured speedup against a parallel human team.

A gatekeeper accepts a proof only after Lean’s kernel checks it and a comparator confirms that it proves the approved specification. The repository’s comparator checks cover the theorem statement and every transitive definition it depends on.

The safeguards include:

• A held-out specification copy that proof workers cannot edit.
• Acceptance restricted to standard Lean axioms.
• Rejection of proof shortcuts such as sorry and native_decide, as detailed in Sysnote’s analysis.
• Review of proposed specification amendments, with human approval required for changes to trusted assumptions.

These checks prevent a worker from completing its assignment by quietly redefining the security property into something easier to prove.

The security theorems cover Signal’s PQXDH handshake and Triple Ratchet, establishing:

• Forward secrecy.
• Post-compromise security.
• Message confidentiality and authentication.
• Handshake secrecy.

The team produced two independent security arguments:

1. Symbolic: cryptographic primitives behave as idealized black boxes, following the Dolev–Yao model.
2. Computational: an efficient attacker’s success is bounded through assumptions about the hardness of attacking the underlying primitives.

Both arguments connect protocol-level properties to the compiled executable.

The paper’s scope and limitations, collected in Sysnote’s analysis, leave several concrete boundaries:

• Cryptographic implementations: 37 routines use trusted contracts, including cryptographic primitives and selected runtime helpers.
• Key generation: the keygen command is outside the proofs; parties’ keys are supplied as inputs.
• Messaging topology: coverage concerns one-to-one sessions between two parties. Group messaging and multi-device state remain outside scope.
• Quantum guarantees: the computational proof covers classical attackers. The symbolic proof covers handshake secrecy against a future quantum attacker; neither proof establishes the post-quantum healing properties added by SPQR.
• Execution environment: the CLI runs as a fresh process with a fixed clock, 1 GiB of memory beyond loaded segments and an 8 MiB stack. Side channels are excluded.
• Application builds: carrying the results to Android and iOS requires trusting that those builds preserve the protocol code’s behavior.

The computational bound also reflects Signal’s eight-byte truncated MAC. Under a workload where nearly every message begins a new epoch, the bound becomes vacuous at roughly 25,000 messages in one session. That describes a limit of the bound, not a demonstrated attack.

DeepMind reintroduced two previously fixed Signal bugs and obtained machine-checked proofs that both modified binaries were insecure.

The historical fixes addressed:

1. Archived-session state: processing a prekey message that decrypted only under an archived session could store state containing a copy of the signed prekey secret.
2. Small-subgroup handling: the initiator’s X25519 base key lacked a torsion check.

Both experiments refuted the symbolic security theorem for the buggy binary. The project reported no new vulnerabilities in libsignal.

Translating published research into Lean exposed mistakes in the security statements themselves. The team documented more than 200 departures from prior work or implementation details on the computational side and about 35 on the symbolic side, according to Sysnote’s review.

Most were routine adaptations. The substantive corrections included:

• Double Ratchet analysis: 15 gaps or bugs, including missing hypotheses and security-game conditions permitting trivial wins.
• Published ProVerif queries: a skipped-message-key lookup at the wrong ratchet index, an unbound variable and an overly permissive post-compromise-security statement.
• PQXDH analysis: wording that, read literally, made one corollary unprovable.

These findings concerned published formalizations, with no reported corresponding attacks on Signal.

Google opened Carbon to paying API customers and began rolling it out to AI Ultra subscribers the same day, according to the model’s launch post. Signal verification featured among the internal long-horizon workloads highlighted in the launch announcement.

Separate early coding experiments included ivanleomk’s proposed two-hour Carbon run around Ember, a self-hosted runtime for AI agents.

The public verification repository includes the specifications, proofs, binary-building scripts and checking tools. Its README documents:

• Pinned tools: Lean 4.34.0 and Rust 1.98.1, with exact compiler output required by the generated Lean representation.
• Build requirements: several hours and roughly 15 to 34 GiB peak RAM for the default proof check.
• Binary identity: scripts/cli-elf-stock rebuilds and verifies the SHA-256-pinned AArch64 executable.
• Independent replay: comparator checks export proofs and replay them in a fresh Lean kernel.
• Sandboxing: the comparator workflow requires Linux and uses Landlock through landrun.

The authors reported that early in the project, small source changes or a recompiled binary required large proof repairs, according to Sysnote’s account.