Formal verification of code could never create a bug-free world, I thought, because it's infeasible to rewrite everything in Lean. Sure, you can prove things about commonly used algorithms, but you'll never be able to prove things about the actual implementations that people use. You're not going to port the world's Linux boxes onto a fully verified stack.
It turns out I was completely wrong; you don't need to rewrite everything, you can prove properties about the existing code! We'll explore this very exciting and new direction of formal verification for code below, and prove among other things that OpenSSL's implementation of the SHA-256 hash function is correct.
As one side effect of crazy fast progress in AI, it seems like AI will be able to prove everything we want[1] pretty soon, which is one of the few clearly positive aspects of AI progress. As a result, I now think a ~bug-free world can be achieved through checking existing code with proof assistants.
How does this new approach to formal verification work? Via writing a formal model of the computer in e.g. Lean, then running the software of interest on that model of the computer and proving things about the behavior of the model plus the software. In a blog post, Lucas et al. (2026) at Anthropic build on the work of researchers like Kaashoek and Zeldovich (2026) and demonstrate that throwing a bunch of agent coding compute at the problem, as expected, yields results. I found the case study buried in the post most interesting: They write a formal model of x86 assembly in Lean and prove that the implementation of the compression format zlib in the Linux kernel (and a few others) conforms to the official specification, save for a few minor, fixable bugs.
This part the authors unfortunately didn’t open-source, so let’s first make a formal model of x86.
Our ultimate goal is to formalize an entire computer. The first step towards that is to formalize the instruction set that the core of the computer, the CPU, uses. This is itself very complex: Intel’s 2003 manual for the IA-32 instruction set is 978 pages long. Luckily there is some prior art, with for example the WASM assembly spec having been formally verified by Watt (2018). A very nice recent paper proving more ambitious statements about security-critical assembly code is Kaashoek and Zeldovich (Oct 2026). They write a model of the RISC-V instruction set in Lean, plus many interesting features like privilege levels and interfaces to hardware.
Since the x86 formal model from Lucas et al. isn’t public (and from the description, not necessarily thoroughly tested?) and there’s no other public formal model of x86 as far as I can tell, I decided that the ground truth should be the behavior of the CPU I have access to, an AMD EPYC 7742 [2]. Since I expect the proofs to be easier with a 32-bit instruction set [3], we’ll use its 32-bit mode for the main formal model. The QEMU emulator is useful for quick tests. We’ll also end up extending the model a bit further beyond the instruction set level by adding platform devices, which will be interesting when proving correctness of Linux features that use input and output.
One modern instruction set itself is apparently very complex. I’ve never programmed in assembly before, but I have played the assembly-programming puzzle game TIS-100 before, whose CPU has 14 instructions. For a modern CPU, depending on what you count as an instruction, there can be more than 1000. We have integer operations, control flow, waiting, floating point stuff, single-instruction-multiple-data, and more.
Since everything rests on the correctness of the formal model, we better test it well. The basic technique here is fuzzing against the real processor across the different types of instructions. Doing this of course turns up bugs in the implementation, and it seems like new bugs turn up each time we increase the number of test cases tenfold. However, it only turns up bugs in the well-established emulator QEMU! Though none of these bugs have been major or critical enough to be worth the time to report them, so far.
Besides that, since we have a more or less functional model of a CPU on our hands, we should be able to do everything with it that we can do with a CPU: in particular, we can boot Linux on it. And voilà, it works fine:
Sure enough, we can boot DOOM in that Linux and play it, albeit slowly.
Note that running DOOM doesn’t actually cover many important instruction tests: floating point, virtualization, and so on.
In this domain, let’s demonstrate with three commonly used pieces of software:
What's an interesting theorem about assembly code? Probably one that proves security and correctness of some important software. It could also be that the proof is interesting from a mathematics perspective. Since I’m not in the mood to have to disclose crazy zero days in commonly used software, let’s focus on correctness here. We'll demonstrate with statemetns about three common software libraries:
A cryptography library that runs on tens, if not hundreds, of millions of devices every day, mostly through its use in the sodium PHP extension. Here we start with easy correctness properties:
A ubiquitous library for protocols like Secure Sockets Layer (SSL). We focus on cryptographic primitives inside it.
It’s cURL, you know what it is! Here we focus on an even smaller part, the function Curl_cert_hostcheck. It checks whether the name on certificates matches the host requested by the user. Here we have three simple statements.
We selected these theorems because they seemed tractable and likely to be true. It turns out that it’s not the default outcome for interesting statements to turn out true: Even highly scrutinized software still has (parts with) many bugs. In searching for good problems, I found bugs in Signal’s SPQR protocol, the Linux kernel, cURL, and more. I’ve reported the most important ones and they're being fixed now, more on that when everything is settled.
All together we have a suite of 30 statements. I then let a swarm of Opus 5.5 loose on them for some days. In the end, 19 of the 30 statements led to a successful proof, most interestingly correctness of SHA-256. You can go ahead and try the rest with your own agents, the repo is available here.
This post is a byproduct of an ongoing project about misbehavior of LLMs in formal verification, specifically specification gaming when AI writes formal statements based on a natural language spec. If you're interested in that, reach out! For that, we need a suite of difficult tasks. In turn, for that, we need a framework for formal verification, which is what we’ve been developing here. The next step will be a task suite in this assembly-level verification paradigm that is difficult for even frontier models.
Also, though, I wanted to showcase what’s possible in this wild new world of superhuman formal verification. AI can prove that the compiled assembly from the SHA-256 implementation in OpenSSL is correct for any input! For a reasonable definition of correct! Only a few people alive could do that. And I’d sure have to pay them more than a few dollars for the proof. Just imagine how tedious this task would be if you were forced to do it. Mapping out the 4,681 bytes of machine code back to intelligible logic, reasoning through every possible combination, etc. The proof ended up being 33,670 lines of Lean here. Not fun to write by hand.
Stay tuned for the suite of even more difficult proof tasks in the next part of this post series, featuring the linux kernel and more!