ZK HACK IV - Provable State Changes: Polygon Miden Transaction Kernel

Transcript

hello everyone um we try to to apply the same style um of the C hack design to our polyon design basically uh today we want to talk about the miden transaction kernel and um it is a program that runs in the mid VM as you will see and uh so for that it might be a very cool uh real world example Le of a um program running in a z KVM creating proofs uh how bobin has designed it basically and um how it's used in our rollup so yeah stay tuned um basically yeah a very quick rundown is that the Mind transaction

kernel proves State changes that's its goal and uh this session will have three parts um first we will talk about the m v M um the Mind VM executes programs most of you probably will know the Mind VM already um and creates execution proofs while running these programs and uh in that we talk about VMS versus ckvm as um risk zero did last time maybe we can add a flavor we talk a little bit or Bob and will talk about the Mind VM design and how MVM programs look like in our masm language um and then we talk about uh what mid transactions are um uh and we

redefine what a transaction is uh basically um to accommodate um our goals like we want to have client side proving and uh so I will explain how transactions are used in the rollup uh how we redefine that uh and how we use accounts and noes in miden and then everything is set basically to talk about the transaction kernel itself which is a program executing these transactions inside the mid VM and in doing so creating proofs so we will talk about the transaction program uh the design of it what are the inputs the outputs uh the four phes or

sections of um of the program and um what do we do with the proof and then yeah we show a bit of code and let's see answer hopefully a lot of lots of questions then I will just hand over to you rob yes hey everyone um very excited to be here and as I'm said we'll go through the three sections and and and then of each section we'll have like a Q&A if people want to um ask questions about that specific section but um the first part is really about um what is my and I think a lot of this U uh you know Le some of this will be repetitive for some people here because uh um there's only so many ways you can describe what a ZK

virtual machine is but I think we'll as Dominic said we'll have a few interesting things to share here as well so let's start with a very basic uh question uh what is the ZK virtual machine and um you know to take a step back like what is a virtual machine or machine computation in general and usually we think about like a you know you can also say it's a state machine something that takes uh some initial State uh and a program applies this program to the initial State and outputs a final State and you know you know a lot of virtual machines or regular computers work in the same way um now ZK um virtual machines add few twists here um first uh we uh as part of the executing the program we also want

to J appr proof and this proof is important because we want to make sure that we can um verify um the execution much faster than we can actually execute the program so this proof assest to the correct execution so like basically you don't need to re execute to the program to get uh uh from state from initial state to final State you can just verify that given this program this initial State and the final state that the everything was executed correctly and this is the what is proof for um another thing that we get with a virtual ZK virtual machine is that we are able to provide the witness or um depends on you know there are different ways to call it called you know secret inputs um something that the verifier of the execution doesn't need to know about

so you kind of can say okay uh some secret data that I'm supplying to the DM when it uh executes and when Jes the proof but the verifier doesn't know about this and and doesn't need to know about this to verify that transaction is executed correctly um a few examples of this witness know we could provide a signature there and let's say the verify the signature or you could provide the preimage of a hash and then you can prove that you could be the actual hash correctly and so on and so forth um now running the VM uh kind of like with the initial state and full status uh like it requires you to provide potential of public input so frequently what we do is we replace the states with commitments and do this uh through the witness we provide initial

State and final state so you'll see in the transaction Cel for example we almost never provide like the actual state of the account you only provide the cash of the account as a public input uh and the actual uh state of the account is provided through the witness theistically um and uh the other thing we can do is do the same thing with a program as well so instead of providing the program in a clear we can provide the commitment to the program and inside the VM um know we provide this specific uh uh you know all the instructions of the program nistic and then the VM does kind of like equivalence check that the uh things provided to the Witness match the commitments uh but this is a very convenient way again you'll see it in the kernel we actually uh you know do

not provide the program explicitly for when we're executing notes we just provide the commitments to those uh programs and like that and andm figures out internally how to uh get the real the relevant code and that code actually never needs to be shared with the verifier all right uh let's go to next slide so why do we need to um why do we even need to do zkm and there's a lot of discussions of like okay um do we want uh the other alternative being like we can go with a circuit computation with specific circuit for a specific uh uh use case that we want to implement but why do we want um uh VMS in general so the first thing and this is arguable because it depends also

in the circuit model you can have a compiler that compiles but uh one of the nice benefits of the VM is that you don't need to learn anything about zkp systems or cryptography uh you just use it as a regular VM you just get this extra thing in the end like in terms of proofs and you able to do a few other things but hopefully all of this is abstracted from you and all of people are L familiar with uh virtual machine so that hopefully the learning curve is much lower uh the other thing that is interesting is like if you have a ZK virtual machine it kind of allow and if it's Turing complete it allows you to run any computation so you don't need to change anything about the DM and you can execute any program out there this is slightly different from like a circuit

computation model where you may need to generate a new circuit uh for a different use case here we kind of say you know we built the VM once it's Universal we don't need to change anything about it we can support any arbitrary computation uh and you know there is relative Simplicity that comes with the VM and also an arguable point to some extent but basically once you've designed the VM and add the constraints and done all kind of like heavy lifting once you don't need to do it again hopefully because the constraints are stable nothing changes about the VM uh itself it can uh then we use other sets of tools to kind of execute programs on the VM and those sets of tools hopefully we you know been running things on Virtual machines and machines in general

for longer they're more mature and all of that stuff so we can take advantage of uh existing infrastructures where you know we' we've kind of you would say like if you compare it against the circuit model for example a specific circuit can be simpler but if you need to generate a a circuit description for every time you uh need to do a new program then you know maybe there is extra complexity there so VMS heavier lifting up front and a bit more complexity or to reduce the complexity as you use it and then um with the DM you kind of get recursion not quite out of the box but you still need to do work but you basically can if the VM is complete and execute arbitary programs then it can

exit the program that verifies its own execution so this is actually the approach we've taken with miden where um we don't have a specific circuit to do recursion uh we just have a program that uh executes within mid that can verify proof of its own execution and this gives you basically infinite recursion you can recurse with the VM as many times as you need so um VMS are nice but they do come with drawbacks especially if we compare them you know against Circ computation one of the main drawbacks is that um because they're are General there is overhead associated with this and know it you can argue like what is the overhead and how do you compare it but it could be you know anywhere between like 5 10x to maybe 100 x depending on

what you are doing so like there's extra like if you have a very small computation you can define a very uh like let's say even sh 56 or uh Blake three or whatever uh that could be a relatively small circuit while the VM circuit is large so like if you need to prove sh 56 or if that's the only thing you need to do inside the VM then uh probably like you're wasting a lot of like extra resources on on uh this overhead that VM requires um now we can op this or I guess um one of the things I should mention actually I was talking about the other point could you go to the second point no no no uh scroll

forward yeah so I was talking about the performance I think um the first point that is mentioned here on the slide is actually about like different proving systems so like you cannot do VMS in all proving systems uh because VM kind of implies relatively unbowed computation uh meaning that you uh you know at the time when the BM starts you may not know when it will terminate so um and it may not be practical to pre-built like different circuit sizes uh or different sizes of circuit for computation so like an example mid VM could execute for um 256 Cycles so it could execute for uh 32 million Cycles or even more um close to a billion not

quite a billion it can't execute for billion cycles but uh it could execute close to billion cycles uh and you would not need to change anything about the DM and it would not require um you know doing uh kind of like different setups for different SI circuit sizes it will also uh not incur the overhead of um you know running the circuit for different SI running the of different circuit size so if we need BM executed for 256 steps that's what we pay for if we if it executes for 8 million steps that's what we pay for that's a nice Advantage now um there are different proving systems that support VMS one of them is Starks we use Starks and that's one of the more efficient systems to uh kind of build

the VM computations in um other other proving systems may be more appropriate for circuit design and faster than those but for mind starts and then yeah the the point that I was actually talking about in the beginning of the slide was you know this performance where you get the overhead and um uh there are different ways to kind of like minim this overhead as well specifically if you know what you're building this for you can use acceleration circuits within this and I'll touch upon a few of this that we have in mind in the and that can uh you know brid the gap between a dedicated circuit and performance and the DM performance okay jum here I'm sorry to

interrupt but I can see that there are a bunch of questions from the audience already in the Q&A type maybe now before uh you switch to the next part would be a nice to actually cover this because I feel like they're related to the to the slide let me do that so I think the first question is performance is 52x uh 51x slower compared to specific Sur with implementation of sh physics uh in a non ZK language so take this numbers as like General like U uh guide guides because they are um like they vary significantly between different implementations of Z languages Z KVM and so on and so forth in general I would say if you have a

simple computation um you know let's say you have a ZK language and that uh creates a circuit for shat 56 and that's the only thing it does uh and you have like uh something like M that is very general or maybe like zkm or uh risk five like what risk zero does I would imagine that like without extra acceleration like the circuit would be more than 10 times faster uh like prob and this is just like speculation because I haven't done actual benchmarking maybe closer to 100 x faster just if you just do the circuit uh now as I mentioned we can put accelerators in the VM uh to bridge this Gap we can do other things and then as complexity of the computation is increasing I think uh the the Gap

actually also shrinks to some extent so this is uh like one of the Cs I want to make but again take this all is directional like benchmarking this stuff is very very difficult and figuring out like what uh uh what is the actual overhead is non- Trivial um so the next question can I execute an invalid operation um on a regular VM um so if uh if validat validating all transactions um and I would say this is uh this depends on VM design so in some VMS um you want to allow people to execute and

valid operation and then you can you know raise an exception uh this complicates the design uh of the VM somewhat but for example you don't allow division by zero so like instead of like trying allowing the person to divide by zero um you would say if you try to divide by zero we'll check for that and it will kind of like return an error within the VM and you need Mechanics for this in the VM uh the other option is that you just can't prove invalid operation so like if you try to divide by zero you can just you cannot generate a proof that simplifies the M but also like you know uh ra a few questions so um at polygon for example zkm follows the first approach where um you can execute a m operations andm will catch

them and uh it will raise an error so you can actually generate proofs for any program um in M VM we follow a different the second approach where you can't uh prove invalid airation so and this is like difference between kind of like approaches because for example we target client side proving where it is you who want like who wants to CH the transaction proof so you probably don't want to uh execute a program that you would not be able to generate a proof for that doesn't make sense in our context so we decided to kind of like go with this more simple design um because of the kind of like the different design space that we're

occupying um hopefully that answ the question uh so the next question I think the vmj proof of transaction and bches this together I think we'll get to this later but uh yes uh um this is how we do it like each uh each uh transaction is a separate program this is what transaction cols about on the VM uh and then we batch them together also using different kernel uh this is a batching and block kernel but we'll get to this later uh M transaction C is a program running in the VM and this is like what the bulk of this talk will be about once I get through the explaining what VMS are in general um uh so the last question here I think

how can be sure that the new state is Created from the last state I think this is the cracks of the like why we run this in the VM as well like if the VM executes correctly assuming there are no bugs and things like that um you you can check the proof and say okay the the initial proof uh the initial State when app when we apply uh the you know desired program to it results in the final State this is uh kind of like uh this is what we prove with zkps and again assuming there there are no bugs this this comes with it kind of like out of the box with with a design I mean we can get into how exactly the VM Works under the hood and there will be a little bit of that later on but I'm not sure if we'll go as deep during the

stop okay let's go to the next slide all right I'm going to try to go through this quickly because uh so we can get to the meat of the content of today's presentation but basically um you know once we know that we want to build a zvm and we decided to do that uh the question is what do we want to kind of which instruction set do we want to build use for this and there are different options so like mainstream instruction set web assembly risk five um there is something that we want to have like for specific life of blockchains for example evm is could be a good choice uh and then last option is like we me want to design something um like completely new uh come up with our

own instruction set this all come with their pros and cons um you know one of the consideration could be a distinct tooling uh you can see like with mainstream you get a bunch uh of tools out of the box and ZK optimize uh the new instructure set obviously has no tool and you have to build everything yourself um is it designed for blockchain specifically uh mainstream instruction set I usually or at least so far haven't built with blockchains in mind and then the last one is like uh I won't say the last one but uh there is uh many more considerations but the the one that we listed here is like the performance aspect can you design it to be very performant with ANP circuit um in some cases that's may be because depends on which instruction set do you

choose out of the mainstream some of them may be simpler like x86 is probably very difficult uh risk five is much simpler and then if you choose your own ziki optimized uh instruction set then you have full flexibility okay so let me uh kind of jump into the mm specifically so mm is St complete St based ZK optimized virtual machine so what it means is that we're using STS as the proving system we can execute any arbitrary program um it is z optimized meaning we're using our own instruction set and I'll get into the reasons in a second so um so and this is like why we're using like minm goal like why we want to use the slightly different instruction set

and let's say we didn't pick U uh like let's say evm instruction set that is optimized blockchains or um uh why didn't we pick let's say risk five or web assembly or something like this so one of the things that we want to do is and this is very crucial to M and design U is that we want to support client side proofs and this entails uh actually a lot of different things but the one of the more important one is that we want to support executing private and unrusted programs so uh and you'll see that when we talk about the transaction fernel but basically the transaction fernel that executes the program is publicly known uh you can execute uh you can anybody can execute it and then you can you can verify per like

execution of the transaction colel because know exactly what it does but as part of the transaction col we also execute Uh custom programs which we call node scripts or account interface functions which may not be known uh and can do different things um and the idea is that we need to provide a level of isolation between uh this programs versus the programs that are being executed U kind of like what is the kernel doing so like we don't want uh some malicious program to be able to interfere with a kernel so like for example this uh requires uh building a context separation at the DM level where we actually support different execution context and as you execute a node for example it goes to one context which doesn't have access to the kernel memory

anymore so it can't modify it uh and you know other things where you you go and um execute let's say a callon account and then a note does not have the ability to write directly into account storage um it all has to go through account interface methods and so on and so forth so uh and you know this is all doable when in a relatively easily in a public context when you know exactly what the programs are doing you can check them ahead of time but in a private context when uh you want to execute something client side and you don't even want to reveal the uh what you're executing this presents a bit more challenges than this at least uh you know our approach has been to handle this through a custom instruction set that is specifically tailored for this use case and then the second point or

second reason um uh why we're doing a specific instruction set and I think this is kind of like a uh you know an important part because not only do we want to you know do this client side but we also want to make it efficient because we want to you know eventually be able to prove it on the smartphone and other places so we've optimized mym specifically for U kind of this blockchain use case and more specifically for blockchain uh blockchains that support this clii proving this means like you know designing an instruction set or using an instruction set as a kind of just picking your trade-offs in different places uh and for us um you know the things that are important for example recursive proof verification we want to make it as as as uh uh we still want to do it inside the DM but we also want to

make sure that it's as efficient as possible we've optimized hashing so that hashing is very very efficient uh because when we will need to handle encryption we we're working optimizing encryption with an ADM so we've picked a few use cases and this is just cover some of them that we want to make sure the DM is very fast so it will not be fast for some computations for example it will not be fast at executing an EDM transaction or it will not be fast at executing some uh you know let's say general purpose computation like something that you may need for machine learning or whatever uh but it will be fast for the use cases that we care about specifically for this uh things that you may want to do on a blockchain like you know verifying C proofs verifying moral path encrypting data and

things like that so these are the kind of motivations for why we decided decided to go with The Specific Instructions um now very quickly M VM is a stock machine um there's like a push down stock in that way it's similar to EDM um and many other veral machines out there we do have uh read write memory that you can access um and you know a program can write this memory as I mentioned previously we have different memory context uh as well like every time cre you enter new context you have a kind of isolate memory uh we have accelerators that accelerate specific types of uh computations we call them chiplets so there's like a hashing chiplet there's others I'll go through

them in in a second and then we have the whole infrastructure of how the might plugs in into the host environment um where you can uh a big a big part of this is what we call an advice provider which provides nistic inputs to the VM what I mentioned in the beginning where you provide just a hash for example via the stock of some data and then the advice provider gives you the actual data and then you can kind verify the equivalence between the two we have you know event hand thebug hand and a bunch of other things that help interfacing with the VM from the host side uh for debugging and other purposes now in terms of acceleration there's um to highlight a few important ones we have range checks which allow us to do a bunch of things with ANM it is this is

one of the most important uh chiplets that allows uh enables like memory accesses or u32 operations to supporting them natively in the VM uh there is also the the hashing um chiplet uh that does a bunch of things it does uh simple 2 to1 cashes sequential cashes it actually can it's a mini processor that can verify meral path very efficiently and this is what I meant like when I said we optimize for specific use cases this is like uh one of those some of those optimizations and then we also have uh uh kind of bitwise operations and exort to make U know let's say something like CH 56 um or like three uh more efficient it won't be again in my VM it will never

be as efficient as a dedicated circuit for those but uh using this instructions that allow you to do ands and exort and other things like that uh natively in the VM uh spits them up quite a bit now um this is kind of like an ey chart of like how the M EX Trace looks like there are different components to it uh I will just highlight a few important ones uh the first one is uh program decoder so like I'll go into like how we um if you go to the next slide uh yeah so instruction decoder is the kind of main component that is responsible for taking the program or the program hash actually and while the VM executes uh reducing or extracting

like the the relevant program information so that they DM can execute instructions that are eventually hash to this hash we have the oper and stock which is basically the main processor of the VM this is where most operations happen like you know addition multiplication you know pushing things onto the stock reading things moving things from the stock to memory and so on and so forth uh and then we have our chiplets uh on the right hand side which is what I covered uh just a few seconds ago um that allow us to execute Accel applications now one interesting thing about my VM and this is very different from uh most other VMS that I've seen out there is that the way we execute programs is uh going through this mask

approach uh so we have M assembly and we're working on a compiler that actually will allow uh already does allow but we still working improvements compiling rust to M assembly so you would be able to write programs in Rust compile them to M assembly and then execute them on MM but um starting with mind assembly uh one of the transformations of the First Transformation we do is that we transform it into what we call the merized abset syntax tree or must um and uh the VM actually executes this uh M um when it runs the program uh must uh is a unique structure because it's it actually makes m not a like a traditional Harvard architecture architecture it's actually a different

architecture where we don't have like an instruction pointer that F instruction for memory we kind of have this traversal of the Mas then um Dominic if you go to the next slide yeah we can we can go to the next one yeah so um when traverses uh the mass that actually builds up the hash of this this is kind of Mer synx tree and the properties that we get from this is that um all programs are reduced to a single uh Mass root so like it's kind of like um you know if you want to compare to something else it's like a Content addressable uh program execution where every program is reduced to to a hash where you can compose programs very

easily together because every node in a in this math tree is just a representation of a sub program under it um yeah so that's what I mentioned and then the leaves of the master are just you know sequential sets of instructions that have no control flow in them so like all all control flow is encoded inside the tree and then the the leaves and code a non control flow based logic uh it's very the m is very convenient I'm actually probably going to skip this example in the interest of time um but um the mass is very convenient for a number of reasons it it does introduce some complexity by complexity actually in the decoder uh but it is convenient because um when we execute a program we only need to uh kind of hash only the

part that we execute so if the program is complex but we in a given for a given set of inputs we execute only a branch in that program or some set of branches then uh it's very efficient in that way uh the other part is that um we statically know what we are executing so like whenever you have a node in The Mask you actually know underlying program and that helps us for example in uh M rollup because um accounts commit to specific programs so you can change the account code for example or change the script uh hash whatever uh uh without modifying the underlying program um and I think the last one is like the nice property of uh this Mass

structure is that you can have public programs with uh or private programs with public preconditions and post conditions we use that uh in uh in the Gom transaction kernel as well this is one of the important properties but yeah mass is actually pretty cool it does come with its own trade-offs but I think it's one of the unique aspects of BM in general all right uh I think there have been some more questions should I read the questions sure like there's one person like if I understood right your touring complete um sorry if I you right your teing complete how can you uh have stuff like

Dynamic arrays uh unknown Loop amount if all the must leaves are known at Advance or can the leaves be looped yeah so the leaves can be looped so there is actually um I I'll share a link here in the chat um uh to the description of how M works but one of the nodes in the m tree could be a loop node and this node will basically repeat the execute the underlying uh tree as many times as like as there are until the top of the stock changes from one to a zero or from zero to one Whatever actually from one to a zero um so it will execute the underlying Master once um check the stock if the stock is one it will execute it again if the stock is one

again the stock changes to zero it will uh stop executing and we move on to the next uh like assembling of of this m r next question is like which instruction set is being utilized here is it risk five or vasm um apologies if you've already addressed this but no so yeah so we have so M assembly is actually its own instruction set so there is um underlying instruction set there is uh we this is you know one of the things that I uh kind of try to explain but basically there's like trade-offs here and we could have gone to the main instruction set uh but then we would not be able to optimize for things that we care about uh it would come with its own pluses and minuses and

also maybe not support like private programs uh and client side computations as easily uh so yeah we we have our own instruction set but we're working on um compilers and other things that will allow you to not to have to learn this instruction set so you can just write a program in Rust and then it will execute on M BM um where can people get more information regarding the rust uh miden assembly compiler uh we have a repo so we'll drop a link to the uh repo in the chat here um it is still in fairly early stages but we can already support compilation from rust to like the way we actually do this compiler is that it compiles rust to web assembly and then it compiles web

assembly to Mid assembly uh so in theory it doesn't even have to be rust in the future although we're focusing on Rust right now so basically anything you can compile to web assembly you would be able to execute on M now there are restrictions for example don't allow floating Point operations because this is not the use case we're targeting uh but in the programs that don't use floating Point operations so like it's basically a um you know subset of web assembly that we can compile into M assembly transparently um maybe I do the stack question first like why did you decide on um on a stack machine as opposed to say a register machine or pure memory machine yeah so I think there were a few considerations and to be honest this is

not something that uh you know I can say definitely we made the right choice I think there are pros and cons to each approach uh I think one of the reasons is that uh uh for a stock machine your instruction representation is much more uh concise so basically for a register machine or for memory machine your instructions are usually like 32 bits uh maybe even more in some cases but usually 32 bits around there uh for a stock machine uh we actually have an instruction being seven bits uh each and then uh depending on how you define like um uh actually for for memory machine I think it's actually even more than 32 bits because you need to provide memory offsets uh and things like that but

stock uh stock instructions are just seven bits in our case and this means uh that we can pack uh like we use gold delog field 64bit gold field we can pack up to nine instructions into a single field element and so when we compute the program hash it's actually super efficient uh we can um in a single premutation we can absor ABB like 72 instructions in the best case like it doesn't always happen but in the best case we can absorb 72 instructions and that allows us to C the program much more efficiently there are other reasons for the stock but uh again it's a trade-off because stock does require you to do like stock manipulation when you execute programs and that adds extra Cycles uh in some cases it may be more uh relevant than others in our case uh for the most cases it's fine because

like of the way the VM is arranged like you're doing usually other things that um uh um that require a longer length so um uh taking extra Cycles on the stock doesn't create too much trouble but yeah I agree it's like it's a trade-off and it's not always clear for which use case would uh which design would work best uh can you elaborate on privacy within the mid VM or is meant the m r up yeah maybe is there privacy in the M VM as well maybe the witness yeah so M VM privacy um there are a couple of comp parts to this like some of this is the same as like you would get with any zkm where I mentioned you can provide the

witness and you don't need to provide like you can execute things uh uh in such a way where the verifier doesn't need to know all the inputs and but this is basically true of any zkp or any zkm that supports uh you know zero knowledge part in improving system um the other aspect of my medm uh from the Privacy standpoint is uh related to how we structure this execution context and must so like one of them is execution context where you can execute untrusted programs and they will not interfere with the trusted program uh there is like uh separation at the DM level um enforced by this and this this by itself doesn't create privacy but it enables uh privacy and this private programs that uh don't affect the rest of the VM uh

the other part of this is M where you can commit to uh some program reveal um part of the program but not the entire program and this could come in in variety of scenarios but it is an extra thing that I think might allows that I have not seen in other places where you can have partial privacy in a way that some things are known but some things are not usually you can either reveal the you can either conceal the program or you can U uh you can reveal the full program but not do it in kind of like selective Manner and now there are lots of questions or like many people like these questions what the differences are between the miden VM and the zika evm and I think it is meant to virtual machine like not to rollup but maybe you can also clarify this I yeah the

difference is might uses a different instruction set that is optimized for client side proving uh to or not optimized but is designed specifically to support client side proving evm ZK evm is designed to be evm compatible so it uses the evm instruction set uh and is uh basically so that we can with no hassle Port eum existing eum smart contracts um yeah and the difference between the two rollup designs will be in the next part um one more question like is is there any plan to support beus for faster and efficient hashing this is this is an interesting thing like we are definitely looking into it and would like to explore um

this more I think um for Mid design specifically the way it stands now I'm not sure there's going to be a ton of benefit to be but again this is to be explored and the reason is like one of the benefits of beus is that it allows you to reduce this embedding overhead uh where if you have let's say if a field element but you're only using a small portion of the field element let's say one bit uh out of the entire field element uh Venus allows you to like really optimize and like save on that uh in the design of Might VM we actually almost don't have such situations where only a part of the field element is used uh overall like I would say probably like less than 10% of the columns or about 10% of the Colum

colums are kind of like binary but 90% use full field elements uh and again this was part of the design so we could realize some benefits but I'm not yet sure how much of the benefits we would get from Bas and but it's an very interesting topic to explore and is there any similarity between miden and ZK Shrine unfortunately I'm not super familiar so I would not be able to answer the question I also don't know C Shrine maybe we can uh yeah and uh like the last question is what would be the requirement as a def to build on miden and um I maybe you mean the rollup with

it um and then maybe we can answer it at the very end of this um presentation basically just check out the repo and at the moment you need to uh code in M assembly which is also okay to do and then two month we will have a compiler hopefully very quickly like I will go to the second part like what is the m rollup and like where do we use this m VM now um and then uh we talk about the transaction kernel basically but um yeah like what problem does the M rollup want to solve um the problem is that uh blockchains today uh and also some ZK EV like yeah ZK EVMS or rollups um they

have the same problem that block producers they execute all transactions in a block and then all other nodes need to reexecute all transactions uh in a block so um basically you have um the problem that all nodes need to keep track of the entire state which leads to State blo and also to execution blow like if all transactions need to be re-executed by many nodes at the same time and this actually um is soft as we think with client side proofs or when the user generates its own uh proof of its own State transition uh uh and that uh obviously gives you privacy which is one of the unsolved

problems yet in a blockchain space uh but it also gives you high throughput and even uh more like the more private the more people use it in a private mode so they prove their own State transition the higher the throughput will be because you can uh create these proofs in parallel at least in the M design but uh our solution to this uh State blo and execution blo problem uh basically or to this scalability problem of blockchains is as we think um that users generate their own proofs and as bobin said this is also one this was one of the reason why we designed the MBM as such is that it

is efficient uh for users um to do these client side proofs and to do blockchain operations in the miden VM um but you cannot simply use an evm uh uh and add clients at proofs to it so you need to change quite a lot in the execution and state model and this is what I will uh talk about now basically miden uh is inspired by the actor model which is used for high performant databases and uh you can imagine actors um in the actor model as State machines with inboxes so they have a little inbox and they get messages from other actors and uh these messages they trigger State changes and then uh like a state change can result in sending out new messages

to other actors and like these um messages can be produced and consumed asynchronously and uh it would be super nice um if a blockchain like in a blockchain you would have the same uh basically um then you would would have this asynchronous uh message passing and like also um at the end parallel transaction execution and um so in miden we implemented the actor model as such that uh you have accounts like uh you have them at the moment in ethereum uh because they are super very good uh for smart contracts and um these accounts they can send notes to each

other and uh basically accounts they still like as an ethereum they maintain State and they expose interface methods so every account on miden is a smart contract and uh these accounts that they send nodes to each other these nodes can carry assets and like in this case um account one creates a note that uh contains three metic and he wants that account two uh consumes this node and in doing so um uh get these three Magic but we need two transactions in miden to facilitate this asset transfer and this is different from other blockchains so basically we have a first transaction where this note is being created and a

second transaction where the note is being consumed and like as opposed to ethereum for example where one transaction always involves at least two uh accounts Alis sends something to Bob uh in miden this is different every transaction always involves only one single account and um but you can like this is how we imagine m in our mental model basically these accounts send notes to each other and in doing so they trigger State changes and one state change is also that you get or you have more uh tokens after State change or you have less tokens and um yeah like this little video is how we imagine these accounts

communicate with the other and um accounts in Maiden um basically as I said they are all smart contracts they have code and storage the code is like you can think of um as an ethereum smart contract and the storage is also yeah also etherum stock projects have the storage and um the one difference is that all assets in a miden account are stored in the account itself again as opposed to ethereum where you if only e as associated with this account um in and all the erc20 tokens are stored or being tracked on an esc20 contract in mid all assets are

always stored in the account itself so you don't need to change two contracts for example to send out or to create a note with an esc20 token and uh we also have two native asset types like fungible and non-fungible assets uh on miden a mid know like these messages that the accounts sent to each other uh they have a script and this script basically needs to be executed uh uh at node consumption so it defines rules how this node can be consumed um and like basically anyone can execute a no uh script uh like anyone who can execute this node script without failing uh like they can consume

this note and in doing so create a proof for it because execute these in the transaction kernel which runs in the MBM as you will see and uh these nodes can carry multiple assets um and they also have inputs that you need uh to put um before you execute the no script into the advice provider um but yeah the main point in this section is just that we needed to redefine what a transaction is in miden uh in order to um accommodate client side proofs and like what we want want is that our accounts can create a proof of their own State transition and then do not need uh the information from the other accounts so a transaction is

always executed against a single account so far and uh it can have uh like it can consume um 0 to 1,96 nodes I guess is the current number and it can produce um um zero or four around 4,000 noes in one transaction and um this mental model of a transaction which helps us to solve uh State load and execution load in the blockchain and helps us to um parallelize transactions basically this transaction is now being executed as a program in the miden BM and in doing so like for every

transaction in mid there's always a stock proof that can easily be verified uh from the mid in the in the mid Network or at the moment uh in the miden operator uh in running in the miden node um are there any questions to the very quick R of the M rollup then let's go to the transaction colel so that this is what bobin showed at the beginning right so we have a zero knowledge virtual machine it uh has an initial State uh like a public input it

has a program uh as an input and a secret inut uh like a witness how we call it and it produces a final state or a commitment to a final State and appr proof and the transaction kernel program basically looks in this image like this so as a public input we have data and state commitments um like commitments of of the account that uh we want to uh execute a transaction against for example and uh as an output we get again commitments and all the data like the blockchain data the account data the node data uh we provide as secret inputs what we provide as uh program input

basically is the whole transaction kernel program and what we get out yeah is a proof that can be verified by the network of this one state transition um that the account wanted to prove as inputs basically as public inputs we have uh commitments to the data and um like in our case uh we have the block hash of the last known block uh we have the account ID the initial account hash so we can hash the whole account to yeah reduce it to a single hash to a commitment and we have a commitment to the um nodes that are

being consumed in this transaction and um in the um advice provider or secret input uh we provide the last known block data the initial account data and the inputs no input nodes data um and then the advice provider can always like grab the Neary uh data uh and unhash these commitments and compare them and in doing so check that everything is correct um the transaction program itself has four faces like in the prologue um the uh the kernel basically passes the transaction data and sets up

the root context that means that we have like it puts all these because the MBM is a stateless uh version machine it puts all the um uh necessary information in into different memory slots and it checks basically that um the nodes that are being consumed in this transaction uh are in fact somewhere in the uh in the blockchain or we're already recorded in the blockchain and um if all of this is correct like the product does a little yeah some more things but this is the main thing basically and then uh like it starts to process the node scripts like these scripts that

basically um that are defined on the Node how um um this node can be consumed and uh each not script is then being um executed in a different memory context which I will explain in a second and um so in an isolated context we can execute each of these notes and uh if all of them are successful um like an optional transaction script is being processed processed which can be used to sign the whole transaction for example and then in the epilog in the fourth phase um the transaction kernel checks um um certain that certain rules are adhered meaning that like is the did the

nons increase by at least one um and like where no assets destroyed or created in a normal transaction and then if everything is correct it outputs uh commitments to the new like to the new state of the account and to the output noes um that are created in the transaction but let's look at each of these steps um uh one by one so basically uh we have the prologue and uh like this is the code as you can see and uh like it starts with processing the global inputs the block data the chain data the account data and the input nodes data this is exactly

what I said so basically it um tries step by step to unhash the inputs like the commitments that we gave via the public input and to authenticate the data and if everything is correct like or it stores them then in the in the memory um and what it also does is like it's uh building a single Vault containing um all the assets of the inputs so it puts the account assets together with the note assets in a W uh and then um it verifies that all the input nodes are present in a noes DB like in um for example in the Second Step here it recomputes the block hash

like the block hash we provided via the public inputs at the beginning and here like we also provided in the advice provider all the data such that it can be recomputed uh by the block data and if these don't match then the transaction Cal execution will fail um it also recomputes um the chain route MMR to check if all the noes are recorded uh in there uh it also uh checks if it's a new account or not like if this account that executes this uh transaction is already already registered uh or not and recomputes the current account hash or like the initial account hash and then

um it authenticates the nodes computes the noes hash and the nullifier and the nullifier is just the information for every Noe uh that we need to cheack if it is already consumed or not um yes I just answer the questions I don't know why this is always uh like one question is the mid R uh mid rollup transactions format is not evm compatible is that right could you please describe sequencing in a short term uh um yeah M rup transactions are not evm compatible that is correct um how would you sequence them like sequencing you mean that you we

order them in the in a block um if so then um like we have one centralized node running at the moment in the future we want to decentralize that as well and um like in M you have two ways how you can execute a transaction you can execute transaction locally or in private um and then you would only submit a a transaction proof to the network and um and you can also let the network execute or the network prove your transaction and then sequencing would be more important in the network transaction case because if not then you would only like the proofs

are being isolated in a sense but um like they both like at the end there will always be a transaction proof for every transaction and they will then be batched together in uh batches uh and then uh into blocks yeah I think might like basically just uh to state but that different like the sequencing almost for for a big part of transaction sequency almost doesn't matter because all the communication is asynchronous so like uh one uh transaction is independent from another transaction involving a different account it is dependent on the transaction involving the same account but uh that's kind of like the only place where the sequencing come into uh becomes important so uh and we expect

vast majority of transactions to be kind of like casually independent of each other because you can produce a note and then when this not gets consumed is not important it could be consumed uh you know many blocks later or like maybe even a year later if needed U yeah so uh I guess the term sequencing could mean different things in different context in our context uh if you think about like just arranging transaction in the block uh for most part it doesn't really matter but it could also mean and like uh it can also mean that the executing account can consume many notes at the same time for example and then it could also depend how these notes are being ordered in the transactions so um indeed

like sequencing is a super interesting question uh in M but um yeah my my my be too long here to answer that uh okay I try to catch up with the questions a transfer requires two transaction these transactions happen in the same block um that's the cool thing so they don't need to happen in the same block um so I can create one transaction and a year later or so bobin can consume the node and then the asset transfer is complete um and yeah that has an impact on composability um but um also that might be too much but they don't need to be in the same block uh one another question does the Mind VM employ Starks uh the

Mind VM runs on proving libr Winterfell and this is yeah runs on Starks and I think at the very end yeah yeah so we do use Starks as a proving system uh and currently Winterfell as Dominic pointed we will probably move to plony 3 at some at some point down the road uh but yeah we probably will stick with Starks uh unless like investigations into beas and other things will result in like you know the outcome will be that it's much more performant and then will migrate to a different proving system yeah um do I understand correctly the double spending note is avoided through the nullifiers if so what gives you the ordering in case there would be a double spend of

notes um yeah that's exactly correct like double spending is this like we use um the same system as zcash or estc um um and um like uh the nullifier check basically happens at the um block production level so because you can do clients and proofs and these happen asynchronously in theory you can create a valid proof of a note that is already consumed but you don't have the correct update yet but you would not be able to add this proof um as a valid State transition into a block so um like yeah at the individual level um there also will be race conditions then

but you cannot um do the double spending check um but just happens on the Block Level yeah I think you can you can say yeah you can maybe say that like there is an element of sequencing on the Block Level because this is where you do the final check when the block is being created by the block producer that uh any node that goes into this block hasn't been spent previously and this is this involves the checking of the new fire tree uh and also any node that was any nullifiers that were created by transactions that are being put into a block get recorded in in a nullifier tree so there are a few updates that are happening uh at the time of block production one of them is updating a nullifier tree uh the other one is

updating like the account States because um you do say that this account State changed from X to Y you may not know the actual underlying details of the account you only know the cashes of the account change from X to Y but you do need to record this at the time when the block is created that the state change from X to y and obviously there's checks there to make sure that if you're changing state from X to Y that the previous state was X and not Z for example um another question like can the nodes contain proofs of offchain execution if the nodes can uh have proofs of off execution then the VM does not need to do any proving but just verifications and recording

um I mean in a way the notes um notes don't contain yeah a transaction is a proof of something being executed off chain a note itself contains a script that needs to be executed uh to consum a node so uh there might be like some terminology alignment that is need here but yeah I mean a transaction is a proof of of chain execution that you've executed some uh transaction that consume X nodes uh produced x no y noes and uh updated you know account Z from one state to to another um and that you know could be fully done uh locally by the user yeah there are even but also that might be too much for today but yeah

there are two ways also to store nodes and then like so in theory the blockchain doesn't even know the node but just the have like it tracks only the commitment to a Noe and then um note execution could be like everything of the note could be completely offchain um as well as ex um okay uh next question the first transaction is create is creating the node now the node is like utxo that's correct the second transaction will happen only when I decide to spend it or when um I will want the funds to be in my account um yes like the second transaction can happen like in the like we have a utxo model basically we have a

hybrid of account model that been used in ethereum and the uix O model um this is how we tracks State basically and um now I cannot read the second part of your question but basically you can decide um when you want to consume a note or like if it's a public note anyone can basically consume the note uh if the scripts allows so yeah I think one cool thing to point out is that uh you know transactions can consume many notes and those notes could have been created at various times so for example now I have an account and you know people are sending a bunch of uh notes my way I don't have to like consume them right away I could wait I can consume all the incoming notes once a week or

once a day whatever I want to do but I can execute one transaction that will consume let's say 100 notes that have been sent to me over a week over a period of a week and that actually would be a more efficient way to do it but I would pay lower fees for doing that uh and you know there are different way different other models and how this would work but this is like one of the cool things that you are not forced to consume the notes as soon as they are created um uh you can choose arbitrarily when when you want to do it yeah and from a privacy standpoint by the way the NFI like there was a question about nlif like uh basically the one of the reasons we use it to prevent double spend but the more importantly the reason why we went with

n fire design is very similar to like its original intention is that it breaks linkability between the produced and consumed no so like when you consume something and you do it execute it locally you actually uh just output a nullifier but whoever verifies the proof doesn't know which note you have consumed so basically your transaction that moves consumes notes basically says okay I consumed some notes out of the ones that exist but I it's not clear which ones exactly am I consuming so that that that is like fundamental to preserving privacy yeah um maybe because we're already over time but um basically because we Al like the Mind VM is stateless in that sense that we need to

put in all the data and like the whole account at the beginning of the transaction and then we store everything in memory and uh we need to um yeah Define the whole memory layout basically for every transaction to consume like a certain amount like to be able to consume a certain amount of notes and to be able to Output a certain amount of notes and this is our uh memory layout which is um yeah which I found just interesting like when you have this MVM basically and you put all the data in then you just write it into memory in M like in M assembly and then you can read that memory and um like um but I think there's no time to show all of these uh like a the next

part if like all these checks initial checks uh were happening uh H then we execute these not scripts um in um in a loop basically this is how M assembly looks like so we prepar a note and then there is a function that we call D call and then uh basically this call s um as B explained before like we we get out hash of a script a hash of a MK program basically um here on top of the stack and this with this Sy call now we can um execute this script and we execute it in a new memory context and this is because we don't want uh unwanted memory access of no scripts that they can somehow

temper with the account uh uh account storage or um so the basically have different uh memory contexts and I can maybe show that um yeah it is too much like uh basically this is like the kernel root context of the kernel program is where it starts and when we are at this D call um um um procedure or function basically it um we switch into a note context and then uh we don't have access to we only have access to the top 16 uh stack elements but we don't have access to the memory that we finally laid out before and then uh but we can always read uh uh some

values via the kernel API still uh from the node um also in the node context and then um even if we want to add assets uh like the node cannot do that immediately we need to do that in a different context in what we call an account context basically um and the account needs to expose um procedures to uh to receive assets uh and then the note can call them and um in doing so like like in a simple uh asset um consuming uh note example here for example we already have three contexts um that we need to um adhere and in every context we have an our own

memory memory layout and I think again to point out that this uh ability to handle multiple context at the VM level so this is not a program that like this is built into the DM where you can create multiple context uh uh is I don't want to say unique to my but one of the like I don't think I've seen it anywhere else uh at least not at the same level of kind of like integration and this is super helpful uh for us and uh you know for the things we are trying to uh trying to achieve and especially like being able to instantiate ADM with different kernels that have different functionalities like we are right now covering a transaction kernel but we also have a a block kernel for example is responsible for proving and validating the entire block this is only for transactions for example in that

case you still use M VM you just instantiate it with a different kernel and that gives you like almost like a uh brand new uh operating system that is running on top of the uh on top of the VM it's like very flexible in this way no and um yeah the transaction script is then used to to sign or to authenticate a transaction um let's skip this and what we get out at the end on the stack this uh the thing in blue down there is uh the transaction script route so um after transaction script that we executed we have a commitment uh to the uh to all the output nodes that were created and the final account hash and um together with the proof and

the inputs like only the global inputs that we provided at the beginning like these four the block hash account ID initial account hash and uh nullifier commitment uh then we can already send it to the mid operator and the mid operator doesn't need to know what is the actual state of the account or what what we like in these noes actually uh to be able to verify um again using the mid VM and batch these transaction proofs together into batches and blocks um yeah you're already over time maybe the two last questions um one question is like is this similar to resource oriented programming I think this was about the

context um context switchings I think there are some similarities I think um you know the closest that that I can think of is like I don't know uh um how much people are familiar with like a component model what is you know trying to be built in top of web assembly there are some similarities with the component model where components kind of are independent execution environments uh that interact with other components so we actually you know did this before that and it's not exactly the same uh but it is similar I think uh you know this separation of context in in a kind of different components in our case we have you know components like every time you create a new memory context you can think about

it as a different component in this case we have like three components interacting with each other kernel note and account those and they are kind of distinct and have different ways of uh you know for example a node cannot call a method on the account that doesn't exist and this will be uh enforced by the kernel so like you can say if the account method does the account interface does not expose a method to let's say send do something with the assets uh then the node would not be able to call it just because the kernel would not allow it and um yeah should we answer the last question or okay let's wrap the last one sorry yeah let's W the last like what kind of use cases does the Mind V mind VM aim for what are you better or worse

than some other ZK VMS um yeah maybe yeah I think yeah I mean uh I basically what I mentioned in the beginning like we're trying to optimize mid VM is a general VM but we're trying to optimize it for a specific mid rollup and the goal of miden rollup is to um allow this uh you know private blockchain or blockchain with private smart contracts which can have M kind of parallel transaction execution and most importantly client side proofs like this is the use case that we're going for uh and it unlocks a lot of things privacy is one but also like you can think about like running computations that are very long running and still put them on a blockchain fairly for manner uh but yeah mm is optimized for M rollup and M

rollup wants to have this parallel uh transaction execution and private smart Pats excellent you can check out our examples and then I think you guys sent a bunch of of links in the chat so yeah feel free to check them out uh thank you very much Bob and mck