# Stateless Ethereum - the benefits for users, node operators and bridge - Valentin Mixov | Daedalus

- Channel: [ETH Belgrade Community](https://streameth.org/eth-belgrade-community)
- Date: 2023-10-07
- Duration: 38:40
- Watch: https://streameth.org/watch/yt-CSqqmIh9_hI
- YouTube: https://www.youtube.com/watch?v=CSqqmIh9_hI

## Transcript

always interested into like math and data structures and stuff and today we're gonna talk about the future of ethereum like what is going to happen and this is the ethereum roadmap Maybe some of you if you've seen it actually here uh maybe just a quick check how many of you are actually coming from like web 2 not like web free people but like web to people that uh okay okay so I think most people here are kind of part of the web free so it's not yeah somebody that sees that for the first time but yeah for for the web to people so this is a diagram that shows basically the road map of ethereum so what is going to happen in the future and it's split into a couple of stages and one of them which is the one that we're gonna talk today is called The Verge and this is the part about implementing some new data structures about how uh the state of ethereum is going to be kept and this is about making the ethereum stateless and we're gonna see what actually this means so what is the current problem when you sync a new ethereum node it's going to take a lot of time a few days maybe like maybe a week that all the states that you need to download and process right now is around two terabytes and it's increasing so you can't actually run a node on your mobile phone even if it's a Solana phone no that's gonna work um also you basically because of this you basically need to use a centralized RPC provider so you need to rely on somebody else to tell you what is going on right now ethereum like how much I I need to pay to buy it from unislab for example like you need to rely on on a centralized third party and we actually yesterday there was a panel about infrastructure and Dev tooling and there were people on stage that are their business is basically running nodes and they were explaining that it's getting harder and harder to run these nodes and there is actually this example that on binance Smart chain right now it's impossible to sing a new note from the very beginning it just there is no uh big enough Hardware in the world that is going to allow you to do that now for ethereum that's not the case you can like run a full node and it's going to take a few days but yeah like for Solana also that's uh very problematic and another thing that is also the kind of a status quo right now is um the bridges uh Bridges right now they rely on message passing and in order to pass these messages you need to rely on somebody like us maybe not like a centralized entity but maybe like a set of validators like a separate set of validators that no it's just additional security assumptions so that's not ideal and we actually see what happens sometimes you know with Wormhole hack and with multi-chain problem now um where you know we can't find the CEO so money are stuck sorry guys um so let's dive into a little bit of technical detail so the current state is the following so everything on ethereum like the database of ethereum is kept in a so-called merko tree and a Marco tree here it's like a simplified uh version of it you can imagine it it's like a tree and all the data is at the leaves this is like where everything is kept so you can imagine this is just a key value store so we have like keys and we have values all the values are at the leaves and then for each Leaf we compute the hash and then for each two uh for every siblings of of each node we compute the hash of the two hashes or like the the other HS and now we we do hashing hashing hashing and we end up with a single hash and this is the root of the Merkel tree and this is basically the the the fingerprint about the current database of ethereum like if the fingerprints match of what we compute it and what somebody else is telling us we know that yes he's telling the truth because we can validate that so this is how it basically works and here we're gonna uh just review like the blockchain is basically this thing that you have a state X which has a given State Route which in this case it's like 0x beef we have a bunch of transactions that are in a block these transactions execute on state X and you get state state X plus one so the next the next state this is what called a state transition so you you take State X you execute the transactions you get the new state and it has a new state route and this is like 0x dead in this example so you should be able to execute these uh these Transitions and uh this is how your state evolves now the merko trees they allow you to generate this thing called a witness so when you see witness in basically in the in the blockchain or the cryptography literature what this actually means is that it's just some bytes that you can use to validate that given data is indeed in the in this tree and you can do this in a kind of a a quick way so you don't need to keep the whole database somewhere because you know if you have the whole database and somebody tells you yeah this key the value is that you can check that it's it's easy so we have all the two terabytes but if you have a witness then you don't need all the data only using the witness you can validate yes indeed this data is inside the tree so Marco trees they allow you to have to generate such kind of witness and the way this works is like this so if we have this data which is like D3 here which is like the data that we want to validate that it is in the tree oops so we want to validate that D3 is indeed in our current state so what we need to do is we need to uh just have a list of of a bunch of hashes that are along the path to the root and when we collect these hashes we'll be able to to validate that indeed the the root hash matches and if this D3 is something else then we won't be able to do that like it's it's it will be impossible to to generate such kind of a witness um so this is what basically a witness is now with with Merkel trees what happens is that The Wider this tree is so the more witness uh siblings you have the bigger the sweetness becomes and that's a kind of a problem right now the Merkel Tree in ethereum is like I don't know it's quite wide maybe like 10 or 15 something like that I don't remember the exact number so what happens is that generating these Witnesses for Marco trees um they're actually quite large so it's about one three kilobytes per Witness so uh and where I I'm going here like the idea is that well can we somehow do this state transition without having all the two terabytes on our hard drive so to be able to make sure that yeah indeed these transactions lead to this new state route but without downloading all the data so potentially we can try to use Witnesses for this but in order to generate Witnesses for all the data used for in a block right now for the Merkel 3 that's going to be 18 megabytes and there is a new block every 12 seconds so if we actually implement this then we need to transfer 18 megabytes every block around all the nodes on the network so basically we're going to DDOS the whole network they're just not gonna basically if you want to do this stateless ethereum right now there are ways to do it like technically it's possible but in practice it's it's not because it's just too much data for these Witnesses and given that you know this uh yeah the the state is uh growing and all this like yeah I mean it's it's just not not going to happen um another another um yeah another thing that also complicates the whole thing is that when you have three Orcs you need to uh to keep even more data because you need to be able to to unwind the previous transactions and yeah that's uh that complicates things even more so but theoretically if we have this approach where you we have these Witnesses we will be able to have these State transitions without keeping all the data and now let's look at what a Virgo tree is which is basically a data structure that has this properties that we need and it's actually gonna make it work so you can imagine the Virgo tree is pretty much like a Merkel tree it also allows you to Hash this data although the hashing is done in another way and this another way is we're not going to actually explain how it works because it's you know your head might explode but basically it's not hashing it's not like a sha hash but it's something called polynomial Vector commitment which is uh some Moon math that relies on the elliptic curves and all that kind of stuff but the properties that it has is that the witness now becomes like 200 bytes instead of three kilobytes so it's like orders of magnitude better than using a Marko tree so we can estimate that currently if a block is 15 million gas and we have uh 2000 2500 gas per access to the state we have around 6 000 accesses to the state so that's the amount of Witnesses in the worst case that we we might need so that reduces the total witness size to generate for a block to about one kilobyte and one kilobyte is great like we can transfer this amount of data every 12 seconds now where is the trade-off there is always a trade-off like there is no free lunch in software engineering so the trade-off is that it just takes more time to compute this workout tree to update it but we can see here that it's actually acceptable so um if we go into a little bit like technical details if right now uh you know we can see for Merkel trees um it takes like uh and for ethereum this is the K aery Marco tree uh it's like like Owen to construct and K walk K login to update and this is the the proof size for vircle tree we increase linearly the amount of time it takes to to construct but we have also like order of magnitude smaller proofs and that's like an acceptable trade-off so it's harder to it's it takes more time to update it but given that um computation scales better than bandwidth um that's an unacceptable trade-off so if we look at the the structure of a vircle tree it's pretty much the same like with the merko tree like we're not going to go into the details of how exactly it works because it's like connected with a lot of like polynomials and stuff but basically we have the data in the leaves and then we generate these polynomial Vector commitments you know as as we go up cool so how a stateless block is going to look like in this case so let's say that we transition all we we transition from Merkel trees to Virgo trees and now we want to have stateless theorem so what is going to happen is that every block is going to contain a list of transactions and then together with the list of transactions also going to include all the data that this block needs in order to run as a key value store so we put just you know we because when the validator creates the block he executes it so he knows what data this block uses so he can make a list and say like okay this is the keys and values that will be needed for this block it's going to be included there and also he's going to include a list of witnesses and what this is going to allow is that if I'm a node operator and I download the block I see the list of transactions I need all the data that I need to execute it and now I also have the witnesses and I can make sure that this data is actually correct so I don't need to keep all the two terabytes on my on my machine in order to validate it and this is basically going to allow like to run ethereum node on a on your mobile phone basically so what are like the benefits like the the clear benefits is that you don't need to keep like two terabytes hanging around you don't need like a fast SSD to um uh sync the the latest uh uh the tip of the chain um you basically need only the blocks so you don't need to download anything else um everyone can run a full node now you you don't need to rely on a third-party rpcs in order to validate the data now you're going to need the rpcs for another purpose and that is if you want to actually create transactions if you want to let's say you want to execute a swap on uniswap you need to know what is the current liquidity in order to to make sure that the price is correct so you're going to ask an RPC note that actually has this data in place to tell like okay tell me what is the current price of ethereum on unislab and this RPC note is going to reply to you but it's also going to reply to you with a witness so now you can make sure that the RPC is not lying to you because right now if you rely on a centralized RPC provider he's going to serve you whatever data he wants and actually that's that could be a security issue because if the RPC provider lied to you about the current liquidity on uniswap then you're going to sign a transaction that is going to be unfavorable for you so it's very easy for an RPC node to lie to you that ethereum is like five thousand dollars right now and you're gonna be okay I'm gonna buy this price and and then you submit the transaction and you you're going to be like sandwiched and a name of your Bots are just going to destroy you so if you have Witnesses then the RPC providers will be able to provide you an additional cryptographic proof that like okay this is the witness for the data that I'm giving you and now you can also validate it like on your mobile phone without any additional stuff you're only knowing the route of the the tree that it's not actually lying to you so in in this new world we're going to have like two types of notes we're gonna have like full nodes that are having all the data and we have the stateless light nodes that run like everywhere and light notes are going to ask the phone I was like okay give me just some of the data that I need right now these nodes are going to serve it together with the witnesses and you know uh you'll be able to validate it and it's going to be great another big benefit of transitioning to this new data structure is also that it's much easier to put it in a snark so this is like a zero knowledge like like box that allows you to generate also a proof that the given computation has been carried on so it's not only about a proof that we have certain data but also that a given computation has been done and that's valuable basically to make sure that uh you know we might transition actually in a world where you even don't run the ethereum transactions at all you just receive ZK proofs that the computation for these transactions has been carried on and then using this proof you know you don't need to run the transactions you just verify the ZK proof and then you know it becomes even more lightweight you you basically don't run the evm code at all so workout trees are much more uh snark friendly compared to merko trees and that's because snarks they don't like sha hashes um I think yesterday somebody told me that right now to generate a proof for a single sha hash it takes like one minute which is which is insane like if if you need to generate a proof or like the whole consensus of ethereum it's like billions and billions of caches so that's going to be too complicated to Too Much Time and now okay we saw what is the benefit for for basically the users and like node operators like we're going to make validation so much easier we can easily run nodes but what about the bridges like this is something that we haven't talked about and it's kind of hard to figure out okay what is the connection with Bridges here um so let's just do a little bit of overview how the bridges work and we actually did that in in the beginning so they pass messages but in order to pass these messages they need to facilitate some network of validators like on top of the ethereum consensus usually these validators are not as decentralized as the ethereum validators so that's a kind of a problem and these are basically like uh very centralization points and actually vitalik did a blog post about like what he believes is the future and he was explaining that you know having a multi-layer one future is problematic exactly because of bridges because there becoming this weak point and if you manage to break the bridge you pretty much is able to wrecked the whole blockchain and this is actually something that happened with Phantom like a week ago um that's uh yeah like the mood Chain Bridge got exploited and yeah people went crazy about Phantom um so the question is can we utilize the same technology to improve Bridges and how we can actually do that so the way we do we do this is uh it's actually very simple so imagine that you have two blockchains and the state of this blockchain is vocalized so they they use these vircle trees to keep their data so now what you can do is you can take the state route of one of the blockchains and submit it to another only the state roof so that would be equivalent to taking like the the current Miracle hash or whatever as we said it's the same you put it on the other blockchain and now imagine you need you want to execute a transaction on one of the blockchains that needs some data from the other which is the standard bridging problem you need to know you know you're on arbit room and you want to know okay does this address own an ape on ethereum let's say and you need to run a smart contract that does something so if this address has an ape then I don't know I'm gonna airdrop him some coins let's see so you have the state route of ethereum on arbitrum and when you execute a smart contract what you're gonna do is you're gonna pass the data that you need to validate plus the proof the witness that we said like the same witness that you know can be used for the other thing and now the smart contract what it can do is okay given that this is the current route on ethereum right now this is the data I want to validate this is the witness validate the whole thing into the smart contract and if it passes the validation that I know in this moment I know yes indeed at this state route this data is present on ethereum so now I can continue executing and I can do like the airdrop or whatever I need so in this case you basically by only submitting the state route of ethereum on another blockchain you pretty much Bridge the whole state of ethereum so now every smart contract on this other blockchain can validate all the data on ethereum just by having a witness and when you think about it you in order to do that you you kind of don't need uh this additional security assumptions about like a network of validators or anything like this the only weak point in this whole story when you think about it is how do you make sure that when you update the latest state route it's actually correct because if you if you actually want to attack this system then you know I can just craft a state route in which I'm the owner of all the board Apes in the world and I submit it to the other blockchain and suddenly you know it's like another reality so in order to to to fix that in order to fix that um we we pretty much need to rely on on zero knowledge so if we are able to validate the consensus that this state route um is is correct using a ZK snark this is what we talked a bit earlier that if we're able to generate a snark that this list of transaction transactions indeed reach this new state then once we submit the the new root on this blockchain you can also submit the proof the ZK proof and the contract that accepts the route it can validate that well this route is actually correct now if um if we don't have this ZK thing then we indeed need to kind of rely on on this um validators network but you know you can you can argue that it's not like much better than what we have right now but the truth is that actually you can monitor what is being updated on the blockchain and it's kind of very easy to see if somebody submits an invalid route um so yeah I mean it's um it's kind of much easier to to monitor I would say but the moment when we managed to snarkify uh the consensus which is also something that's going to happen in the future we basically going to reach this ultimate decentralization where we don't rely on like any additional validators or anything uh we rely solely on cryptography in order to you know pass a state around different blockchains and validate the blocks so that's basically how uh you can use these Virgo trees to uh to improve the things here I I listed some resources which you can take a look at if if you're interested in so there are two projects that I know about that are working on this kind of a bridging thing using um such kind of witnesses one is for grunge and the other is Herodotus and it's very similar although like they have like slight difference in their approach but I would recommend to take a look into that especially if you have a problem where okay I I want to maybe deploy an app on on a layer two but this app somehow needs to rely eye on some State on ethereum so you know Bridges could also be expensive like you need to pay for these messages to go around so you can actually use uh uh you know the technology that these companies are providing uh to basically utilize this and you know it could be we know that all the nft trading happens on openc on ethereum but if we want to build like a game it needs to be on like Layer Two or layer 3 and whatever so that's going to be a bigger and bigger problem as as we go uh the other resources um this guy um I think Italian guy he actually uh wrote an Aragon version where the stage is completely vocalized so using vircle trees instead of Marco trees and he has even like a test net for it and you know you can actually take a look into it the other one which is like a PDF is pretty much the first implementation of and test of workout trees that was done by a research in MIT and this is if you look at the URL this is research from 2018. so we are talking about cryptography that is pretty much like five years old um you know it well that's not the cryptography it's like the data structure because the the Witnesses in the cryptography think it's probably older um so you can take a look into that it's it kind of uh it shows some statistics and stuff um and the other the other two are uh one EIP from uh vitalik that explains how the transition actually is going to happen because that's actually not trivial um like you need to transition from Marco to Virgo trees like migrating the whole two terabytes to another data structure it's going to be a a challenge and also there is a blog post on htm.org about Virgo trees you can also read that for more details so that's pretty much it like as an overview I'll be happy to take any questions if you if you have and I hope you took something from the stock hi hey actually what first come to mind is usually when you like work around cryptography it's sometimes tricky in terms of you might have all uh components of your cryptography and like a new data structure which is it's pretty much like B3 but instead of mean Max we use some polynomial as I can see so actually in general reduction um like tree size like this is just prolonging the problem but whatever it's like K could be really huge but what I'm really concerned because from the top of my mind I can't figure out why it's this has the same security level as Miracle tree because in Miracle tree you have each part on the line and you basically like again go to the root and check everything it's all you carry and you can sort of even cache Parts which you use frequently which would be to the right because it's like in history more new or maybe not it's just statistical but here it will involve well it's really hard to formulate my question because it just come to my right now uh but in general do you have any idea about research is is it more secure less or is the same um I would say it's maybe the same um the concern that people have is that both I believe um merko trees and this workout trees they're not Quantum resistant so the next level of security that we're gonna talk like in the future after all this is done will be how to actually make all the cryptography Quantum resistant uh I see this as a kind of a recurring topic that people are talking about but the thing is like there is these problems that we have right now that needs to be solved so it's much better to use this like cryptography to fix them although we know it's not Quantum resistant um and then start thinking about okay how we bulletproof our capitalist because Quantum resistance is actually a problem that's going to be so wide and so big that pretty much everyone will be trying to figure it out like it's not impacting only blockchain it's in its impacts like https like SSL and like all these other protocols um so I mean in that sense um it's pretty much the same security level uh you can measure the security level also in another uh way which is how many bits of security this given scheme has and I believe that with with this vocal trees the level of security that and it's the Virgo trees plus like the elliptic curve on which they they do like what is like the the field the computations are done um I think it's 128 bits of security basically this is the amount of uh the main concern if you use a polynomial instead of just plus minus we we should use in a miracle tree like I see simplifying so usually it's like when you measure something you can increase your mistake by using polynomials especially if you multiply and divide and seems like in polynomial as I saw from from it could be the case maybe not it's not clear but whatever it's just uh what what comes to mind so it's like maybe it's not a concern so we've already solved that I mean you mean that polynomial seems like um like kind of easy to manipulate in some way yeah so uh uh you you need to take a look at uh at the Moon mat basically but uh it's it's just amazing like it's um it's actually like they they do all these type of Tricks so I think um uh the the founder of starkware kind of tried to summarize it in uh in easier terms which was like in in the world of polynomials it's uh it's very hard to lie because if you lie and and we are talking about polynomials that are like big polynomials going through like a lot of points if you lie for one thing the whole thing just because you can imagine it is you kind of interpolate the like the the a polynomial that goes for a lot of points and then you need to like commit to a certain value so if you uh kind of try to lie in this setup the polynomial which is going to be completely different it's going to change like completely so it's it's just not possible to uh to lie even once uh in uh in this kind of scheme um so I mean if you look at the the at the math it totally makes sense so who is first okay okay uh just a quick understanding question right um so you said let's say I run my note on my phone right um the witness I'm getting only tells me like if the data I'm getting is correct right so yes I would if I want to verify the transaction I still have to pull the data from somewhere and like the only thing the witness gives me assuming I trust the witness um that I know okay this is data correct right so in the block you're gonna have both the data that you need and a witness that the data is correct so if you want to execute the transaction the transaction is going to use like Keys ABC you're going to have like ABC this is the values that these Keys have and then a witness for each one of them that they're correct okay okay but the block is bigger than 200 bytes right I would still have to pull a lot of data on my phone do the verification but I don't have to save it right yes so you well you're probably Gonna Save The Block like with the with the data although if you validated the book you probably don't need the data to be honest like once it's validated you can probably throw out the data and even the witness I guess because I don't see why you would need to keep this around you just need the uh the state route and that said um so yes indeed the Box are going to become bigger but when you compute like the size it's completely okay to to transfer this every 12 seconds okay so it's more like an um I'm not concerned about the witness is more concerned about the data I need to pull in my phone to do the verification right it's more kind of an storage versus uh bandwidth trade-off yeah yeah okay thanks hi uh thanks for the presentation uh I'm curious what is your thought on how far are we from Ultimate decentralization that you mentioned and do we need some more changes on the consensus layer to achieve that that's a good question um I would assume that we are pretty far uh unfortunately um I would say at least maybe a few years until we we reach that so um I I couldn't I I can't say like uh estimated ETA when we're gonna reach that and all this but um yeah I mean we can see that there is so much research around ZK EVMS and that kind of stuff so that's very promising but until we reach this like there are proof of Concepts out there like there is this blockchain called uh Mina I think that is completely snarkified so it's not something that we are kind of just inventing there are people playing with this concept um but um yeah I would assume that first we need to transition to workout trees then it's going to be certain time uh when you look at the EAP for the transition there will be certain time where we run with both the merko tree and the Virgo tree like they're going to be both present in the client and the data is going to be migrated slowly and then we need to figure out how to drop the Merkel tree like completely from the from the client node so that's going to be another kind of Fork I guess or something so once we reach that then I guess it's going to become like within reach to also snarkify the the consensus but it's it's nice that we have these projects that are kind of playing with with this idea like Ranch and uh it's uh it's it's great that um they they kind of playing with with this concept and um yeah maybe they they kind of push this initiative uh further so we'll see other questions thank you for the presentation so actually I think you mentioned Mina I think what they are trying to do is do the recursive snack and to and I mean shrink the the bitcoin's verification into several kilobytes or something and I think there are a lot of techniques to do how to make the whole Mercury or how to make the whole blockchain to be verifiable and much more smaller so why we call it stateless I mean a lot of blockchains they are trying to do the similar ideas with different techniques what is the difference from the stateless ethereums and others yeah um so there is certain uh security assumptions you know with with this um Mina that you know basically it's not so the nice thing about snarks uh is that you can recursively uh kind of merge them together so if you generate uh a proof a snack proof for a bunch of transactions then it's very easy to merge them together and get a snark for all of them and this is very easy to parallelize so that's that's amazing but um one of the security assumptions of of Mina and kind of uh could be problematic is this wonk range attacks uh which uh yeah I I won't kind of fall into details because I actually need to refresh my memory about it but um yeah it's um there are certain assumptions if you want to fully kind of snarkify the the consensus and don't have any transactions going on like it's kind of a hidden and all this so yeah like um unfortunately I'm not super deep into the middle blockchain so I can't kind of elaborate on this but uh yeah it's a it's an interesting thing to research so sorry I guess I can't help that much giving you concrete details but check long range attacks and weak subjectivity basically these are the two types of kind of things that could be problematic and I think we're kind of running out of time so yeah thank you very much I hope you're not asleep at this point so [Applause]