AlphaProof Code

Google DeepMind’s new AlphaProof Code system, which uses multiple AI agents and the Lean proof assistant to formally verify the compiled Signal encryption library, is prompting both enthusiasm and skepticism. Commenters highlight the significance of machine-assisted formal verification for security-critical code, but stress that the guarantees apply only to narrowly specified properties of the crypto protocol—not to the wider Signal app, operating systems, or hardware, and not to whether the specs themselves are correct. The thread broadens into questions about the limits imposed by the halting problem, the risk of AI “cheating” at proofs or tests, and whether such techniques can realistically scale to general-purpose software or remain a specialized tool for high-assurance systems.

Reaction to the Signal / AlphaProof Code Result

  • Many are impressed that a large, real-world crypto codebase can be formally verified at all; Signal’s protocol code is seen as high‑caliber.
  • Some stress this covers the protocol library, not the full Signal app or OS, which remain much larger attack surfaces.
  • A few express suspicion about Signal/EFF’s independence and possible intelligence ties; others push back or ignore this as speculation.

What Was Actually Proven (Scope & Limits)

  • Clarified that the proof targets the compiled ELF binary for libsignal-cli, modeling Arm instructions in Lean, under simplifying assumptions (single-threaded, static linking, stubbing syscalls/crypto).
  • They formalized Signal’s security goals and proved the implementation satisfies those goals, not that the code has zero bugs.
  • Commenters emphasize this is “fail-safe under the modeled security properties,” not a guarantee against all crashes, deadlocks, side channels, or app/OS-level issues.
  • Skepticism that no new bugs were found; likely the properties proved were relatively narrow and the spec itself could be flawed.

Formal Verification, Halting Problem, and Specs

  • Multiple explanations: halting problem blocks universal program verification, but many specific programs/properties are provable.
  • Proof effort is often 50–100× writing the code; AI aims to lower that cost.
  • Core limitation: you can only prove code matches a spec; you cannot prove the spec matches “what we really want.” Spec bugs simply replace code bugs.
  • Discussion of Curry–Howard, dependent types, and termination proofs via decreasing measures; many verification systems deliberately restrict expressiveness to avoid nontermination.

AI as Proof Assistant / Coding Agent

  • Some have used LLMs to generate Lean/Coq proofs or specs and found they look correct but can be subtly wrong or “cheat,” so adversarial review and human experts remain crucial.
  • AlphaProof is viewed as a multi-agent, AI-assisted pipeline that scales expert work to a much larger codebase, not a push‑button verifier.
  • Experiences with “agentic coding” in industry: higher velocity sometimes frees time for better tests and reliability; others warn AI-written tests may be vacuous yet all green.

Hardware, Threat Model, and CPU Verification

  • Desire to extend verification down to CPUs; some note open hardware efforts but emphasize physical effects, side channels, and fault injection remain outside typical formal models.
  • Several warn against equating “formally verified within scope X” with “secure,” given real‑world hardware, compilers, and OS behavior.

Broader Impact and Future Outlook

  • Some predict a future where running unverified critical software seems reckless, analogous to plaintext HTTP today.
  • Others argue most real software (e.g., complex GUIs, business logic) is far too underspecified and messy; verification may remain focused on kernels, protocols, compilers, crypto, and infrastructure.
  • Debate over “spec‑first” development vs. retrofitting proofs: easier if designed for verification from the start, but performance and developer skill are major constraints.
  • Comparisons drawn to Anthropic/Theorem’s work verifying nixpkgs at the assembly level; both approaches build large trusted semantics and use LLMs to handle scale.