DSS 2026 — From Production Rust to Lean 4 Proofs: A Verification Pipeline with AI Provers Natalia Klaus Source video: https://www.youtube.com/watch?v=jOzP9PoC2Ig Automatic captions — not human-reviewed. Complete spoken-audio coverage is unverified. Source language tag: en (English). Source export SHA256: 41a1b9dda56665699cb35d19c13d46ca13fa2cfe2940d72b5ce735dbf7a82c1e [0:00] Hello. My name is Natalie Klaus. I work [0:03] at Runtime Verification. I'm proof [0:05] engineer and today I'm going to tell you [0:07] about our [0:09] collaboration with Ethereum Foundation. [0:12] We've been working on formal [0:14] verification of zero knowledge EVM. It's [0:17] an ongoing project. [0:19] Yeah, verification project. And we try [0:21] to build a pipeline which translates [0:24] source code to Lean. And we prove [0:28] formally using mathematical methods that [0:31] code corresponds to specifications. [0:42] Okay. As I said, it started with [0:44] collaboration with Ethereum Foundation. [0:47] And this is briefly what our pipeline [0:52] does. So step number one, take source [0:56] code, Rust cryptographic [0:59] libraries were our goal to verify or [1:02] Plonky2 free risk zero. These are [1:07] Starks libraries, right? And step number [1:10] two, translate library source code to [1:13] Lean 4. You We could use any instrument. [1:17] We were allowed to use any instrument [1:19] which is mature enough to do such [1:21] translation. And spoiler, there is no [1:24] such instrument yet there, not mature [1:28] absolutely because, for example, we do [1:30] not support unsafe, we do not support [1:32] async, we do not support low-level code, [1:35] and Linux kernel is low-level code, and [1:37] we have lots of concurrency in Plonky2 [1:41] free, for example, but we had to try, [1:43] right? [1:44] So step number three, specifications. [1:47] Specifications are human-written, [1:49] handwritten. And we also use AI to write [1:52] specifications, but sometimes AI fail in [1:56] writing specifications because they can [1:58] write really often vacuous [2:00] specifications which are really easy to [2:02] prove and they state nothing. So we [2:05] prove nothing. So [2:06] human engineer should check each and [2:09] every specification we write. And we [2:11] also used ArcLib and CompCert. These are [2:14] libraries for Starks which were also [2:17] created within this project within [2:20] Ethereum Foundation. [2:22] We are not the authors of these [2:24] libraries, but we contributed to ArcLib [2:27] and CompCert heavily because seven [2:30] months ago when this project actually [2:32] started [2:34] these libraries also were not mature [2:36] enough. [2:38] And we had to write math and we had to [2:42] build some we had to fulfill them with [2:45] bridge lemmas which helped us to do [2:47] verification. [2:49] And final step actually writing the [2:51] proofs. So [2:54] production Rust we should prove [2:56] mathematically that production Rust [2:58] matches the mathematics, right? That [3:01] code actually does what it should do [3:03] always for all possible inputs like we [3:06] prove [3:07] theorems in our geometry, right? It's [3:10] cool. And [3:12] yeah, and what is in the basis of our [3:15] approach? Lean. Lean 4 is a prover. It's [3:19] a kind of language which we can use to [3:21] write code and to prove to reason about [3:26] the code. [3:29] So [3:30] so this is [3:31] top level of our pipeline and in more [3:35] no, this is not [3:38] right. And this is more detailed [3:40] specification. So how exactly we [3:42] translate code? Well, actually we can [3:44] play with this pipeline. We don't have [3:47] to [3:48] well, let me be [3:52] more clear. So [3:54] first step we take Rust crate like as it [3:56] is [3:58] plonky2. [3:59] Step number two we lower it. We use [4:02] special instrument, Caron, which [4:04] translates code to MIR. When from MIR we [4:08] take LLBC, it's intermediate [4:10] representation, and from LLBC we can [4:13] build lean definitions. [4:17] And once we have lean definitions, it's [4:21] similar let like we have mathematical [4:24] model. On this step, when we have lean, [4:27] we can reason about our model. We can [4:30] write [4:31] specifications, we can write theorems [4:33] and lemmas and proof. [4:35] For example, for Rust code, we can prove [4:38] that code never panics. We can prove for [4:41] C code that code do not have undefined [4:44] behavior anywhere. [4:46] And [4:47] we also can connect our lean model to [4:51] specifications on ArcLib and CompCert. [4:54] CompCert is about polynomials and finite [4:57] fields. ArcLib is about Starks in [5:00] general, and CompCert is underneath [5:03] ArcLib. [5:05] They initially should be one and the [5:07] same project, but they are separated. [5:11] And how we write proofs? We use AI [5:15] provers and we use [5:18] engineers. [5:20] We also use specialized AI provers like [5:24] Aristotle from Harmonic and Aleph from [5:26] Logical Intelligence. Aleph is AI prover [5:30] which should work only with lean, and it [5:33] has all math leap within, and it can do [5:37] the proofs really quickly because, you [5:39] know, like before AI era, like [5:43] five years ago or four years ago, I had [5:45] to write all these proofs myself, and it [5:48] was horrible amount of work. It's like [5:51] digging land with your bare hands. And [5:54] now with AI, we have like exoskeleton, [5:57] and we can work really quickly. We can [5:58] do more in shorter time. I really think [6:01] that [6:03] AI is something incredible. It's [6:05] progress, and it's unstoppable. [6:08] And it will help us to cross this ocean. [6:11] And ocean is huge actually. [6:14] So this is example of simple behavioral [6:17] lemma. For example, we have x and [6:22] our function simply divides x [6:26] on two and when plus one. And this is [6:28] theorem we prove. This is very simple [6:31] example, right? Just to show case. [6:34] And here we prove that [6:37] for all possible inputs [6:39] our result will be [6:43] first of all it will never panic and our [6:45] result always be [6:47] more than zero, not equal to zero and we [6:50] will have such result, right? It will [6:52] exist. So this is example of simple [6:55] behavioral lemma. And our clip and comp [6:58] poly, as I said, we have complicated [7:01] mathematics here which describe how [7:03] Starks, how cryptography should work. [7:06] And our goal was to prove our lean model [7:09] against this specifications, simple and [7:13] actually cryptography specifications. [7:17] We targeted [7:20] several [7:21] we we tried everything. We tried Fry, [7:24] Mersenne 41, Horner evaluation. And here [7:28] I'm showing what instruments in pipeline [7:31] we used with each and every example. And [7:35] what actually we proved. All proofs [7:37] online you can check. [7:40] Yeah, and with one step Fry folding [7:43] round we had the most interested result [7:47] because we managed to connect it to our [7:50] clip. It was not that simple because [7:54] yeah, because all the instruments as I [7:56] said are not mature. It was like [7:58] experiment which showed that [8:00] instruments are not mature. [8:02] Okay, so what AI is we used during the [8:05] process? We used Claude, of course, I [8:08] have to say that specialized AIs like we [8:13] we can contribute themselves, we can do [8:15] PRs, we can [8:17] proof. We had one interesting proof. We [8:20] had to prove really complicated lemma [8:22] and it took like [8:24] $200 [8:26] and [8:28] 24 hours it was running, running. We [8:31] provided it with PDF, we provided it [8:34] with additional mathematics which is [8:36] behind and it finally did the proof. [8:42] Aleph it actually splits proof to [8:46] several sub steps and prove them all one [8:49] by one. [8:51] And also what is important here [8:55] in our pipeline there are a lot of wings [8:59] things we should trust, right? [9:01] We are talking about mathematics, so we [9:03] would like everything to be proved [9:05] mathematically and there is nothing to [9:06] trust, right? In our PI, in our [9:09] pipeline, but still we have to trust a [9:11] lot of things. We have to trust [9:12] translator. Ideally translator should [9:16] we should be able to proof [9:18] mathematically the translator actually [9:20] that a result code in line four equals [9:24] to initial code and it is possible to do [9:26] such proof. [9:27] For example, by induction if if [9:29] translation is correct for simple piece [9:32] of code for one [9:35] piece of semantics it would be correct [9:37] by by induction for a whole big bigger [9:40] piece of code, but [9:42] such proof [9:44] equality between translation and initial [9:47] code is separate research work which [9:49] should take take maybe several years, [9:52] but again with AI it can be done much [9:55] faster [9:56] nowadays. [9:58] And also we should trust compiler. We [10:01] should verify compiler, we should trust [10:03] specification itself because it was [10:06] human written, right? And all the [10:08] specifications are in maintainers head. [10:11] So this is collaborative work. [10:13] Verification engineers should work [10:15] together with um [10:17] maintainers. [10:18] So um [10:21] yeah, and as I said, AI provers failed [10:24] in some places because [10:27] instruments which translate code from [10:29] Rust to Lean, they are very specific. [10:33] When you build such instrument, you [10:34] should decide on many things. For [10:36] example, what logic to contribute to. Is [10:39] it separation logic? Is it many sorted [10:41] logic? Also, you should decide what [10:44] semantics you should use, [10:46] right? And it perfectly it should be [10:48] executable semantics. So we could do [10:51] differential fuzzing in Lean version, in [10:54] C version, or in Rust version to prove [10:57] not prove in mathematical sense, but to [11:00] show at least with fuzzing that our [11:02] translation is accurate. [11:06] Yeah, building the pipeline was not [11:09] trivial task itself because [11:11] each instrument in our pipeline [11:14] is having different Lean versions. [11:18] Arclip, even Compolly, they both had [11:21] different version. [11:22] Enias Hawks different versions of Lean. [11:25] So and our goal was to build it all in [11:29] one and the same Lean project, right? So [11:32] what we did? We had to connect with all [11:35] maintainers and ask them to align Lean [11:38] versions into once we could build our [11:40] pipeline. And they were very responsive [11:43] and we managed to build it. [11:47] Yeah, and another problem we faced, as I [11:51] said, is extraction gaps. [11:55] Enias is the most mature instrument [11:58] nowadays for [12:01] translation from Rust to Lean, but it [12:04] doesn't support even unions, for [12:06] example. [12:08] I'm not saying about unsafe facing [12:12] code. [12:13] So [12:16] we decided to build translator [12:18] ourselves. [12:20] So, this is the prototype of our [12:22] translator [12:24] to show [12:27] to show C side effects. This is for C [12:30] language, but approach itself, which is [12:32] having several years of research behind, [12:35] approach itself is language agnostic. We [12:37] can use it for Rust, we can use it for [12:40] C, we can use it for Go, but we are [12:42] doing it for C, first prototype. Well, [12:45] first prototype was for Go, and this one [12:47] is for C. We do it for C because right [12:49] now we are targeting Linux kernel, and [12:51] we already found several bugs [12:54] in Linux kernel, and last one was [12:59] security bypass in Linux kernel [13:01] isolation layer. Each and every AI works [13:04] in this isolation layer, [13:07] and we found bypass. It was fixed in 6 [13:10] hours after we found it. And take a look [13:12] at this translation. It's I think it's [13:15] perfect because [13:17] they are almost identical. This is also [13:19] result of our research. The only thing [13:22] which shows that this is lean is this C [13:25] done word here and there because we [13:28] should exit [13:30] free Monad, actually. Yeah. So, to show [13:33] imperatively functional lean, [13:35] to show all the side effects, we had to [13:38] use Monad. We are not able to use free [13:41] Monad because it's not enough to cover [13:43] all side effects. So, we are using [13:45] advanced free Monad, and we are hiding [13:48] this prototype from LLMs because we can [13:51] steal the ideas. We We don't know what [13:53] to do with it right now because [13:56] several years of research behind, and [13:59] you can reproduce it with LLM really [14:01] quickly and do use this approach [14:04] yourself. [14:05] So, [14:08] yeah. We also I have I described how our [14:12] instrument works. We translate C code to [14:16] C to JSON IST by Clang, and then we [14:20] receive Lindy cell. [14:22] As I said, effects are covered with [14:25] freer monad. [14:28] Yeah, I think that's it. I'm almost in [14:31] time. Thank you very much for your [14:33] attention.