Polygon Miden - a STARK based ZK Rollup

[Music] [Applause] so next up i want to invite bob in to talk about polygon minded so um robin whenever you're ready feel free to uh get started and welcome thank you kartik and uh hello everyone very excited to be presenting amongst such brilliant people and talk about polygon minden let me just share my screen all right i hope everybody can see the presentation everything is good all right so before i explain what polygon mightn is let me give you guys a bit of history so i've actually started working uh with zero knowledge tech and stark specifically in spring of 2019 and the first thing i did was build this uh jen stark library which was a stark ruler for you know aiming to be able to generate proofs for kind of any kind of computations and once i build it i realize that it's extremely difficult for regular developers to just pick up and start using something like this and i can spend a few months trying to figure out how to make it easier and try to develop it first kind of that means specific languages that would make it very simple to create stock proofs but even that turned out to be quite complicated uh so the next thing i try to do is uh i start to think about start-based virtual machines and i actually made a this if research post early in february 2020 describing kind of the my thoughts on it and at the time i actually didn't think it was going to be very powerful machine i didn't think it was going to be touring complete but as i started working on it i realized that you know there are a lot of things that we can unlock and there is actually a way to build a practical start based virtual machine and a few months later i built the first version of this staff vm and you know improved it over the following months and this fvm is actually one of the foundations for polygon uh the other foundation of polygon minon is winterfell which you know after i worked on this fdm i joined uh novi and uh as part of being there built this winterfell stark rover it's uh in a way very similar to jen stark but it is much much more performant modular and you know up to date implementation of star protocol and now polygon mode and vm is kind of a combination of dystopia and winterfell and in a way it is uh uh a combination of what i've been working on for the last two years so to say uh so i'm very excited uh to kind of talk about it so uh what exactly is polygon midan polygon midan is general purpose stark based uh ck roll-up and i know a lot of people here are already familiar with all of these terms but for those who are not let's uh go through these terms one by one and start with ck roll up so what is the zk roll up uh in sdk roll up we have uh users operators and then we have an on chain contract which is uh you know on the team main chain and the idea is that that users send transactions to operators and you know there are many users and operators aggregate those transactions into batches and then they submit uh kind of the state change or whatever has changed in the internal state of the ledger that the operator is uh managing together with the zk proof that they verified all those transactions to the on-chain contract which uh verifies that so why do we care about this type of uh setup and uh one of the answers is that it gives us a lower fees because you know we can compress a lot of things using zk proofs and there are other reasons why uh you know for example we don't have to include every single transaction if some transactions happen between uh the times that uh uh we verify sdk proofs then those transactions can actually become you know completely absent from the kind of the state change that gets pushed into the amina so we can get up to actually over 100x reduction in fees as compared to ethereum and the other thing that is that is important is we can get this without sacrificing security so in the ideal scenario the the zq roll-up is just as secure as ethereum itself because it includes security from ethereum there is no way for operators to submit invalid transactions or you know submit a state transition in sdk proof for something that is not really valid so if they didn't have a transaction to verify they couldn't make it up and the other exciting part is that roll ups can be very high throughput and the reason for this is that unlike let's say in the decentralized ledger of kind of the way ethereum is the operators can be fairly heavy and they can have very you know sophisticated hardware to process a lot of transactions and um you know we only need to really to have one operator that is honest uh uh to for the roll up to work and even if the single operator for whatever reason decides not to be honest um uh we still the users can still go directly to the on-chain contract to reclaim their funds so we of course want to have the roll up to be decentralized but uh this uh kind of setup allows us to have have much more flexibility and experiment with different consensus models execution models and you know structures of the ledger and achieve this high throughput lower fees while still maintaining the same level of security and that's flexibility portion is something that is really really exciting to me personally okay so this is a very high level overview i'm sure most most people here really knew what the secret roll up is but just to kind of set context okay so let's talk about the next term start based so uh before we talk about what the stark based means we need to talk about proofs of computational integrity and you know we we talk about this as zk tag but actually the thing that we really care about is this uh proving that the computation was done correctly zk in many ways is incidental to a rollup although you know it is a useful property if we want to achieve privacy as well so in terms of proofs of computational integrity usually there are two parties there is the approver and the verifier and approver was to say that they ran some kind of computation and they have gotten some kind of result in the context of a rollup the computation is verifying all the transactions that they want to put into a batch and they want the proven to accept that they've computed the result correctly without prover without the verifier having to rerun those computations themselves and obviously we want to be in a setting where we don't want to trust the approver on their word so the verifier cannot just accept the progress result but what we do is the approver can send this zero knowledge proof to the verifier and the verifier by examining the proof can be convinced that the approver has run the computation and the gut and received the claim result uh without having to do the computation themselves and uh it's very important for uh for in our context that the proofs are small and fast to verify it has to verify so um overall in terms of proofs of computational integrity there are two large families uh starks and snarks and um you know uh stark stands for scalable transparent arguments of knowledge and they were developed by brilliant people at starkware and there are a lot of different stories developed by many different teams and they stand for succinct non-interactive arguments of knowledge but rather than saying like there are two different families there's actually a lot of overlap between them um so and non-interactive stark is actually also a snark and the scalable transparent snark is also a stark so in our context we're actually working with non-interactive starts which means also that our system is a snark as well right there are a few advantages and reasons why i think starks are a very good choice for a roll-up type system and i'm going to go through them in the next slide so start advantages as i mentioned or is it comes from the name starks are transparent and scalable so there is means there is no trusted setup we don't need to worry about toxic waste you know trusted setup being compromised and you know potentially somebody uh one of the operators or proverbs uh generating fake proofs so that's a very good fundamental property to have uh the other advantage of starks is that they use very lean cryptography and what i mean by this is that they rely only on collision resistant hash functions and that makes them post quantum secure and in many ways it's a future-proof technology um they're very flexible and here i'm getting a little bit uh too technical but uh you know we had the talk from uh polygon zero where they talked about selection of a field and you know the same applies to starts as well you can choose a specific field which is very performant and allows you to generate proofs faster you can also dynamically kind of trade-off between prover time and proof size so you can increase proper time by uh reducing proof size and you know play with different security levels without having to modify anything uh kind of in the proving system uh you can do it uh you know you don't need to choose a different elliptic curve you don't need to uh redo your circuits you can kind of dynamically trade off these properties and tailor it to a specific use case and then in terms of performance this is i think one of the big advantages of starks as well first the verification is very light in terms of like real world performance most of the proofs that for any practical computation are just single digit milliseconds to verify and the description of the computation is succinct as well because there is no process reprocessing that needs to happen um and then on a verifier on the approver side the proof generation is also very fast so uh a few benchmarks of on the current implementation of my mdm is that right now on a single cpu port you can verify um you know you can execute about 10k instructions per second which is you know 10 hertz if you think back to daniel's talk of uh a little bit earlier where he mentioned that it took uh uh like multiple seconds for a single uh instruct instruction to be executed on the tiny mdm this is already many orders of magnitude improvement uh but it gets better because we can paralyze very easily and even with the current implementation we can get up to you know 400 hertz uh if we spread the generation across multiple cpus and we believe that with some additional work we can improve the significantly in the future um and then you know if we go to gpus and fpgas and in the future where there is hardware acceleration this is going to be in the megahertz range and probably very very fast for all practical purposes starts are not perfect there are some disadvantages to them and the biggest one is the proof size usually proofs are in dozens of kilobytes so just a few benchmarks for mid and dm in its current form if you if you execute 1000 cycles the proof size is about 35 kilobytes and for a million cycles it's around 80 kilobytes and you know if we need to go more it grows but it grows logarithmically so it's uh it's not gonna uh get too big it's probably not gonna exceed you know 150 or 200 kilobytes at the at most for uh pretty much any practical computation um this kind of like the proof size is lead to relatively large gas cost when we try to verify proofs of the helium so uh between three and five million gas for verifying a stark proof probably closer to five million uh on ethereum but once eip4488 comes through we should see that uh gas cost dropped to hopefully under a million but uh this will need to be verified but uh again because the the actual proof is very fast to verify it's just the the proofs are large once the whole data cost gets reduced uh the cost of verifying um star proof will get reduced significantly as well uh the other thing is recursion and it is possible to do recursive starts they haven't been demonstrated yet but especially in the context vm this becomes like having a virtual machine this becomes a real possibility to build recursive starks proof as well and this is something that we will investigate uh on our end too now let's talk about general purpose so if we think about zika roll-ups specifically there are two ways to think about them so there is a specialized type of zika roll-up which handles a specific use case like payments and you know exchanges nfcs and so forth and then um there are general purpose zq roll-ups which allow you to write arbitrary smart contracts and this is um the more exciting type of a roll-up uh which you know developers can build their own logics and you know smart contracts that we can think about and like have the full power of uh you know ethereum type environment within the roll-up and having building a general purpose dk roll-up requires to have a or at least you need to have a zero knowledge virtual machine so um in the context of uh uh polygon might and the uh well let me talk about first about what the zero knowledge virtual machine is so zero launch virtual machines you can think about as a virtual machine that takes some initial state and a set of programs executes them and you know gives you some final state but it also uh gives you a proof that it has executed everything correctly and this is the crucial part where you can execute many different programs on this vm they don't have to be all the same program they could be different programs and you'll get a single proof that says all the programs have been executed correctly and you one other distinction is that you can provide this witness data for example in the blockchain context this could be signatures that once the vm has verified them you don't really need to include them into your proof that goes onto him so you can basically discard the sweetness data where it gets discarded and that allows you to significantly compress things that need to go on to the main chain in the context of polygon maiden we have might and dm which as i mentioned is based off of this vm and let me give you a few highlights about the vm itself and where we're going with it so one of the main focuses that we want to uh have is that to have the vmb developer friendly and by that i mean we want it to be as close as a typical uh virtual machine that you know you might have encountered outside of zero knowledge or a cryptographic context so but you don't really need to learn anything about cryptography so for example it's going to be a simple stat based machine uh this is what uh polygon midan is right now it is going to support natively 32-bit integer arithmetic so no need to think about field elements or understand finder fields or anything of that sort you can just work with 32-bit integers it will have read-write memory so very easy to kind of like you know learn how to use it it will have native exception handling which is very important in the context of smart contracts where one contract can call another contract and the other contract can fail so we want to make sure that uh even if there is a failure somewhere we can still prove that that you know the original smart contract that called the field uh contract executed correctly and we are planning to build a very extensive standard library which will support all kinds of uh goodies that people and developers and you know for smart contracts and defy might be interested in the other important thing that i want to mention is that we want to make a mighty multi-language uh solidity will be the first class citizen in this vm but we also want to make sure we can support other languages such as for example move uh or other languages that people would want to compile into my vm assembly um and one of the other design goals and it feels kind of related to multi-language support is that we want to make the vm safe and actually safer than evm itself so we will not allow dynamic cool targets and you know we still can compile solidity into this and still will work fine but underneath the vm will be safer than the evm itself which will also make making bugs potentially much much more difficult uh putting bugs into your smart contracts and then we're taking some hints from like brass programming language all operations in the vmware safe by default um and there is also privacy focus kind of like you want to build in some privacy features into the vm but uh this is not the focus right now this this is but we do want to make sure that the groundwork is there where we want to support uh you know both data and functional privacy in the future so that the vm can execute kind of privacy preserving smart contracts uh and just to kind of like show this diagram of how we think about multi-language so solidity uh we will uh can be compiled into you uh intermediate representation right now and then we'll have this ultimate uh transpiler which will transpile you into midan assembly language and then the modern assembly language is the native language of might mdm and then other languages will be able to compile into might and assembly as well so um i talked a lot about where we want to go now let me give you a little bit of a roadmap of how we will get there and uh right now basically last month we released the version 0.1 of my nvm it is it already has kind of stock manipulation arithmetic operations and basic control flow implemented in a few months from now we will be releasing the version 0.2 which will have memory and native support for 32-bit integers and we'll have procedures and we'll keep building on top of it over the next year and to add such things as storage and support for things that are important for edm compatibility and uh you know our plan is within a little over a year to get to a point where you can compile solidity into uh might and assembly and then in parallel uh toward the kind of uh um you know late q2 of next year we will start building the actual roll up around the vm as well uh starting with uh you know initial couple alphas and then hopefully uh by q1 of 2023 we'll have uh data in production to experiment this is a fairly aggressive timeline but we'll do our best to make it happen uh and then to wrap up just wanted to talk a little bit about some of the values that we have with polygon might and the first one is we do want this to be a community driven and fully open source project so the source code for even the early version of light indian is fully available right now we do want to collaborate with anybody who is interested in building on polygon maidan or even just using vm for whatever purposes they want to have so please you know check out the repo and feel free to start using it and let us know if there are any features that are missing so we really want to make it so that we build it with the inputs from the community we will be releasing the initial draft of might and assembly and probably within a week or so and the feedback on that will be very helpful and the other set of kind of values is we do want to build if we decentralize and censorship resistance roll up so uh uh not a single up not to have a single operator but to have a kind of a network that is fully in alignment with kind of web3 ethos and here is uh the link to the repo so check it out and let us know uh if you would like to use it in some way uh even before it's ready that would be very uh helpful what's that uh i'll open up two questions thank you so much bob and this was an incredible um overview on all these improvements that you've kind of made with the help of the team we don't have any questions specifically to uh what you've talked about it's just been comments from like this is uh incredible and uh some of these things are just amazing that people are enjoying um if something comes up i will uh happily share them on the chat here uh to you in the zoom but uh you know some specific questions about that yeah definitely definitely if somebody thinks of something else later on feel free to drop me a line on twitter or something or anywhere else perfect [Music] [Applause] [Music] you