6.5 Million Lines of Proof Rest on 26,000 Lines You Have to Read

In short
Key takeaways
- The proofs cover libsignal linked into a small command-line harness and compiled with stock rustc to AArch64 Linux machine code, in both the symbolic and the computational model.
- The four properties are forward secrecy, authentication, post-compromise security and handshake secrecy; the handshake secrecy claim is against a future quantum attacker and is made in the symbolic model.
- About 6.5 million lines of Lean proof rest on roughly 26,000 trusted lines, about 18,000 of specification and definitions plus about 8,000 of AArch64 semantics.
- Two previously fixed libsignal bugs were reintroduced, and the resulting binaries were proved in Lean to violate the symbolic security theorems.
- The project took four weeks, against twenty person-years for seL4 and six for CompCert, though those figures cover whole verification projects and are not like for like.
- The cryptographic primitives were assumed secure in the computational proof and idealized in the symbolic proof, so the result is conditional on them.
About 6.5 million lines of Lean proof sit between Signal's compiled AArch64 binary and the four security properties Google DeepMind says it established about it. On 10 November 2026 the lab published a technical paper, a blog post and a public Lean development making that claim, and the claim is narrower and stranger than the coverage that followed.
The implementation is libsignal, which the paper calls the Signal protocol's reference implementation. It was linked into a small command-line harness and compiled with the stock rustc compiler to AArch64 Linux machine code. Nothing in the source was changed to make the proof go through. Proofs were produced in both the symbolic model, where cryptography is idealized and the attacker follows Dolev-Yao rules, and the computational model, where security is argued against standard cryptographic assumptions.
Signal variants are deployed in WhatsApp, Meta Messenger and Google Messages, which the paper describes as protecting billions of conversations. That deployment is why the result matters: a proof about a protocol model is a familiar artefact, and a proof about the instructions that run on a phone is not.
What was verified
The paper's own phrasing is "the first proofs connecting protocol-level security guarantees to the unmodified code of a widely deployed cryptographic protocol implementation." Each clause is load-bearing. Previous formal work on Signal targeted abstract protocol models, or reimplementations written to be easy to verify, or implementations modified for the purpose, or narrower properties such as crash-freedom.
The modification clause is the interesting one. Verification of pre-existing industrial code is harder than verification of code written for the exercise, because the prover cannot reshape the program to suit the proof. libsignal carries years of engineering decisions that exist for reasons unrelated to provability. The team had to prove the thing that already shipped.
The paper also makes a second, stronger first: that this is the first time the implementation of a widely deployed protocol like this has been formally verified by any method, with or without AI. The AI framing is the one the announcement leads with. The second claim is the one that would still matter if the agents were removed from the story.
The four properties
The proofs cover Signal's post-quantum PQXDH handshake and the Triple Ratchet, and establish four properties:
- Forward secrecy: a compromise of long-term key material does not expose earlier sessions.
- Authentication: a message accepted as coming from a party was produced by that party.
- Post-compromise security: a session recovers its security after an attacker has held key material for a period.
- Handshake secrecy: the handshake does not hand an eavesdropper the material needed to read the session.
The quantifiers differ across the four, and the difference is easy to lose in a summary. Forward secrecy, post-compromise security, message confidentiality and message authenticity are proved against classical attackers. Handshake secrecy is proved against a future quantum attacker, and in the symbolic model rather than the computational one. So the post-quantum claim is real and narrower than "Signal is post-quantum secure", which is a statement about primitives this paper does not verify.
Why the compiled binary is the hard part
A proof about Rust source code says nothing about the instructions a phone executes. Between them sit optimisation passes, inlining, register allocation, linking and memory layout, any of which can turn correct-looking source into a binary that behaves differently.
The blog post frames the target as the gap between design and implementation, which is where real-world vulnerabilities tend to live. That framing is a fair description of the threat model.
Proving the machine code moves the boundary. What has to be trusted is no longer "the compiler preserves the meaning of this Rust", which is an enormous and mostly unchecked assumption, but the semantics of the instruction set, about 8,000 lines of Lean describing AArch64 and its symbol names. That is a smaller and more inspectable assumption, and the one the paper asks a reader to accept.
Two models were run rather than one, so the result is not exposed to the complaint that symbolic proofs ignore computational subtleties or that computational proofs are too concrete to mechanize. The symbolic proof idealizes the primitives as opaque tokens and shows that no sequence of attacker rules yields the secret. The computational proof reduces the construction's security to standard hardness assumptions.
Six and a half million lines nobody has to trust
The number the announcement leads with is the number that matters least.
| Artefact | Approximate size | Status |
|---|---|---|
| Lean proof corpus | 6,500,000 lines | untrusted, checked by Lean |
| Specifications and definitions | 18,000 lines | trusted, human review |
| AArch64 semantics and symbol names | 8,000 lines | trusted, human review |
The proofs are untrusted in a technical sense, not a dismissive one. Lean's kernel checks every step, and a logical error anywhere in those 6.5 million lines is rejected rather than silently accepted. Nobody has to read them, because a machine already did, which makes the corpus size a measure of work done rather than a measure of risk carried.
The specification is the opposite. It defines what "correct" means, and no tool can check whether it says the right thing. A weak specification yields a valid proof of a weak statement, and the proof will look exactly as convincing as a strong one. Section 2.1 of the paper states this directly: the specification must be trusted and cannot be automatically checked, and a flaw in it could weaken the guarantee the theorem provides.
That leaves about 26,000 lines a specialist has to read. The paper's argument is that most of the human effort in software verification now lies in engineering the specification, and the arithmetic supports it. Twenty-six thousand lines is not a weekend, but it is a quantity a small number of people can audit in a way that six and a half million is not.
Three assumptions sit outside both numbers, and the authors name them. Lean's kernel is assumed correct, which is the load-bearing assumption of all machine-checked mathematics and not specific to this project. The cryptographic primitives are assumed secure in the computational proof and idealized in the symbolic one, so the primitives libsignal uses were not re-verified. And some routines the executable calls are described by extern contracts, which are human-written assumptions that no tool checks.
The check that could have failed
A verification effort that cannot detect a known-bad binary is not verifying anything. The team built that test in.
Two previously fixed libsignal bugs were reintroduced into the code, and the resulting binaries were proved in Lean to violate the symbolic security theorems. Both bugged versions were proven insecure. This is the correct negative control, and it rules out the failure mode where a specification is vacuously true and everything passes for the wrong reason.
It does not establish everything a sceptic might want. Two bugs are a small sample, and they are historical, so they are defects the original authors already understood and fixed. It does not show that the specifications catch a novel class of attack, because no specification can exclude an attack outside the class it defines. What it shows is that the specifications are not empty.
The workflow has a second guard in the same spirit. A gatekeeper agent accepts a proof only if Lean's kernel checks it and a Lean comparator confirms the proof establishes exactly a held-out copy of the specification, so a prover cannot quietly satisfy a weaker or different statement than the one a human approved. Prover agents may propose amendments when a specification turns out to be vacuous or wrong, but those require a user-set policy or explicit human judgment.
What four weeks does and does not mean
The Signal verification took four weeks. Agents generated over six million lines of Lean, and agent auditing highlighted about one percent of the codebase for a second look by a human. The agents were powered by Gemini Carbon.
The comparison figures in the paper are seL4 at twenty person-years and CompCert at six. The contrast is dramatic and it is not like for like. Both baselines are whole verification projects, specifications included, and neither was a re-verification of a protocol with decades of published formal analysis to draw on. The paper does not claim the ratio transfers.
The one percent figure needs the same care. It measures the audit of the generated proof, not the work that produced and approved the 18,000 lines of specification. That work is the larger part of the project and it is not the number the announcement leads with. The paper says a good specification took many rounds of iteration between the user and the agents, and that AI assistance can reduce the cost of specification writing but cannot replace human judgment and review. Four weeks is elapsed project time for a team that already knew the Signal literature, not the cost of doing this for an arbitrary protocol.
What the proof does not establish
"The cryptographic primitives are secure" is an assumption, not a result. This is standard practice and not a defect, but it sets the boundary: the theorem says the compiled code preserves the guarantees of the protocol given correct primitives, not that the primitives are correct.
The result is about one implementation, one architecture, one build. libsignal, stock rustc, AArch64 Linux. Other builds, other architectures and other implementations of the protocol are not covered. The sentence "Signal is verified" should be read as "this binary of libsignal, built this way, satisfies these properties", which is a real claim and a much smaller one.
The specification is a human artefact adapted from existing published models for Signal and extended, with human guidance, to cover the protocol as deployed, including the post-quantum ratchet those older models predate. That is reasonable and it is also a scope limit: the properties proved are the properties of the literature, extended where the literature had not caught up.
The extern contracts are the weakest link, and they are the part a sceptic should press on. They are assumptions about routines the executable calls, written by a human and checked by nothing. Their volume and quality determine how much of the guarantee Lean actually established versus how much someone asserted. The paper points to Section 5.3 for the Signal-specific trusted computing base.
Where this could be wrong
Nothing here is independently verified. The paper is a self-report by the team that did the work, published alongside the artefacts, and no other group has reproduced the Signal proof. Lean's kernel correctness is assumed, as it is across the whole field. This is not a defect of the paper; it is the state of the art, and it means the correct description of the result is "a machine-checked proof exists and its authors published it", not "the result has been confirmed".
The trusted base may be larger than 26,000 lines. Sections 4, 5 and 6 of the paper were not read end to end for this account, and Section 5.3, which holds the contracts on called routines, was not examined at all. If those contracts cover more than a thin interface, the claim that a reader can audit the result shrinks in proportion. The figures quoted above come from the abstract and Section 1, both of which state them explicitly.
The six and a half million figure measures a corpus, and a corpus can inflate. If it includes boilerplate, generated scaffolding or rejected proofs rather than accepted proof, the measure of work changes even though the proof does not. The paper says about 6.5 million lines and the blog says over six million; they are compatible, and neither is a count of anything a reader can check without opening the repository.
The "four weeks" comparison should not be turned into "twenty person-years became four weeks". No person-hour count, no count of specification iterations and no breakdown of the four weeks was published in the material read here. The baselines are whole projects, the comparison is not controlled, and the specification phase, which is the expensive part, has no separate cost attached to it.
The repository is one commit old, at 808b4b7, with nine contributors. That is what a paper release looks like, not what a maintained project looks like. Anyone planning to build on the Lean development should expect to read close to what the authors had on release day, not a living artefact with downstream patches.
Finally, the AI framing may be incidental to the result. If a non-AI verification of libsignal appears, the framework's contribution would be speed rather than feasibility, and the interesting claim would revert to the narrower one: that unmodified industrial cryptographic code can be verified at the machine-code level at all. That claim would survive. The attribution would need rewriting.
On this page
Sources
- AlphaProof Code: Verifying Signal's Security at the Machine-Code LevelSwarat Chaudhuri, Andrew Ferraiuolo, Anton Kovsharov, Tej Chajed, Sam Schlesinger, Karn Seth, Jonathan Katz, Charles Sutton, 2026
- Introducing AlphaProof Code: a breakthrough in verifying complex software at depthPushmeet Kohli and Swarat Chaudhuri, 2026
- google-deepmind/code-verificationGoogle DeepMind, 2026
- AlphaProof Code: the Lean developmentGoogle DeepMind, 2026
Frequently asked questions
What exactly was verified?
libsignal, the Signal protocol's reference implementation, linked into a small command-line harness and compiled with the stock rustc compiler to AArch64 Linux machine code. The source was not modified to make the proof easier. Proofs were produced in both the symbolic (Dolev-Yao) model and the computational model.
Why does machine code matter more than source code?
A proof about Rust source says nothing about what the compiler emitted. Optimisation, inlining, register allocation, linking and memory layout all sit between the source and the instructions that run, and the paper frames the gap between design and implementation as where real vulnerabilities tend to hide. Proving the compiled binary closes that gap.
What is the trusted base?
About 18,000 lines of statements and definitions that a reader must read and trust, plus about 8,000 lines of AArch64 semantics. Added to that are Lean's kernel, the assumed security of the cryptographic primitives, and the contracts of some routines the executable calls. The 6.5 million lines of proof are not in the trusted base.
Does this mean Signal is proven secure?
No. It means this build of libsignal, on this architecture, satisfies these four properties given correct cryptographic primitives. The primitives were not re-verified, one architecture was covered, and parts of the executable are described by human-asserted contracts that no tool checks.
Was a known-bad binary tested against the specifications?
Yes. Two previously fixed libsignal bugs were reintroduced, and the resulting binaries were proved in Lean to violate the symbolic security theorems. That is a negative control: it shows the specifications are not vacuous, though two historical bugs is a small sample.