DSS

DSS 2026 / Day 1 / Amber Hall

From Production Rust to Lean 4 Proofs: A Verification Pipeline with AI Provers

Natalia Klaus

14:37 · Recording

Watch on YouTube ↗Open recording viewerOriginal programme entry
Download plain textDownload timestamped JSON

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

Source export SHA256: 41a1b9dda56665699cb35d19c13d46ca13fa2cfe2940d72b5ce735dbf7a82c1e