[KongchangAI]
· 2 min read· 1,451 words

AlphaProof Code: AI Agents Formally Verify Signal's Code

AlphaProof Code: AI Agents Formally Verify Signal's Code

DeepMind used AI agents to prove safety properties of libsignal's machine code in Lean, opening a new engineering path of agent generation plus formal verification.

Google DeepMind combined AI agents with the Lean theorem prover to formally verify several safety properties of libsignal's machine code. Verification is pushed down to the binary level, bypassing source-to-artifact trust gaps. Formal proofs cover all possible inputs, a magnitude beyond testing. The paper's conclusions have clear boundaries: specification correctness, Lean kernel reliability, agent coverage, verification scope, and the build chain remain trust assumptions—a shift of trust, not elimination. Developers can learn to verify actual artifacts, use independent checkers as a backstop, pilot in high-risk modules, and specification first. The barrier is high; the Signal case proves viability but not low-cost replication.

Title

AlphaProof Code: AI Agents Formally Verify Signal's Code

Meta Description

Google DeepMind used AI agents to formally verify safety properties of libsignal's machine code in Lean. This article analyzes the paper's actual claims, the premises that still require trust, and the agentic coding verification approach developers can learn from.

Article Content

Google DeepMind used AI agents to prove safety properties of libsignal's machine code in Lean. The significance here isn't that "AI can write proofs" in itself, but that it points to a new engineering path: as more and more code is generated by agents, verification methods must be upgraded in tandem.

What the Paper Actually Did

According to the paper published by Google DeepMind, the research team combined AI agents with the Lean theorem prover to formally verify several safety properties of the machine code of the libsignal library used by Signal. The key phrase is "machine code"—the object of verification is not high-level source code, but the actual binary instruction level that runs, theoretically bypassing trust gaps such as compiler correctness and inconsistencies between source and artifact.

The verification method here is formal proof: construct propositions in Lean, have AI agents search for proof terms, and ultimately obtain machine-checkable proofs. Compared to testing or fuzzing, which can only cover finite inputs, formal proofs attempt to cover all possibilities—this is a difference in magnitude.

Lean Theorem Prover: Lean is an interactive theorem prover and also a dependently typed programming language, initiated by Leonardo de Moura at Microsoft Research. It allows users to state mathematical propositions or program properties in a formal language and construct machine-checkable proof terms. Lean 4 further strengthens its capabilities as a general-purpose programming language and provides a metaprogramming framework that facilitates automated proof search. Its kernel is very small and is responsible for checking the type correctness of proof terms, so the trusted base is relatively controllable—this is also the prerequisite for AI-agent-generated proofs to be independently verified.

The Essential Difference Between Formal Proofs and Testing: Testing and fuzzing can only cover finite inputs; even randomization can only increase the probability of finding errors. Formal proofs, by contrast, cover all possible inputs (under model assumptions) through logical reasoning, which is a universal quantification. The cost is that proofs must be constructed manually or by AI, and the specification must be precise. For scenarios sensitive to boundary conditions, such as cryptographic implementations, formal proofs can rule out corners that testing struggles to reach.

Why This Matters

libsignal is the reference implementation of the Signal protocol, carrying the core logic of end-to-end encryption and reused by a large number of downstream projects. Errors in cryptographic implementations are often subtle and have serious consequences, and traditional audits rely on manual work and testing, making it difficult to exhaust boundary cases.

More noteworthy is the trend: code is increasingly being written by AI agents, and agent-generated code likewise needs to be verified. Using AI to verify code written by AI forms a closed loop, which may become one of the foundational infrastructures of future software engineering. High-security scenarios like Signal happen to be the most suitable testing ground for this approach.

libsignal and the Signal Protocol: The Signal protocol is a set of end-to-end encrypted communication specifications, including mechanisms such as X3DH key agreement and Double Ratchet message encryption, and is widely adopted by WhatsApp, Google Messages, and others. libsignal is the officially maintained reference implementation library of Signal, providing multi-language bindings such as Rust, Java, and Swift, and carrying the core cryptographic logic. Due to extensive downstream reuse, implementation errors may affect a large number of applications, making it a high-value target for formal verification.

What You Must Still Trust

The paper's conclusions have clear boundaries, and stating these boundaries clearly is more important than restating the conclusions:

  • Correctness of the specification itself: What formal proofs establish is that "the code satisfies the specification." Whether the specification meets real security requirements still requires human judgment.
  • The Lean kernel and toolchain: Proofs are ultimately checked by the Lean kernel, and the reliability of the kernel itself is a trust assumption.
  • Behavior of the model and agents: AI agents are responsible for searching for proofs, and whether a proof is accepted is determined by the checker, but the coverage of the agent's output still requires human review.
  • Scope of verification coverage: The proven properties are specific safety properties, which does not mean the entire library is proven safe in all dimensions.
  • Build and deployment chain: Machine code verification reduces the trust gap from source to binary, but links such as the build environment and dependency introduction still require independent assurance.

In other words, this partially shifts trust from "believing the code is written correctly" to "believing the specification and kernel are correct"—a shift, not an elimination.

The Concept of Trusted Base: In formal verification, the trusted base refers to the set of components that are not proven but must be assumed correct. For Lean verification, the trusted base typically includes the Lean kernel, compiler, runtime, and the specification itself. Verification can only shift trust from "believing the code is correct" to "believing the trusted base is correct." Therefore, explicitly listing the trusted base is a key step in evaluating the strength of verification conclusions—the smaller and simpler the trusted base, the more reliable the conclusion.

What Developers Can Learn

For teams incorporating AI agents into their development processes, this work offers several actionable ideas:

  1. Push the verification target down to the actual artifact. After agent-generated code is compiled and packaged, its behavior may differ from what was expected during source review. Verifying machine code is an entry point closer to the real runtime state.
  2. Use proof checkers as a backstop. Let agents generate freely, but the final result must pass through an independent, mechanically checkable gate—this is more scalable than line-by-line manual review.
  3. Pilot in high-risk modules first. Errors in modules such as cryptography, permissions, and financial flows carry high costs, so the return on investment for formal verification is more reasonable; ordinary business code may not be worth it.
  4. Specification first. Without a clear specification, formal verification is impossible; before letting agents participate in coding, write clearly "what counts as correct."

A Calm View of the Limitations

The barrier to this work remains high: formal verification requires specialized knowledge and substantial engineering investment, the integration of the Lean ecosystem with mainstream development toolchains is not smooth, and the capability boundaries of AI agents in proof search have not yet been fully characterized. The Signal case proves that this path is viable, but it does not mean it can be replicated at low cost in any project.

For most teams, the more realistic benefit is understanding this methodology: agents are responsible for generation, checkers are responsible for gatekeeping, and specifications are responsible for defining correctness. Clear division of labor among the three is what constitutes sustainable engineering practice in the era of AI coding.

FAQ

Can AI agents replace manual security audits? No. Formal verification covers the properties that have been formalized, while audits must also handle issues that cannot be fully formalized, such as requirements understanding and threat modeling. The two are complementary.

Do ordinary projects need formal verification? Most projects do not. Prioritize high-risk modules, first use testing and static analysis to cover most scenarios, and then consider formal methods.

Why choose Lean? Lean provides a kernel that can mechanically check proofs, as well as a relatively active mathematics and formalization ecosystem, making it suitable for carrying agent-generated proof artifacts.

One-line Summary

DeepMind used AI agents to prove safety properties of libsignal's machine code in Lean, opening a new engineering path of agent generation plus formal verification.

Paragraph Summary

Google DeepMind combined AI agents with the Lean theorem prover to formally verify several safety properties of the machine code of the libsignal library used by Signal. The verification target is pushed down to the binary level, bypassing the trust gap from source to artifact. Formal proofs can cover all possible inputs, a difference in magnitude from testing and fuzzing. The article emphasizes that the paper's conclusions have clear boundaries: specification correctness, Lean kernel reliability, agent coverage, verification scope, and the build chain remain trust assumptions that must be retained—this is a shift of trust, not an elimination. For developers, the ideas worth learning from include verifying actual artifacts, using independent checkers as a backstop, piloting in high-risk modules first, and specification first. The barrier to formal verification is high; the Signal case proves the path is viable but does not mean it can be replicated at low cost.

#formal verification#AI agents#Lean theorem prover#libsignal#Signal protocol#machine code verification#Google DeepMind
Share:

Related articles