The verkle advantage by Guillaume Ballet | Devcon SEA

[Music] uh yeah so thanks for coming um I assume if you're here or uh that's because you might have heard in the past few months some uh some voice saying maybe veral is uh you know should be replaced with starked binary trees and the purpose of this presentation is to give you some arguments to understand why uh now is not the the right time to do this uh let's briefly go over the current status of veral trees uh the veral tree implementation in ethereum uh we launched a devet two two weeks ago it's uh chugging along fine uh we have something that is pretty close to the final spec we're missing a couple gas costs here and there but nothing uh nothing that won't be fixed by by the next devet um and you can go have a look at at this address it will be displayed again at the end one of the biggest things we achieved during the last uh during the last year was a holis sky Shadow Fork uh we validated that the transition model works so we're really proud of that and big shout shout out to devop for helping us through this because that was uh that was quite uh quite something and yes the elephant has landed that's uh that's because the spirit animal of the stateless Fork is uh is the elephant we simplified and clarified so there was a big work of uh simplification clarification of the gas cost EIP so veral is split into two eips one of them is 4762 the gas cost they pertain to stateless and then there's 6800 which is the pure description of the tree um so you know we we had a lot of questions uh about it it caused a lot of corner cases we addressed all of that uh so I'm not going to say it's completely ready because we still need to take into account eof 7702 and I'm sure a billion things that will come in the next two forks but um it's it's looking pretty Advanced and pretty mature at this point we also implemented execution the the execution spec test framework so until now when we wanted to make sure clients agree that we don't have any consensus bugs we used to uh we used to launch a test net and and verify but now we don't even have to to do this uh we just have tests that Target a specific use case so uh big shout out to ignasio and of course the testing team for uh for working on this one because uh we found countless bugs before we even had to launch um so yeah that was that was also a great progress this year and then uh there's been experiment ments in implementing veral friendly sync uh so this one was actually done by nether Mine by Tanish and nether mine and uh it's the first feature full feature that has been implemented in that hasn't first been implemented in guest so big uh big sh shout out to to Tanish again um right and the last uh the last thing that we achieved last year was the state expiry um like we there was an EIP that was uh by hand he did a very good presentation this morning about it so I if you haven't seen it I suggest you go you go and watch it but just to give you a quick rundown uh the idea is that veral veral trees um are pulling their um their leaves together by groups of 256 and then they have some kind of extension stem on top of it uh and the commitment which commits to the to the the orange uh to The Orange Box which is the commitment um what we do is we add a new field um that used to be zero and now it's the epoch number so it's backwards compatible it's really good and uh when you want to uh delete some data you just delete the whole 266 values and you just keep the commitment and because everything is polinomial based you can re uh provide a proof of the entire sub tree so you have to resurrect the the whole sub Tree in one go but uh it's great because effectively you only keep the internal nodes and the internal nodes is where veral trees especially shine this is what takes the less space in the whole in the whole thing so it will provide a state expiry scheme that is efficient that that is pretty much TurnKey we could activate on day it on day one of veral and uh and yes it's uh it's very simple in the sense you don't need address space extension you don't need to do any modification it's really working out of the box so the conclusion is that after four years uh veral is pretty much uh ready for its prime um of course I'm not going to pretend it's uh ready to ship tomorrow we still have a couple things to do but I think um within a year we'll we'll be uh we'll be you know a year of focused work of course uh we could be ready to we could be ready to ship um let's go over the pros and cons of veral to for the rest of this discussion the first pro uh is that if you take the veral proof and the veral witness this is really small and this is like much smaller than anything any alternative you can think of uh we had several experiments uh and we found some encoding that is especially efficient so it's it's known as type three here um the average size is uh two like 400 KOB less than 400 kilobytes and the worst case that we observed so we replayed historical blocks uh caveat of course they did not because they're historical block they didn't have the whole vertical gas cost in activated but it's still a very interesting uh um yeah like reference uh what we see is that the worst case is less than 1 Megabyte uh the theoretical worst case is 3 megabytes but on average it's less than 400 uh um kilobytes which is really good because you've probably have heard about increasing the gas limit uh increasing the blob count all all of this is going to have an impact on the bandwidth so the fact we have a very efficient um proof structure something that like we will add some some size but adding very little compared to any any other option is a is definitely a plus um the trees itself is small um we it's like on average from measurements we've made so we take an MPT we convert it to veral and we see what the end result is it's about 25 person smaller we have optimizations where we could shave yet another 10 maybe 10 20 20 gab still um but more importantly it's uh also changing the way we store the data so you can write to the DB DB more efficiently at least the guest DB this is my my reference uh so this is something that's very useful um one of the really good things about verical or at least stateless actually it's not even just verle but you can immediately join the network when you want to sync and then uh you can download the data you're missing if you want to build a full you can download the data you're missing in the background but unlike the current uh experience where you just wait for the blocks to be downloaded and then the state and then you hope that you've got everything in uh in order to be able to to be able to to follow the chain you start following the chain right off the bat and only then do you uh do you worry about downloading the data um so if you want to compare the the idea of a vertical sync to the current state of snap sync what happens in snap sync is that you start downloading the the state here uh this and uh I'm using Sprouts because uh I want to point out that the data at this stage is fresh it's the latest data you've got but as blocks keep being added to the chain uh the node keeps downloading data but the old data uh like the data that was downloaded before is actually becoming stale so this is represented by um by uh dried leaves so what you have to do is go to the network and ask nodes that are synced to send you the data that is Obsolete and uh update it and keep it fresh but while you do this of course the chain keeps advancing so the data is some other part of the data is becoming obsolete and as a result um you need to hope that this dance and this communication can go fast enough that you can uh hope to sync up to the uh to the to the head of the chain in a reasonable time this uh this is the problem that might hit us at some point especially if we stress the chain with uh with increasing the gas limit um inre like lowering the block time whatever there's a few things that can happen that will make this even uh even more difficult with vertical sync uh you have what I call the instant heel because the block contains extra data here that is a proof that uh a proof plus the the pre-state and the pre-state is everything you need to execute the block so as you download the data here it's sparse but it could be linear it doesn't matter um you have the same problem of what you have becoming stale but at the same time all the all the data that you need to heal the the the the state you've got the the stale state is already uh provided in the block so you can immediately heal it you don't have to go over the network so that makes for a much much faster sync and eventually you get the whole data downloaded and and that's it um so now let's uh there's there's a point that uh veral is not perfect there's no Quantum resistance especially uh well in two places really the proof computation and the uh the balancing of the tree you could craft uh keys that in such a way that the tree would be unbalance which is really computation would make recomputing the state rot computation intensive um another issue with uh with veral trees is that uh even though they've been designed to be ZK friendly they're not the most efficient structure for the latest and greatest of uh ZK ZK technology as I call it however you want um so there are potent bunch of potential fixes one of them is that at least for the three and balancing you could simply use a regular um hash and that would that problem would be solved it would also make veral uh veral trees much faster because the pon hashing is one of the one of the biggest um uh waste of time uh speaking of uh time I'm getting a bit uh a bit late so I'm going to skip the rest of this slide and switch uh and go on to to Binary trees so there are good things about um about binary trees it's Quantum secure I mean at least if you use the the correct hash function uh the hash functions are faster and it does play nice uh with all the fancy new new ZK Tech especially Starks like circle circle Starks binus uh whatever the bad part is that um unless you do have proper uh performance which might happen soon if Poseidon is fast enough for example but if it's not we're still a bit wanting in in this respect um then uh you will have to use binary like just binary mer proofs this is not very good because it will make proofs much uh bigger even if you activate uh ZK well sorry not ZK but Starks if you use binary Tres with Starks um what you will get is a um is a proof plus witness that is twice at least uh twice as big as the veral proof so we were talking about bandwidth this will have a cost like there's a trade-off here U and then the tree because there are more noes the tree will be significantly larger so caveat here we're working on someon coding that might not make it it as true as what I just stated but this is like the current state of uh yeah the State ofthe art that might I I might change my tune in in a week or two but currently this is this is a fact um and it doesn't solve the what I call the syn race issue you still need to ask someone to Pro provide you with a proof maybe a star proof this is quite uh computationally intensive to provide so the problem Still Remains okay let's get to the to the big question should we skip veral uh and go straight to uh binary trees so that was to be clear that was already the that was always the the goal right uh vertical trees are here in the middle it's the big uh it's the big uh blue square but if you look at uh later there's Quantum like the end game I would call um is the Quantum safe stocks um this this like stepping uh stepping over uh veral would you know has a few assumptions the first thing is that the end game Remains the Same uh we don't decide to add more features or we don't decide to go in a in another Direction um maybe you've heard about beam chain you know uh there was a direction that was given and all of a sudden we're talking about changing changing directions this has always been the case in ethereum um since been uh in part of the community so this is extremely likely that the end game will change um it also assume that that the argument is always well you know we will have to do two two transitions instead of one this is the least likely to be true uh of all these assumptions because um right now you want to have binary Tres with Starks in the hope that the technology that you use will be the one that you can use to um you know start the entire block uh block execution not just the tree root computation but because you delivered this in two steps there will be something new coming up that uh will you know maybe not play as nicely with uh the technology you chose to compute the tree rout so I would say there's a big question mark here um and also what if uh you could find and you know research has barely started on this and not is also not as as active as it should be but theoretically you could find a way to do a z ZK ZK friendly uh sorry ZK and uh Quantum resistant u veral tree it also assume oh sorry I went a bit fast uh it assumes that posidon is secure uh we're like the E theum Foundation is about to create a some some kind of Grant to try to break posidon because posidon did not get enough scrutiny um and then uh also there's a big question of whether or not we want to be able uh or what do we do for example if uh producing a stark proof in in an acceptable time can only be done in Big Data Centers um can uh do we you know do we turn our backs on the ethereum itos of of solo building solo blog building and solo blog proving um this is a big question to have so there's a lot of political there's also a political dimension for this um and then yeah like I was uh I mean like I revealed before uh there's also the like this tweet proves that there's a lot of um innovation in ZK right now the the one um the or at least tree proving State proving uh the one technology that we're talking about right now will be obsolete in six months um so it might make sense to just take it easy wait for this um frenzy to to stabilize a bit and then uh make the decision um and uh yes well there's of course the quantum Computing risk there's a lot there seems to be a kind of a moral Panic right now about Quantum Computing I am a skeptic I'm not going to hide this but uh yeah there's a like your guess is as good as mine should we Panic about something that should that might not ever exist um yeah we don't really understand uh decoherence is it possible to count to have as many Q bits as uh as we uh as would be needed to break uh to Break um uh to fake a veral proof well I don't know the future will tell us um so yeah like the one of the problems also with this question of skipping verle is you are uh effectively comparing something that is ready to ship quasy ready ready to ship with something that is quite undefined so there's still a huge uh specification work that needs to be done done and has barely started we don't know what the exact structure of the binary tree would be uh we don't know what the witness would look like does it contain uh does it contain uh all the state diffs um this is being answered as uh but maybe not as we speak but this is this is being answer debated and we we need to reach a conclusion but we haven't so far um is posidon secure if Poseidon is not secure well we need to go to chatau 56 this is much harder to prove uh in a in a circuit uh which proving system this is what I was saying before we need to we need to make sure that um that we have the best technology for for the job and uh yeah there's also a question of values do we want to only build blocks and proof blocks in data centers or do we want to do on a Raspberry Pi surely the question is the answer is somewhere in the middle but it needs to be discussed and uh and agreed upon um let me add the to the to that point that the more uncertainty you add the more delays you add because questions need to be answered those questions I just mentioned uh and you have the choice between the imperfect technology that bring uh that you can have now and the perfect technology that never will be um if um yeah there there will always be an improvement in fact you know what happens to veral right now will happen to Binary trees where start there will be something better uh veral displaced binary trees without Stark so it's definitely going to happen uh in my view done is better than perfect um and I would say ethereum has a history um so for those who don't know I was uh with M Kini and Danny Ryan I built the first prototype uh to do the to do the merge um the exact same thing happened there were lots of ideas but nothing was being delivered so we sat down we designed a very simple engine API done was better than perfect ethereum Advanced and I think the problem of ethereum right now is that it doesn't make those leaps it keeps living in that future and toying with a lot of ideas that will never happen right now veral exists veral is there it's the strongest Val it's the only value proposition at this St stage so um we I think it makes sense to keep working on it but to be clear veral has been uh or at least stateless has been built with upgradeability uh re reusability in in in mind so we will change the tree structure but the gas cost would not change the state conversion would not change like all those methods have been validated um the historical root contract like 20 2935 could be used State expiry to be confirmed but should be a reusable verbatim as well um so that's uh yeah that's reassuring I think uh we can afford to push the question of binary trees to a time where it's more defined um that's pretty much it go uh check verino to have all the all the news and ctin and test net to check our latest test net come break it help us uh help us build it um yep thank you for the wonderful talk Gom let's turn our attention to questions if ethereum Al adopts fkl uh should rollups also adopt it yeah that's a good question um there are good I mean it's always a question of maintaining a diff so if you think um that uh so yeah there's this thing called rollup guas uh that tries to be a fork of guas and uh you know maintain a standard base maybe rollup guas could Implement binary trees if they want uh but should they um I mean I don't know do you are you interested in a smaller dis footprint small proofs and uh and uh something that's readily available I'd say yeah uh I'm not going to tell rollups what to do I'm saying I think it's also a strong value proposition for rollups how do veral trees help with stateless clients um I mean it's a technology that okay it basically makes very small proofs so you can attach it to the block and as a result uh stateless clients just download one block and they're following it's I mean they're considered to be following the chain that it's uh completely secure so that's uh that's their power are there any major trade-offs of verl trees over merkl Patricia tries uh it's a bit uh I mean it's like maybe an order of magnitude it's still very fast but it's slower to to compute the root commitment in veral trees so blocks tend to be a bit slower to build okay um how do veral trees generate 01 proofs um by the magic of uh how would I say that so yes because I know the that's probably the question is probably because we use IPA and IPA is logarithmic but uh it's logarithmic on constant Vector so uh it's effectively uh o1 proof if you want some details uh we can talk about this after the after the talk how would a Quantum attack work on veral is it important to consider Quantum resistance it's only important if quantum uh quantum computers are real um how would a netac work on veral uh yeah I skimmed a bit over it uh you could either unbalance the tree but that's easy to fix or you could create fake proofs in that case what would happen is that all the stateless clients would accept a block and all the stateful client would realize that the proof is completely nonsense and would reject the block so the network would uh would split um that comes at a cost of course because uh obviously if quantum computers happen then veral is of the table we're not doing that anymore but the question is what happens if no one knows you have a quantum computer in that cas case you would reveal like you would show your deck to everybody um so and the result of doing this uh would be that um you know you would be a newens to ethereum for a couple couple days but then everybody would just go back to having State stateful clients so yeah that would be a usability drop uh potentially um you know a big headache for core developers But ultimately that's a big price to pay to to just annoy a few people what about Legacy data if uh veral trees are adopted on Main net the whole thing is converted uh so nothing is lost okay uh what's your opinion regarding the post by vitalic to wait longer and do more research into ZK instead of doing veral trees soon uh I mean the whole presentation uh is my answer but to be fair just uh vitalic you know is more like it's a it's an idea it's not like it's not like he's hardcore decided on it I have a screenshot that says veral might be the last thing that we do that is not Quantum resistant well the next one's more of a command than a question but stop delaying veral and ship it instead of other non-urgent features do you have would you like to comment on no no I think people know my opinion that's uh enough has been said okay great and how does PCS multi prooof with random evaluation work on veral trees I tried hard but I'm too stupid to understand CRI oji * 2 um yeah it's quite hard uh we we can definitely explain uh just maybe not in 37 seconds okay and as a last one uh what is your take on the bandwidth disc trade-off I think uh well bandwidth is going to be the biggest resource in the future my just my personal opinion um so whatever uh whatever makes uh improves the bandwidth requirement is is is a good thing um dis is also a good thing uh but I think at this point veral is going to come too late to prevent the the switch to requiring 4 terabyte hard drive all right that's it for questions thank you very