Compiling Rust for MidenVM

Transcript

[music] >> Hey everyone. Uh my name's Paul Schönfelder. I work at Miden. Today I want to kind of share with you the approach that we've taken to compiling Rust for RVM, uh which I think is kind of a unique approach. Um and the reason I wanted to share this and, you know, talk about it is that I think the landscape right now is kind of solidified around maybe one or two approaches.

And I think our approach is slightly unique. Um and may open the door to other alternative approaches. So, uh yeah, let's get into it. Really the kind of three major things I wanted to go through here are like what makes Miden like a unique target uh that's not just about how we're compiling for it, but why we're taking a unique approach towards that. Um you know, and how that ultimately informed the choices we made about the tool chain. And lastly, you know, what that actually gets us in terms of benefits and what it ultimately costs us uh and trade-offs.

So, [clears throat] currently today, if you were to like look at the landscape of different techniques for compiling to a ZK VM, you really kind of get three major approaches. The first is to take a common ISA like RISC-V or WASM and prove that. Uh this is like RISC Zero, SP1, um Nexus. They all kind of do this. Um the second approach is to build a custom LLVM back end um that targets like lowers out to your own VM ISA, uh but lets you kind of build on top of the existing compiler tool chain that, you know, most developers are familiar with like C lang or Rust.

Um this one uh like Valda I think would be a good example of this. They do this. Um and lastly is like building your own compiler, right? You essentially are going to throw away all the existing options and build something specifically tailored for your VM uh in a language that lets you surface all the unique capabilities of that VM. Um but the trade-off there is that, you know, you're going to be building everything from scratch, which is an enormous amount of engineering effort, a lot of risk around that.

Uh so, that gives you the maximum amount of power, but also comes at a cost. So, Miden is kind of interesting that it doesn't really fit into any of these buckets exactly. It's more of a blended approach. Um it has its own ISA, so we can't exactly just take an off-the-shelf compiler and and target. Um but we also didn't want to like build our own language, build our own compiler stack from the ground up. We wanted to kind of find a way to to navigate this in a way that let us reuse quite a bit of existing tech, uh but then surface unique capabilities that would let Miden really shine.

Um so, what makes Miden kind of an interesting target here? Unlike uh most other architectures, like we don't have a typical assembly language. Instead, we have this merklized abstract syntax tree, which is a bit of a misnomer. It's not really an AST. Um it's a tree-shaped bytecode for lack of a better descriptor. But what's interesting about it is it's a Merkle tree. And so, every node in that graph or in that tree is uh got a unique Merkle root, right? So, that lets us uniquely identify procedures. Um and the navigation of that tree, the evaluation of that tree is essentially like a tree-walking interpreter.

Um that imposes some interesting constraints though in terms of like control flow, right? You there's no real recursion. Um you have to know like for procedure invocation, you have to know the procedure root, uh the Merkle root of the thing that you want to execute. So, you can't just call things by name. Uh there's no like notion of instruction pointer or anything like that. Um but there's some interesting capabilities that come out of that. Uh one is basically giving you a cryptographic identity for a program um top to bottom, you know, you're not just hashing like the whole program code and saying that's good.

Actually lets you know structurally what is in that program. Um I don't want to get too deep into that because, you know, it's more there's a lot of kind of interesting choices that follow that, but it's not super relevant to this talk today. Uh the other part of this is that in part due to MAST, uh this architecture is a Harvard architecture. Meaning the code and the data are separate, right? Our memory does not contain any code. There's no way to like dynamically emit code and execute it. Um this is very similar like WebAssembly and a couple of other more esoteric architectures.

Um it's a stack machine, not a register machine, which has some interesting trade-offs as well as far as compilation goes. Um but ultimately allows us to keep like code relatively small. Another interesting like caveat here or not caveat, but like feature of the Miden VM is it has this context system. So, these are isolates essentially uh where all of the memory, all the context is kept separate. So, if you call from one context into another, you're getting a clean fresh slate as far as like memory, uh operand stack contents and stuff like that go.

Which is kind of the underpinning of how the protocol works, which is more of an actor model. Uh so, when you're sending messages or like switching between contexts, uh if you're familiar with like Erlang processes, this is a very similar kind of notion where you're executing a very like isolated uh separate context. So, we also have to be able to compile in such a way that we preserve those semantics all the way up into the source language. Um unlike other approaches, you know, the ISA here is machine word, by which I mean the native integral type is actually a field element, not like a 32-bit or 64-bit integer,

uh which has some unique trade-offs as well. But more importantly, what that essentially implies that like our memory model is also element addressable. Uh so, this means that instead of a byte-addressable memory model, we can only address memory by field element. And so, in order to layer over like a byte-addressable memory model on top of this, we have to map byte addresses into this memory model, which has some overhead. I'll get into that in a moment. And lastly, we have sources of non-determinism uh in the Miden VM this called the advice provider. This is how you essentially get like non-deterministic inputs into your program. Um

they provide some kind of unique capabilities. Like we use this, for example, uh for like debugging like input-output kind of things. Um but there's a lot you can do with this. Excuse me. >> [laughter] >> So, like what did we actually want when we were building all of this? Like what of that what choices were we using to evaluate what we wanted from the tool chain? Ultimately, we wanted to take an existing language stack, so Rust really is what we ended up choosing here. We did evaluate other languages, but that was kind of the big one.

And in order to choose a language like that, we knew that we needed like fundamental capabilities, but also we wanted to measure this in terms of like efficiency, size, and runtime performance, namely prover time. Um it needed to be like stable, right? If we're going to build a bunch of tool chain on top of this, it can't be something that's going to be shifting under us wildly, right? So, ideally something that's got a spec attached to it or is very mature already. You know, Rust is very mature. It's not really evolving too much in terms of like its um like the bottom tier of the compiler.

Um but also the target that we chose to lower out of, I guess I I can kind of back up here a little bit cuz I didn't really cover this yet. And that's it, we're choosing Rust as like our surface language, our source language, but we're compiling through WebAssembly, uh specifically the WASM 32 WASI P2 target, which is the component model um like extension on top of core WebAssembly. And what that gives us is the formally specified WebAssembly architecture, but also much smaller surface area. So, we're not providing our own back end for Rust. We're providing Rust as a source language, but

we're really compiling WebAssembly. Uh so, that's where the stability side of this equation comes from. Like WASM itself, core WebAssembly is very stable at this point. It's got a formal spec attached to it, uh which has other benefits. But more importantly, we can expect that it's not going to be shifting under us a great deal. Now, that's not exactly true for the component model aspect of this. It's still kind of in development. But in large part, the pieces of it that we're actually building against are stable at this point.

Um and lastly, yeah, the evolution, the ability to kind of like grow this further. If it turned out that Rust was a bad fit, for example, optimization-wise or the size of the programs that get produced can't be kept small enough to be ideal, or maybe there's another language that is developed elsewhere that would be great source language to use. We want it to be able to take other languages and bring them to the Miden VM and not make Rust kind of like the de facto choice. Um and so that's also something we get from this. Anything that can compile the WebAssembly in theory can also be compiled to Miden VM without having to build any of that.

>> [clears throat] >> So, just real quickly again, you know, the WebAssembly component model Wasm itself is a Harvard architecture, so that's a good fit. It's a stack machine, again good fit. And similar to Mast, there's no unstructured control flow. This means you don't have like go to or anything like that. You have very like limited set of structured control flow primitives, conditional control flow, loops, that kind of thing. Um and its instruction set maps very cleanly to the instruction set service by Miden. So, we don't provide a whole lot of functionality in the core VM ISA.

Instead, we've got just like arithmetic um on belts and then also a set of 32-bit arithmetic like bitwise operators and things like that. Uh so, it's pretty much a one-to-one match in terms of that. There are extensions to Wasm that we don't necessarily fully support. Uh different proposals are in flight. But for large part, we have a very clean mapping from one to the other. Um Wasm itself and particularly the component model enforces a shared nothing boundary. So, if you've got um one Rust crate that you compile to the component model that represents a single component, and then you depend on another component, the tooling already enforces this shared

nothing boundary between those for us. We don't have to invent that or try and hack something together there. Uh it's provided already for us as a native part of the tool chain. Um and then WebAssembly itself, its semantics dictate this kind of shared nothing uh boundary. And a neat feature of the component model in particular is like WebAssembly uh interface types and the canonical ABI. What this allows is essentially native interop between different languages. Uh so, if you're compiling from Rust and want to talk to a language or you know, another program that's written in a different language, the integration between those languages is very clean uh via the canonical ABI.

You essentially generate bindings against that other component that's native to your language, and you can call it as if it's written in your language. Uh this is a little bit different than like CFFI, you know, for those that are familiar with the dirty details of that. Um that tends to be very fragile and error-prone. You know, there's a lot of tooling around it. Uh but the canonical ABI is a lot richer and provides a lot more interesting functionality. For example, like the native string representation can be translated efficiently between languages.

And lastly, and this is kind of important for our use cases, we have some escape hatches available to us via host implemented functions. This is something that's, you know, kind of a native part of WebAssembly because it's designed for that. Um but we use it for like compiler intrinsics to surface some native functionality that doesn't have like a you know, existing Rust API for that kind of thing. Like the device provider would be an example of this. Um precompiles, that sort of thing. Uh there we go.

So, here's a quick overview of our pipeline. I mean, it's very simplified here but you know, there are really sort of three ways to get started with this. You can either be coming from Rust, which we've got provided tooling for, and that's as simple as using cargo build or you know, we wrap that up in like cargo Miden build uh to have some extra tooling around it, but largely it's just under the covers calling cargo build. That emits WebAssembly, uh which we then feed into our compiler front end that internally is mapping that into our IR, just Miden IR.

Uh we can do analysis, transformation, you know, optimization specifically for our VM there, um and then lower that out to Miden assembly, which is the textual form, the AST of the Miden VM. That gets assembled to Mast. Um but on the front end side of this, you can either come into it from direct from WebAssembly. You like you don't have to go through Rust if you already produces Wasm, uh you know, on the component model target, or you can target Miden IR directly if you're building a compiler in Rust for your own like ad hoc language and wanted to just target Miden, that's another entry point here.

We don't have anything that's using that other than our Wasm front end currently, but in theory someone could uh use that as well. And so, the isolation boundary here is really at that Wasm level. Uh everything beyond that is common uh around Miden IR and and Miden assembly. So, it's we're a lot of tooling in here that's not really explained, uh but the three major components are really the Rust tooling, the cargo build side of it, MidenC, which is the compiler, and then our assembler on the back end.

Um I've been asked this numerous times like why did we not choose LLVM IR as like our interface rather than WebAssembly, and there's quite a few reasons uh why that is. Uh this is kind of a quick comparison between the two, but in general Wasm is significantly more stable, has much smaller surface area, so it's lot less ways that things can go wrong or functionality isn't supported properly. It has a formal spec attached to it, which is very useful. And it's just generally simpler to integrate, right? Like we were able just use off-the-shelf Rust.

Didn't have to add any sort of custom tooling or anything like that. We don't have to have a fork of LLVM with their own back end or any of that. Um that turns out to be very useful from like a tooling perspective because we don't have to maintain a bunch of extra stuff. But in general, LLVM also doesn't provide like the shared nothing boundary, so that would have been something that we'd have to invent whole cloth somehow. Um and it's not clear how you would enforce that at the LLVM level uh in a way that doesn't leave potential holes.

So, what is the catch to the decisions that we've made here? Sorry. In general, we've solved a bunch of front end problems that are very convenient, but we sort of created some new problems for ourselves on the compiler side of this, on the assembly side of it. Namely, we don't control the front end, and so there are decisions made there that maybe are not optimal for our VM. Um traditional optimizations, compiler optimizations, for example, strength reduction that will take like multiplication, convert it to like uh bit shifts instead, you know, in certain cases.

Um turns out that like in our VM, multiplication is dirt cheap, but bitwise operations are extremely expensive. So, we don't want that kind of optimization to be taking place, but we don't control that. So, that means that we now have to identify opportunities to reverse those sorts of optimizations. Um that's a problem that gets pushed onto us because we've chosen to like delegate those things to the front end. Um there is some inherent like emulation overhead. I mentioned this earlier, but because Rust has like a byte-addressable memory model and our VM has a element-addressable memory model, we have to emulate byte-addressable memory on top of this

element-addressable memory. Um sometimes that's relatively like thin free but in other cases, it's much more expensive. We have to load an element from memory, mask things out, shift it, and every time you do that, you're incurring a lot of overhead. Lastly, Rust um you know, its whole model around compilation treats like monomorphization of generics as essentially free. But what that does is generates quite a bit of code. Um in our case, we want code to be small because the Mast is meant to be stored on chain for public accounts.

Uh um and anything that over a certain size limit essentially starts to become prohibitively expensive. There are different ways that we're planning to mitigate that in general to make that less of a problem. Uh you know, Mast itself is sort of content addressable but um I think that is kind of the major problem that we have to sort of deal with here. Um I did want to kind of real quickly mention as well that when you choose something here like the compiler tool chain or the compiler part of the tool chain is a very small part of it.

There's a lot else that goes in there. Tool chain management, project management, all the little tools that make using this stuff easy uh are things that you're going to either have to take off-the-shelf or build yourself. So, you do need to factor that in. Uh I don't really have time to get into that, but ask me if you're interested. Um so, real quick like open problems that we're dealing with like the cost side of the equation for Miden really comes down to the performance and optimization side of this equation. Like the size I mentioned, um improver time. Like we haven't done really a whole lot of optimization work, but this is something that we're trying to tackle right now.

And the semantic gaps on the Wasm side. We don't implement everything that's available in the component model currently. Uh there's more to it, but that's kind of largely the the costs. So, just as a few final thoughts here, the space is still very much wide open and in terms of different approaches. I would be very interested to see other alternatives. Um you should look into Wasm as a intermediate target if you're doing this kind of thing. I think it's very interesting approach. And that's about it. I think that's all I got time for. Thanks, guys.

>> [applause] >> Thank you. So, we don't have time for questions during the presentation, but feel free to ask them outside. Yeah. Thank you.