Ethereum Under the Hood: Algorithms And Data Structures - 0xPoland S01E02

okay wonderful so fiore is gone for a moment but he's gonna be back after the presentation if you still have any questions uh and i would like to remind you there's gonna be a networking virtual beer session at the end so if any questions pop up we're going to answer them at the end of the presentation or during the networking event and now to ethereum data structures and algorithms so we're going to start with marco patricia tree make mercury patricia tree is a fairly complex somewhat complex uh data structure that is used everywhere need to well how does it work first let explain how the patricia trees or you might know already this data structure with a little bit different name called radix tree so the radix tree is uh is a tree in memory uh the tree has there is a root there are children it's there is it's not necessarily a binary tree it could be uh it could be very different kind of trees but the core idea is that we traverse from root all the way down to the leaf and every node in the tree has a value and each path from root to to the leaf represents a value that is an aggregate of values in the different in the different nodes so usually radix trees are constructed on some kind of alphabet could be like just normal alphabet so if i traver traverse from the top from the root t r i e then we say well the value at the leaf on the left side represents the value three and we could traverse all the different paths to get all the different values like tree trun toe and token so a pretty straightforward concept a lot of you might have heard about it before although it's not that popular data structure so many of you might have not heard about it yet now we're going to move to another data structure that is also a tree but completely different tree it's called miracle tree a miracle tree is a tree of hashes so again it's not necessarily a binary tree it could be very it could be very different forms of trees but as every tree we have a root we have children nodes and we can traverse from the root to the leaf or other way around so this way it's more interesting to traverse other way around so let's start traversing from the leaf we have uh in the leaf we have a value so let's make it three again and um we also the tree the the value in the leaf is also hushed so we store the hash of the tree uh and then and then as we traverse again from the leaf to the root we hush the value uh of uh we have the hash of previous child right so we have the value from the from from our children and in case we are know that have multiple children then we concatenate the values from those nodes and that produce the new value so except for the leaves the values in the nodes are not really readable just just hashes that don't really means a lot at the first site and um yeah so that's basically how it works here is an example we put the same tree but this time we put hashes as hexadecimal values and as you will see in a moment ethereum laws hexadecimal values so this tree has a very interesting property if you change anything i will go back a little bit if you change anything in any in any leaf that will change the value of in all the nodes as you traverse them from the leaf to the root so that obviously implies that if you change any value in the in any leaf that will change the value in the root so if we transform the tree a little bit and make it a little bit more orthogonal uh you can you can you can look at this this this particular picture and imagine what the miracle proof is america proof is a proof that a certain value belongs to a certain tree so we can imagine a huge tree of billions or trillions or even many more values and uh it's a miracle tree that we construct but we don't need to have access to the whole tree to prove that a certain value belongs to the the tree so in this particular in this particular particle case imagine there is a tree there is a harsh value over here in the root that is known to us and there is a value in the leaf let's call it tree for now and i can prove that the tree belongs to the root just by providing siblings siblings so looking at this picture if i would like to prove that 3 belongs to the root i would need to provide this value this value and this value i think you see my cursor so you should be able to see what i'm talking about so just by providing those three values i can calculate this hash this hash and this hash and calculate the root hash base mid so we can create a method it could be in solidity any other language really as well let's call it verify proofs verify proof it has three arguments it has a root that is well known to us it has a leaf that we want to verify it belongs to the root and we have uh just an ri of bytes um okay that sounds like a weird beta structure why would i occur well i'll give you an example a couple weeks ago and i think you might have heard of it i think it was last fall um uni swap make an airdrop and the idea was that anyone who ever used uni swap at least once would get some tokens down some uni swap tokens and it get especially very important event because actually the tokens that would give away even for those users who are very basic and who like literally used uni swap just once it was way over one thousand dollars i think it was one thousand four hundred dollars or something like that so significant amount of money now a lot of many millions of people have used well many millions of addresses has used uh uh uni swap i believe or or a similar or quite a big amount so if i would like to make an airdrop and make a near c20 talking like pia described just on the previous presentation and i would like to send any everyone a transaction that could be a huge amount of money that goes into those transactions and that would include addresses that maybe are not even active anymore and like don't even occur uh so what uni swap did is they build a miracle tree so they make a long list of all the addresses that they interacted with uni swap at any point of time and they build a very simple smart contract and i have some pieces of that smart contract over here and you can see that it has just two it's a miracle distributor uh and and basically it has just two variables just two member uh variables here uh it has a miracle true root uh it also has a token but well in this case it's um just uni union swap token so it doesn't matter that much but they have a merkle true america route and they have just a clever mapping that basically is a bitmap that stores information and someone claimed uh their tokens so they construct the merkle uh distributor it's pretty trivial just setting the values and here is a magical claim function all you have to do is provide an index which is a calculated value that doesn't really matter it's just a trick to save a little bit of computational power you provide the address of the account so the account that interacted and want to benefit from uh and want to benefit from airdrop and the amount of money they believe was attributed to this account by uni swap and there is just an array of hushes that is america proof and first thing we do is we check if the account the account already claimed the value if no if it did then obviously we revert but if we don't we basically verify the market microproof and if it's fine then we're gonna transfer the money uh transfer the money to the account and that's pretty much it there is also a seller that makes make sure you cannot that just checks that okay these others already have uh claimed their uh money and and that's pretty much it we have a verification verification basically calculates the hash from account and amount and verify that across miracle proof across all the data hashes so as as you see this what might seem as exotic data structure is actually being used in blockchain space but that's just the beginning so now we spoke about two kinds of tricks right we spoke about radix stream the one that you can traverse to get a value and a miracle tree that is the one that basically store harshest so now let's try to connect them together and see what happens we can create miracle patricia tree let's make it simple for now let's make it assat so miracle patricia tree in ethereum space has um is indexed by uh fixed uh sized bytes uh values let's say a machine world words so and we to make it easy to to write we just display that as hex at the decimal values so in this case we have a miracle patricia tree that we can traverse from the root to the bottom and uh each note is a one nimble and one nibble is a value from zero to uh well zero one two three four nine a b c d e f there is also a v which is value which we ain't gonna use for now and when we traverse the tree we can we can collect those numbers and every leaf represents a certain machine word center certain fixed byte length value that we represent at hexadecimal so that's a set but let's make it better let's make it a dictionary let's make it a map let's make it something that has keva let's make it a key value store so in this case as we traverse from the top to the bottom we collect the key and the key points out to a specific value in the uh in the leaf and uh when we the value at the bottom of the tree and um it's also important that at each each node is hushed so if we change if we change one if we change one value in uh in the leaf we're gonna need to change values uh all the way up to the to the root including the roots itself [Music] so uh miracle patricia tree and if you look at the tree if you look at the tree and imagine there is a set of values then the values are probably the set of values probably much smaller than the space of possible values so let's say it's uh 64-bit um byte strings so like let's say 8 bytes that we used to index that would be 2 to the power of 64 possible values that would be more that any memory on any computer can store so on any reasonable computer can store so um therefore it would mean there is a lot of nodes that basically have just one child like it would be not very dense tree so what ethereum does it does it creates kind of a compression so we have different note types you have a note type that basically represents a branch so there is more than one value it has more than one value uh it has more than one child one value but more than one child we have an extension that has just one value but also it might represent multiple levels and we have a leaf that represents uh well note at the end of the at the bottom of the tree are you ready boom here is an example so if you look look at the right top corners we are in this example we basically have a map or a dictionary a key value star that we index with three bytes keys so six nimbles six hexadecimal charts and each has a value that is well in this case let's say integer this represents the account bonds and if we look at the top of the tree we have a root extension node well root root mean just a root node and extension node is a kind of node that goes through the multiple multiple nimbles right so we have a7 and if you look at the note at the top there is just one node and it represents a7 prefix and if you see at the values at the right top corner you see that every single value in that particular instance of key value store starts with a7 but then if you look at the first third position you see that there are differences in diff for different key value pairs so there is one seven f and seven and therefore as a child of root extent of the extension node we have a branch node that will lead into three different directions so if we decide to go for one you see there is only one key that has that starts with a seven one so we end up with the leaf node that represent the rest of the path one three five five one three five five and similarly it goes for f if we go for a seven f you see that there is only one value so there is a leaf node that represents nine seven six five nine seven six five so as you traverse from the root to the leaf you collect those different nimbles you can build keys that stores the values and the last to the last most complicated path goes through extension node 8 7 a7 7 again you can see there are two options now so but both options are going in are following with the same nimbles d3d3 d3 d3 and then there is a branch node again on position five because there is a difference uh on position five there is three and nine that are represented respectively about those um uh no what i wanted to do that are uh represented by those leaf nodes over here every leaf node has a value as expected i hope you understand it if you don't let me know we will we'll discuss it some more at the end so this is merkel patricia tree a very clever tree that has um that we can easily that we can store key values uh key are any bytes strings but it needs to be a fixed size so a certain size for a particular miracle patricia tree and now let's talk about uh storing history so imagine you have so this is something that call that is called version data structure so imagine you have a tree and you would like to add a new item to the tree the problem with uh if you add a new item to the tree you're gonna modify the tree and you forever you're gonna forget about how the tree should be represented how is uh what was the old version of the tree what was the the old set that was represented wouldn't it be great to build a such a data structure that you can have every single every single version of data available for you to traverse in to the to the past or to the future so you can do that with uh with versioned trees and in particular you can do it with miracle patricia tree so imagine you have this token instead of connecting them to this node or this node and trying to modify the tree we can build completely new path that is represent that represents the path from the uh well from the from the leaf to the root or other way around and but that's gonna create only only that many nodes as high as the tree is right so if the the three have three levels that's only gonna create three nodes but what happens is we create a new route so now we have a one data structure that is a list of roots and every root represents a different tree but the tree trees are interconnected and we can do it and we can do it quite a lot so we can create all the versions every time we insert or delete an element we can just create a new path so this is pretty efficient uh in terms of uh memory because if you would like to do it let's say on our eyes then you will need to create a new ri every single time you want to start a new version so why why why are we talking about all those complex data structures well it turns out that ethereum stores pretty much everything in merkel patricia tree there is a state tree that stores all the information about all the variables and all the different and all the different smart contracts there's a transaction tree that stores all the information about transactions and there is a receipt tree that stores all the information about all the executions of every single transaction so i hope you're ready boom and here goes the next one it might seem a little bit complex when we finish with that slide i think it's going to be pretty straightforward and you're going to understand how the whole blockchain how the whole ethereum blockchain is structured so at the top we have two blocks so every every time every time a new block is mined a new block header is created a new block header has an information about hash of the previous block so in blockchain space you can think about hush as a pointer pointer so if you have a hash to a certain block or you have a hash to a certain um transaction that's basically a pointer that allows you to look into market patricia tree and get this transaction so we have a block number n and we have a following block number and plus one uh n plus one points with his hash to previous block number one number m and we're gonna look at some of those fields we're gonna look at the times time sometimes time is basically a time sum that miner is giving to a blog at the time of mining there are some rules about panzer he cannot do a random time timestamp the timestamp cannot be older than uh like 15 minutes from triges block and you know this kind of stuff it cannot be before the last block and so on that just to make sure that uh miners don't do too much of time manipulation although there is a little bit of space for their manipulation obviously there is uncle hash which is an ankle blocks which we're gonna talk about what are the ankle blocks we're gonna talk about in the future but you know the bitcoin uh has the notion of parent blog or previous blog uh in um ethereum we also have a notion of ankle block we have beneficiary also a different name for this field is coinbase so it's uh which might resemble something in your mind different than than the field also related to blockchain cryptocurrencies so beneficiary or coinbase is address of the miner who are gonna benefit from mining the transaction uh there are a couple of other things worth mentioning difficulty is the difficulty of that block so you know at any point of time there is a global competition among uh miners ethereum miners and the same goals for bitcoin and many other blockchains who gonna be the one the next one to win uh win the competition is going to get rewarded and be the creator for the next block so difficulty is just a number of zeros in in the hash that needs to be calculated and basically minor just calculating the hashes with the difference with the different uh nouns and when they do you have enough zeros in front of uh that corresponds to the difficulty they are considered to be the winners for that particular um for that particular blog we ain't gonna talk about consensus algorithms what happens if there is a if there is a tie and so on so forth we there is much more that can be said about it but not yet so there is a black number gas limit for a whole blog gas used by all the transactions on this block uh and and a bunch of other things but i want to get your attention to show you the last row of fields there is a state route transaction route and receipt route which are all routes all the different um miracle patricia trees that are that store state of the whole blockchain uh list of all the transaction and these of all the uh received and you know you can think about those as a small database or key value store once more good so um uh yeah so let's talk about state route state route is the route is the information about the state of the it starts a route for the american tree that represents the whole state of ethiopia so that includes all the addresses so the state route is indexed by address on ethereum hexadecimal the kind of that many of you might be very familiar with by now and um what is the value what is the value in the tree well the value of the three are four different values it's a it's a um it's a aggregate of four values so there is a balance a second one that basically says how much money is on the account so that's pretty straightforward everybody can relate to that one there is announce that is basically a number of transactions that were issued there were issued from this that were mined on this particular account so far that only uh that only is important information if the account is normal wallet if it's not a smart contract if it is a smart contract announce is not very important but what becomes important is called hash and stage and storage route well the code hash is simply a hash of uh of the smart contract of the bytecode of the smart controller that was deployed now the code hash is a hash and a hash on blockchain as we know is basically a pointer because there is yet another uh yet another uh merkel patricia tree that stores all the codes all the different bytecodes which means that every single byte code is duplicated and if i deploy two smart contracts or i deploy one and someone else deploys the other and they have the same buy code it is only stored once and here we have a storage route a storage route is a is a route of american tree again and it's a tree that stores all the information all the variables that are used by the smart contracts that are carried across the transactions that are not just temporary variables and what you can see is those weird lines pointing from one from state tree of one of one uh block to a strategy of the second one which is exactly the reason for that is what i was explaining just a moment ago which is the miracle patricia tree are version which means we can fairly easy traverse in the past and get the value of any specific field or any specific uh balance or really anything that is in the site we can easily query blockchain node to get the bug so i hope that's a little bit more uh understandable now um now we're gonna talk about the what are the implications for etude nodes so there was a there was an event i think it was maybe two or three years ago when someone said it the ethereum node is growing really fast and it already takes one terabyte of data and you know like ethereum is really poor in terms of scalability and that was a little bit of misinformation because it was true that if you want to sort a whole history if you want to have a full node that stores all the history of ethereum it takes one terabyte but if you think about it but but then if you want to store only the latest state it might be a little bit different now but i think at the time it was maybe 200 gigabytes to store the full state of ethereum as it is today and it was at the day i think it might be more like 300 400 today but you know it was much so to start a whole history it was only five times more it was not like thousands of times more as one would expect if you make a copy of everything uh or everything as many times as many blogs there are there are millions of blogs already being ma that was mine on interior so that would be quite a lot so actually that was a demonstration on how efficient uh how efficiently data is stored on e2 but that also made people aware that you can run very different types of full nodes so what is a full node a full node is a kind of node that uh downloaded the whole history of ethereum and verify every single transaction to make sure there is no single block that represents uh like a malicious transaction like a fake transaction like a double spade link like i spend the money that i don't have or i spend the money i have twice uh and and with ethereum you can do it in many ways very efficiently so you can for example download the first block and the second blog and the third blog and keep verifying that and i think at this time point of time it already takes a couple weeks to actually forward like download the whole history and forward verify it and um but then you have very secure node because you traverse the whole history and you know that you know not a single transaction is a fake transaction but you can also because it takes a couple weeks you can start with the loaning the current state and verify it backwards so initially when the when the node starts it's not yet fully verified but it's able to operate and only after week two or three when the whole history is downloaded but now in the reverse order you can see uh the full the node is fully verified and you know that and you know that uh there are no transactions that break the rules but here's the thing you don't really need to do that you don't really need to do that you don't really need to have fully verified know with all the history uh to be to feel very safe all you need is a prune node so if we go a little bit back to to the previous slide you can see that you only need to download uh hashes of the you only need to download headers of the blogs to see that there is a to have all the information right so you have all the transactions you can verify with miracle truths if they are there and there is a difficulty and there is a and there is a hush and of the block and there is a uh hush that was developed by miner that was one by miner that proved how difficult it was how many uh how many computational power was required so if someone would like to just rewrite just rewrite the block headers not the state of the blockchain but just the just the malicious history of block headers he would need to have a computational power bigger than the accumulated power of of computations that was done throughout the history of the whole blockchain ethereum blockchain so that's very highly unlikely so you don't really need a full load uh to to feel very secure you you it's enough to use a prune node and you can even you can even just have like a very very limited view on the blockchain you don't even need to have like to store the current state you only need to the current like download all the headers and then verify the proof proves against state that is provided by some other chain because you know by some other node because you know it's impossible to um you know to cheat thanks to america proofs thanks to merkel trees that stores the information so that's that's very amazing that's very super it was very surprising for me to learn about the data structure and how powerful they are and but you know everything as everything in life you know there are two sides to every coin uh so the american trees are pretty intense computationally because as you update you need to calculate multiple hashes and i told you before that it takes i think too many for three weeks might be a little bit faster now because i know there was a lot of work on optimizing that uh it takes it's take a while to kind of to kind of download the history and walk through it and the reason are and that's pretty pretty funny because a lot of those other blockchains are saying we have faster consensus we have faster deals and faster debt but but really the the the biggest boldness and scalability of ethereum today are merkle patricia trees so it's like just right to those database and every ride is just an update in those three it basically takes weeks it's not the bandwidth it's not the speed of consensus algorithm is the challenge it is database and now we have we have we have some ideas how to make more efficient how to build a struct data structure with similar properties that are more efficient but that's probably gonna happen in the future uh i wanna tell you because we're already talking about block and we're already talking about all the different things so here's a in solidity you can use a variable called block and it has a bunch of different fields and you can access all some of the fields that i was showing you before so we can access coinbase or it was called beneficiary difficulty gas limit for a whole blog the number of the blog you can ask for the timestamp and you can ask for a blog hush but you cannot ask for the for all the blog hushes you can only ask for bloghash of previous blog or any of 256 most recent blogs uh you cannot ask for hash of older blogs because if you would not like to assume that the whole history it needs to be stored by the node and you cannot ask about uh the hash of the current block and it's your homework to figure out why if you do let us know in the comments if you don't we we can answer that on uh networking event now the ghost protocol one more interesting thing about blockchain that is um that we already kind of hinted here was that of the ethereum blockchain is that it has this notion of ankles why do we have anchors well if you look at the bitcoin the block structure is pretty straightforward every every block has a parent and if there is a um a tie and there are two miners that um mind block and similar time uh then then the winner is the one uh who has uh who will have the the the information about who the winner is needs to wait for the next block to be mined and the next block decides if they connect to the one block or the other and if that happens we know who the winner is and as you know the average time between the blocks on blog in bitcoin is 10 minutes so if you buy a house or if you buy a car something of significant value and you want to do a transaction from bitcoin for that which is what some people do and i expect now that we have a bubble it's going to be only more of those kind of transactions then the recommendation is you wait six blocks so on average you wait one hour for six blocks to be mined because there might be a reorganization a reorg and the rework is basically when you know when bitcoin old things this is the kind state but then the other block is being mined in top of the other block and then it needs to switch to another branch so uh that is you know that kills his ability like waiting one hour for transaction to go through is something we're not used to at any kind of transaction systems so ethereum is innovating on top of that so they creating instead of using this idea of longest chain like the chain that is has the most uh the most uh is the longest so have you know the parent to the parent repair and so on um it used the idea of the heaviest chain so it connects not only not only the parents and children in the line but also kind of connects creates a tree of blockchain or blocks via ankles so let's say let's look let's do an example so let's say there is a block a0 that was mined and let's say every everybody in the world agree that is the that is the first block right and then there is a a one block being mined that is uh the sender the next block to a0 right and in parallel there is a b1 being uh mind and then kind of in similar time you can't really tell who's first and distributed network so so the question is which which is the right way to go through a1 or through b1 so what a2 is doing is saying i'm i'm i'm mining on top of a1 i'm adding to ethereum state you know that was developed by a1 and but b2 says you know what i see that there is i'm building it off of b1 but i also see another block which is c1 that someone else uh mind perhaps a little bit later than b1 and i'm gonna say okay i'm a child of b1 but i also have a uncle c1 and what ethereum does it says okay this is the heaviest this is this is the biggest family the b this chunk represents the biggest mining power the the greatest mining power behind it because there is you know uh the same block the same block number being um mined twice so um in that sense it's strongly incentivized strongly incentivized miners to include as many uncles as possible because if they don't someone else will and will take over the reward now the miner of the blog that goes into main chain gets a reward but uncle also gets a reward so ankle gets i think it's 0.7 of what of the what b2 and b1 is getting so that's still pretty a lot of money so if i'm an uncle i don't wanna i don't wanna build another one so let's say if i'm a one and i see there is another chain and i'm already included as an ankle it's fine i'm not trying to build another block and top my old blog and just making sure that you know just increasing my probability that the money is going to be there it's fine i already get my reward i can mine in top of b too so in that way there is a reduced incentive to do like uh um kind of pull mining when people try to compete against each other with different with different kind of uh uh paths in the block tree they just go for uh you know connecting to the heaviest connecting to the heaviest uh that's fine i'm gonna be included in as an ankle if i if i play nice wonderful um yeah so that was a bunch of algorithms and data structures and i wonder if you have any questions uh should we maybe go back to the studio make sure if you don't follow us yet make sure you follow us on twitter if works is where we work with kyoto and if marek is my personal account and now uh hoping to back hoping to hear some questions and i'm hoping to go back to the studio mateos can you bring us back to the studio yeah i think we're here okay [Music] yeah a great question a great question uh so that's another presentation we're gonna if you wanna know more about be able to answer those kind of questions and then come to one of our workshops or on the future presentation but i'm happy to answer this particular one so there is a new numerical error plane set claimed is here right and the question is shouldn't it be after uh sent tokens right uh so here's the thing how to give you more general explanation um here is how transactions work uh on and smart contracts work on ethereum blockchain every transaction is atomic so either the whole transactions go through or it's reversed so there are only two possible outcomes success or revert if transaction reverts there's no change to the state of the blockchain whatsoever means like the transaction was never called there is only an information that there is only in receipt there is an information that transaction failed and how much gas it was used and uh some amount of money subtracted some of the meters uh subtracted from from the balance of the issuer for the transaction but other than that there is no change to any variables in the smart contracts or balances other than the center which means that the order doesn't really matter in most cases there is also something we're going to talk in the future which is re-entry attack but we're not talking about it today um so so it really doesn't matter so if we set it here either the next other transaction will be successful and the whole and the whole transaction will succeed or it will fail and it doesn't matter if it fails this line or in that line the set claim will not be set at all yeah i wonder if we have questions yeah can i can i add something there i think potentially if the token is any token then you could have reentrancy in this case so it's best to first set the variable and then transfer yeah let's not let's not talk about it yet it's there's gonna be a presentation on security and we're gonna go i think it's gonna i don't wanna i don't wanna brag because i'm gonna be doing this presentation but it might be one of the most interesting presentations so far because we're gonna show how people lose or some other people gain tens of millions of dollars and in almost every single case it was a single transaction that led into loss or gain uh there was you know like 40 million dollars one hug 120 million there was 300 000 just yet last year so we thought like you know like and this presentation you know it's get only longer every year so it's like there are new hacks every year and i think there are so many that we only hear about you know some of them like if they're really big or they're really innovative in a way they do that