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