Polygon Zero

[Music] [Applause] [Music] uh you know so basically as uh mihailo mentioned about our polygon you know zika thesis that uh you know and why we we feel that the announcement that we are going to do today is is very very big is that uh there are there are you know uh you know a few uh gk solutions out there but one of the biggest problems with zk solutions have been always about performance and the second thing is that because uh because it requires a large amount of resources for uh you know zk provers to you know create uh you know zk proofs uh it makes it essentially very hard to decentralize right so imagine like as mihalo was saying that you know if we had a very you know extremely fast probably world's fastest uh you know zk recursive proving technology and extremely efficient also which could run there where you could run zk proofs uh you know on on a simple machine like a laptop that would be uh you know the game changer for this industry where a large number of uh you know nodes can be run in a network which can validate the transactions and things like that which will actually truly truly make uh you know us us or truly enable us to create decentralized uh layer 2 network uh for for polygon and and you know like for that uh you know i'm i'm extremely happy to announce on behalf of uh you know our entire team everybody is that uh you know polygon has uh polygon is very excited to welcome uh you know uh polygon excited to welcome polygon zero uh which is uh which will be led by uh you know a really brilliant team of uh you know cryptographers and engineers uh primarily brandon and daniel and they were previously doing it as beard protocol uh which has now uh decided to join uh polygon and focus on zk scaling previously they were building like a zk uh you know enabled chain but now therefore they have decided to join polygon and build a decentralized uh zika roll-up on top of polygon uh you know so with that i will request brandon and daniel to you know take this stage and uh you know take us through uh but yeah for polygon community like you know we are extremely happy uh that uh you know this essentially now puts polygon right in the lead uh in this entire zika scaling effort we truly believe that zk is going to be is the is the ultimate frontier which can bring in internet level scale to blockchains and uh you know this with me team also joining already an amazing suit of uh you know solutions on polygon this will this puts polygon in the lead uh globally in terms of the zk solution providers so over to you uh brandon and daniel uh hey everyone um i'm brendan i'm the uh the one of the co-founders of mir uh you you may not have heard of us uh but hopefully uh we can give uh some detail on what we've been working on um and so i i just like to say that uh we're really really excited to be joining polygon um obviously polygon has had incredible success in attracting users and developers um but i think what's really impressed us is their vision for the future and their commitment to zk scaling um and so over the past few months we've had the privilege of working with um with hermes and with maidan and it's already been a really fruitful uh collaboration and we're really really excited to uh to be a polygons hero i think on behalf of of me and daniel we're also really really excited to be coming back to the ethereum community ethereum is how we both got into crypto uh in the first place and um you know it's it's a privilege to work alongside so many great teams uh to to scale ethereum um so i'm gonna give a little overview of what we've been working on and then i'm going to hand it over to to daniel and some of our team members to give a little bit a little bit more technical detail [Music] but i'd like to open with this so in the history of computing um there's this thing that happens which is when you increase computing speed by 10x uh you unlock radically new applications so this has been true across platforms so for the pc for gaming for mobile every time you you deliver processors that are 10x faster the sk the space of things that you can build and the possibilities increases dramatically and so i guess from that perspective we view uh zkp's as sort of a new computing platform and we'd like to pose a question to the ethereum community which is what can you do with zkp's that are 100x faster specifically recursive ekps that will allow us to build things like more decentralized more performant roll-ups new ways to provide privacy to users um and so we're just going to talk a little bit about about how we've done this what we mean by recursive zero-knowledge proofs and sort of go from there so uh recursion is is really important um for for for scalable zk roll ups because as we know uh the premise behind a a zk roll up is that we can take um a large number of transactions that would be too expensive to verify on the ethereum main chain and instead we can process them off-chain and generate a succinct proof that shows that all those transactions are valid um we can provide sort of the necessary state updates or uh you know depending on the data availability scheme um and that allows us to to scale uh transaction throughput while still maintaining the properties that we love about ethereum that it's decentralized and that's secure so the issue with zika rollups right now is that it's actually really expensive to uh to generate a proof showing that a large number of transactions are valid um this is especially true for zk roll ups that support general applications and even more so for for zika roll-ups that sort of support evm compatibility and so what recursion allows us to do is instead of taking a single proof that verifies uh say ten thousand transactions we can instead generate ten thousand proofs to each verify one transaction we can do all this in parallel and then we can recursively aggregate um and so we're able to generate the final proof that we post to ethereum uh more efficiently so uh so we view sort of this breakthrough in recursive proof uh generation as as being really important for the future of zk rollups on ethereum um [Music] so for some context on how we got here um recursive proofs have only been available in practice since about 2014. before that they existed only in academic papers um so when we started mir in 2019 it took two minutes to generate a recursive proof and so we realized very early that this would never work like we if we wanted to provide uh high throughput and and something that could scale we needed to fundamentally improve um proof generation time for for recursion um because even if we were uh sort of taking advantage of parallelism uh that only gets us so far this still represents um way too much latency for for the performance characteristics that we'd like so uh in 2020s two things happened so um the brilliant team at aztec developed the first implementation of recursion on ethereum uh based on planck and the kcg polynomial commitment scheme um so proof times were about 60 seconds on a desktop and so this was a huge leap forward for for rollups at the same time we developed a plot plonky which is a combination of clock and halo and it allowed us to achieve uh 15 second uh proving times um but the problem was is that uh the problem was that this wasn't ethereum compatible so we couldn't use these faster provers on ethereum and so now i guess uh we uh we're really happy to announce um plonky ii which is a new proving system based on uh planck fry and uh some wizardry from our own team um and so i think it's really important to to sort of give credit where credit's due um and we uh this advances is based uh a lot on um really brilliant work from from zach and ariel uh uh at aztec um and who developed block and then um the extremely talented scientists at starkware who developed fry and so this represents a 100x speedup for recursive proofs on ethereum so plonky 2 is fully transparent there's no trusted setup no toxic waste it's natively ethereum compatible so it takes about a million gas to verify monkey tube proof and this is a constant like we could have a recursive proof that verifies a million transactions it still only costs 1 million gas to verify in ethereum and so i think what we're really excited about is that this is a big step forward for the space because now we're measuring recursive proof generation time not in seconds but in milliseconds and so what we have achieved is 170 millisecond recursive proof generation on a macbook pro so on my macbook air it's a little bit slower it's about 300 milliseconds but this is still a huge step forward for the space it's the fastest uh implementation of recursive proofs ever and it works natively on ethereum and so actually i think that i can show this um we'll see on zoom if it slows it down a little bit but yeah so about uh 355 milliseconds um right now so yeah we're proud of that and so all of this is sort of in service to developing polygon zero which is the most scalable zkevm uh powered by plunky ii um and so we believe that zk rollups are going to compete on speed and on cost and we believe that we're building the most scalable evm compatible zk layer 2. so the goal is to allow developers to compile their existing solidity code to run effectively unchanged on a zkbm and uh we think that this is really important um for ethereum and and for the crypto space in general because uh our goal is to provide scalability um without compromising on the things that make ethereum so important and so special for the space so we we view this as as sort of a route to scaling throughput without compromising on decentralization or on security um so we're really excited uh to talk a little bit more about this in greater technical detail and so i'm going to hand it over to daniel okay thanks brendan so why are we so focused on performance here uh generating these proofs can be very expensive especially if we're proving something like an evm program which is a really conventional design it wasn't designed for snarks so it has features like arbitrary control flow random access and all kinds of binary arithmetic these aren't features that are natively supported by snark primitives we can simulate them but there's quite a bit of overhead so on the right here i took this benchmark from one of the old tiny ramp papers tiny ram is this virtual machine that can be can be we can prove the execution of and the authors measured basically the simulated clock rate of this vm and as you can see it took about 33 seconds just to prove one cycle of execution so if we compare this to a real hardware cpu which would typically run at around 3.3 gigahertz this is a performance gap of 11 orders of magnitude now to be fair this is an older paper and we do have some modern techniques that can help to narrow this gap but this is still a big challenge to say the least especially with the evm because this was a 16-bit machine whereas the evm is fundamentally a a 256-bit machine so when we started this project we wanted to collect some real data about what sort of computations we're dealing with uh so we spun up an ethereum node and we recorded a bunch of blocks and we looked at basically what's going on in terms of that for example we found that the average transaction executes about 3 400 instructions in total which doesn't sound like that much but some of these constructions are relatively expensive so for example we have uh the average transaction executes 88 of these and instructions this is a bitwise and involving 256 bits and on hardware this would be pretty trivial but in in snarks since it's not natively supported we have to either do it bit by bit or we can use lookup tables or other techniques but there's still a lot of overhead either way the other thing that concerned us a bit here is this shaw 3 instruction the straw 3 is this ketchup hash and it involves hundreds of thousands of bit operations just to evaluate a single hash and the average transaction does 13 of them so uh this might sound pretty negative so far but it's okay we can still make this fast we just have to be incredibly focused on performance so with that in mind let's look at some of the proof schemes that we could consider using we basically considered three options the first is schemes based on kcg like plonk and kcg is this polynomial commitment scheme based on pairings it has some nice properties it has very small opening proofs so a whole argument can be less than a kilobyte it's easy to verify on ethereum however the challenge here is that it's hard to do recursion with pairings there are a few different approaches here but none of the results look look really good for performance so next we considered these schemes based on halo halo is this idea that came out a couple of years ago and it provides this really clever way to do recursive proofs without pairings using elliptic curves that are not pairing friendly um and we actually implemented this as brenton mentioned in our library plucky and we were able to get decent prover speed and a decent recursion threshold this way but the problem as brenton mentioned is that halo takes linear time to verify so it just really isn't practical to verify on ethereum unless we combine this with other techniques and finally we have schemes based on fry like starks and these are particularly interesting because there isn't really one set of performance numbers for these proofs it really depends on the settings that we use them with so fry has this parameter called the blow up factor which is basically a measure of how much redundancy we add to a polynomial before we generate the commitment to it and if we want a really fast prover we can use a small blow factor which means less redundancy so we have less data that we we're committing to and proving will be faster however the caveat here is that a smaller blow factor i mean reduces the security of the fry protocol and we have to compensate for this by running more queries and this increases proof size so we have this dilemma where we can either choose a fast prover or small proofs but we can't really have both at the same time luckily recursion helps us here so with recursion we can take a larger proof and we can shrink it by wrapping it in in a proof in a recursive proof with a larger blowout factor and that's exactly what we do in our zk roll up so we start with transaction proofs that we want to be as fast as possible and here we use a block factor of two to to really maximize the prover speed and at first we have these really large proofs because of that but that doesn't really matter because we they just stay on my computer we don't send them to anybody instead we immediately shrink them by wrapping them in a recursive proof with a larger blow-up factor of eight this brings the size down to about 115 kilobytes which is more manageable but if we're going to submit a proof to ethereum which charges 16 gas per byte then we'd still like them to be smaller so before sending approved to ethereum we apply the same technique but more aggressively with a blob factor of 256 and this brings the size down to about 45 kilobytes which is great uh these proofs do take a bit longer to generate but it doesn't really matter because um we only have a small number of proofs that have to be sent to ethereum okay so the other thing we can do to really maximize the prover speed is instead of using a 256 bit field like most snarks do we can encode the witness in a 64-bit field and this is much faster especially for field multiplication because typically quadratic algorithms are used there so we can make it about 30 40 times faster by using a smaller field there are a couple of complications here one is that the protocol assumes a larger field of at least 100 something bits um so here we borrow this idea from heath stark which is we include the witness in the small field and then when we run the fire protocol we run it in an extension field of this 64-bit field uh that way we can get the same security of having a larger field it's just not a prime field but that's fine fry doesn't require that there are also a couple of complications with the planck protocol where certain in certain places planck assumes a larger field for security so we could apply the same technique and run those protocols in this extension field in some cases we do that but in other cases we use another workaround which is to keep using the small field but we repeat some of the checks in the plonk protocol in order to boost soundness and that's it for me now i'll hand it to william okay thanks daniel so yeah i'll talk about the recursive circuit optimizations we use in planky 2. so first a quick intro on proof recreation the basic idea is that in a proof system we have both approver and a verifier and for proof recursion what we do is we write the verifier inside the circuit and that allows us to verify a proof inside another proof okay this sounds easy but historically it's been a really hard problem to design efficient records of proof systems and recently there's been some research on on that um in particular on accommodation schemes with halo but those have many drawbacks as we saw in terms of performance and so our solution to this problem is to use planck with a fryer-based printable commitment but now if you try to write naively the verifier in a circuit you'll end up with a quite a large circuit with 2 to the 16 gates so around 60 000 gates which is okay but the proofer is a bit slow so around 10 seconds and so we really focused on on bringing this number down um so first a quick recap on planck so in planck you have a table of field elements and on each row of the table you have a pair of number constraints that evaluate to zero and each row can have different constraints and so if you go and look at the original plonk paper you'll see that they use a table of which three so only three columns and and most planck implementations use between 10 and 20 columns but we decided to to use a much wider table with a width of 135 okay and um this may sound like a lot at first but the design of our system is sort of it's it's really okay for example we can commit to all the columns with just one numerical route with other printable commitments you would have to commit to each column individually which would be terrible for performance but we can just do it with one local route but so why do we need such a wide table is uh to design complex gate okay so for example in the fry refiner there is this complex operation which is interpolation um so we have eight pairs of points x0 y0 to x7 y7 and another point z and we have to interpolate a polynomial of degree seven on this pairs and evaluate it at z okay so that's quite a complex operation that would take a lot of gates if we did it with a classic planck but with our white table we can actually do it in one gate okay so how do we do so we start by finding the interpolation polynomial f outside the circuit and then we evaluate it at z to get the value of v and then we put all these variables in a single row as you can see on the bottom right and then we have a bunch of constraints on this row the first set of constraints checks that f is indeed the interpolation polynomial of the pairs and then we add a constraint to check that f of z equals v okay another thing we can do with our white table is hashing in one row right so the fry verifier uses a lot of hashes like currently they make up 75 percent of the circuit so it's crucial to us um to have uh hashing as efficient as possible inside the circuit and we decided to use poseidon which is an algebraic hash so a hash designed for arithmetic circuits and it's quite a popular hash and it's used by other teams in the space but what's special about plunket2 is that we can actually do one poseidon permutation in just one row okay so in in some sense 2 is as optimal as possible in terms of hashing and so this is like a [Music] the most common optimization we used in plenty too is exactly this so we have a complex operation in the fry verifier and then we use our white table to write complex gate to do these operations one one other nice optimization we use is what we call miracle caps so the fry verifier does a lot of miracle proof verifications so on the left here you have a classic microproof verification so you start at a leaf and then you hash your node with its siblings um until you go up to the merkle root and uh you compare the hash to get with the merkle root and except if they are very cool but what you can do is you can save hash hashes by stopping at the second layer so on the right we stop at the second layer and we compare the hash with the second element of the second layer and so this layer we call it the merkle cap so that's a cap of height one and uh instead of committing to the root we commit to this miracle cap okay you can also have a miracle cap of i two or three and those save two or three hashes and so this sounds like a small optimization but since we do so many micropro verifications in the circuit they add up to to a nice improvement and and what's cool is that the this cap height is a parameter in the code that we can tune to optimize either for proof speed or proof size and and we have quite a few of these parameters um daniel mentioned the fry rate okay and so we can tune this parameters um to optimize for speed or proof size so this makes plunking into a quite a versatile printing system and all these optimizations add up to a nice result that we're really proud of is that our recursive circuit is like really small at two to twelve gates so that's around four thousand gates um and this is one of the main reasons why we can have such uh fast proving times um yeah and now i'll let jacob talk about low level optimizations alrighty um so let's talk about speed we've talked about high level optimizations we talked about optimizations to the circuits now let's talk about how we implement the very lowest level things i'm talking like multiplication really really fast how do you make math fast to make math fast you need both mathematical insight and technical expertise an engineer can take a spec and write code that runs really really fast on whatever hardware you're using an excellent mathematician can take whatever work needs to be done and minimize the number of some fundamental operations and like multiplication but you know finite field multiplication is fundamental mathematically not physically there is no logic gate for financial multiplication so so the mathematician only really sees a proxy um on the other hand for the engineer the spec is immutable there's only so far that software engineering tricks can take you and a spec can only run so fast to make math fast you need to flip the causation right the work that you that you're doing needs to be determined by um the physical reality of the hardware that you are doing it on plunky 2 is built for performance right when we were designing the protocol we were already thinking about how fast it would be running on commodity hardware the earliest of decisions in planky 2 were already guided by performance let me give you an example when you're doing mathematics in these kinds of groups you're working with a prime field fp where p is some sort of a prime number oh what's a good choice for p that's a very fundamental question well firstly it needs to fit within 64 bits like daniel's already mentioned and the reason why is that computers modern computers are 64-bit machines and once you've crossed the 64-bit boundary everything suddenly gets so much more expensive but it also can't be much smaller than 64 bits for security reasons so you want it to be almost 64 bits but not quite and a different choices of p will also have different algorithms for multiplication and addition with different performance characteristics so we want to choose p such that um multiplication and addition those fundamental operations are really fast so we went through a lot of candidates here's a github thread where we documented our research we considered many fields each one with their own algorithms for arithmetic operations we derived those algorithms we examined the compiled assembly code we counted cycles and micro ups and what we ended up settling on is this really neat prime number um that has a frankly beautiful mathematical structure that just happens to play really well with how modern cpus and isis work let me give you another example as williams already mentioned we spend a lot of time doing hashing and the hashing algorithm we use is called poseidon within poseidon we use an mds matrix for a particular step and the mds matrix is up to us to choose as long as it meets particular criteria and we spend a lot of time doing matrix vector multiplication with this matrix so so it's important to get the matrix right to make that particular matrix multiplication fast there's a few tricks that we use um in order to choose a good value so our the choice for the mds matrix is firstly circulant what that means is that every row is just above it but shifted by one position it means that there's fewer numbers for us to have to remember and this we're spending a lot less time just loading constants from memory which makes our code faster secondly this matrix is composed of powers of two and multiplication by powers of two is way faster on a computer because you're just shifting the bits by some amount as opposed to actually having to go through all the steps of multiplication um these powers are small which makes the finalization at the end like way cheaper and a lot of these elements are one which is like multiplication by one is free like you just don't do anything um we make extensive use of vector operations so most of the code that your computer runs is scalar the computer kind of takes let's say addition you have two numbers and um there's an additional instruction that takes two numbers and returns the sum as one number but your computer also has what we call vector instructions so these do more with one instruction as long as you're doing the same thing for multiple values so you might have a vector of four numbers and you there's an instruction to add that to another vector for numbers um getting four sums as the result in one vector compilers are generally bad at generating these kinds of instructions so if you really want to make use of this that's a lot of work for the program um in planky 2 we make extensive use of vector instructions and this was a lot of work for us uh but it's really worth it so back the instructions give us a two times improvement on poseidon in addition to that uh there's a bunch of asms scattered in the code base so so for example the top one made finite field multiplication 10 percent faster the bottom screenshots are from parts of our poseidon implementations on arm and on x86 look the result of all this work is lightning fast zero knowledge proofs right and you've seen the impressive results from brandon but we're only getting faster there's still no gpus involved for example um we didn't think that you that we wanted our users to need gpus to run uh clunky too uh and i i'm looking forward to how fast we can get in the future the reason that we were able to do this at polygon zero is that we are both excellent mathematicians and also hardcore computer scientists you know it's not often that you get to work on something truly groundbreaking and i feel extremely lucky to have had the chance to work with such a bloody fantastic team right i really can't believe that i get to work with my co-workers because they're just amazing and i am really excited for what we will be able to achieve in the future um and we'll have to take questions jacob and team thank you so much for that amazing presentation and just kind of walking through all these improvements uh we do kind of have uh a small caveat which is we are running a little bit behind so we'll have to cut the q a short but there's one question in the audience and that question was just overall kind of how do you think about now uh new application to sort of enable uh more things with uh just the polygon ecosystem and and also the ethereum side just like with these improvements with these new performance metrics how do you think about just the evm world and what would not be possible here um yep even that tastes really karthik so probably you know i should take this disclosure question and uh you know you just also wanted to you know put a closing note also that you know how this adds immense amount of value to the overall ethereum ecosystem and polygon ecosystem uh you know is that this this prover system like uh you know many who understands the zika technology they know that this is the most efficient and the fastest vk approver system and this will enable us to create a very high uh performance highly decentralized uh uh zika roll-up uh or evm compatible zika roll-up which will you can already imagine that if these uh you know this will provide full security by ethereum and then you know imagine uh you have a zika roll up where it provides ethereum uh you know full security by ethereum and the apps can use that roll up at a much uh you know low cost transactions by using validium kind of systems or you know later on with e 2.

0 data shards it it has a potential to provide a massive scalability to uh you know the to the dap ecosystem and polygon already has a huge dab ecosystem uh which which is you know we we keep getting these demands that you know we need to have more uh you know ethereum secured uh you know and decentralized layer two and i think this will this this takes polygon community very close to that that dream and then what what uh brandon and team and daniel team are building is you know would also provide like this is like a bit technical uh getting into it but you know might also provide an a virtual machine which has more op codes to use to the developers uh you know relevant to the question uh you know that uh you can like the apps on this uh you know layer two can actually run more uh opcodes like that means more functionality more features uh on this one while still be fully approvable uh you know on on ethereum so this is really really massive for polygon and uh you know with that closing note i you know want to congratulate the entire polygon community that uh you know uh this this uh establishes polygon at uh one of the top most player in the zika space and and you know let's let's uh build a highly adopted uh ethereum layer too and bring the you know mass adoption to ethereum thanks a lot karthik over to you thanks everybody and uh congrats again to the polygons of your team [Music] [Applause]