Chih-Cheng Liang | Introducing Sparse Merkle Tree

next up we have cece leon from ethereum foundation's uh privacy and scaling explorations uh it was previously called applied zkp team so yeah so cc will share the screen [Music] uh yeah thank you yeah actually for introduction uh let me share my okay you always see my screen oh sorry um hello can y'all see my screen um let me check wait sorry oh um yes okay okay all right um um today i'm going to talk about the sparse merkle tree uh since um kevin is organizing this dk day series of talk and as you can hear from changu's previous talk we will be talking a lot of oh moving this uh merkel trigger from here to there and then we need to uh do some miracle proofs and this microphone here uh prove to smart country that we have some um leave exists or some something like that and if you're not familiar with some merkle tree uh you you're it's easy to get lost uh in in this talk so uh today i'm time to mitigate this i'm going to save your day and feel free to ask any question you're too shy to ask and yeah people will help answering your question for you and okay so uh let's uh for example we we might talk about uh scaling applications like uh gk rob or an optimistic raw app and usually um this kind of blow up has muggle tree and with its leaf uh represents the pointer to the uh their uh public key or uh mostly uh the lead represent the user's balance and and you might see uh like tree has like 32 labels deep and and and we need to calculate the membership curve in uh either in the circuit or in the evm and let's uh give another example like privacy applications uh this is tornado cache and you can see that it has a history of unrules it's on smart contract and we have a 16 level uh deep mercury and it has some like different hash functions these are snap friendly patch functions and we compute this merkle tree in the circuit so yeah before we get into the mercury we have to talk about a hash function so the sort of hash function is a function that takes uh input it can be arbitrary size by the uh outputs always outputs a big size value uh for example if um you use the uh cut catch up 256 uh this is the hash function used in evm and it always outputs 32 bytes and the output is very sensitive to the input a little change in your input the output looks completely different so for example we can see this python snippet you can import the etch auto cad check and then and then hash the input abc and you get this output uh of hex that you do by h but uh when i add a a character d here and then it this output looks completely different um and let me give you another demo this is the online online tool to compute the cad chat 256 hash uh this is uh developed by uh xan i think it's uh in it's a taiwanese developer and as you can see whenever i i add another input into um when i change the input a little bit the output looks completely different and uh so this uh this hash function has a very important property that is computationally invisible to find a collision uh what do we mean by the collision is if you cannot find like two different inputs and then that can derive the same output so if i uh have a contract ibc that outputs uh this 0x 403 i cannot uh it's uh it's so difficult like like it's uh if i have a huge amount of computation resources i could not find another inputs that can derive the exactly same output uh for this hash function so um keep this collision free property in mind because that will help you reason about the the merkle tree so um another prerequisite i want to talk about is the core structure of evm we will introduce this merkle tree and use the scaling scaling application as the the motivation of why we are building this merkle tree and and uh and yeah and and so so i like to uh imagine ebn or ethereum as the restaurant menu and the evn like uh you can perform computation in the evn and your solid data code solidity code is compiled into some different up calls and each alcohol is has some guest um guest cost so it's like um it's computation computation price is uh is priced depending on how expensive this computation is so uh one of thing you can do is you can store data chen and this this data will be like synced by all the phone nodes and the phonos will have to keep it forever and this is uh you can achieve this as a store of code and it takes uh 20 000 guests to to store a world of of data a word in the event is 32 bytes and another um another way you can uh send the data on chant is uh you attach the data in a tx which we call this code data because this in your transaction you can when you send a transaction and to a contract address and this code data will determine which function in this country you call and what argument you are calling this function and so this code data is defined by per byte gas uh it's uh 16 gas by here uh to compare with the sa store i i write the uh per word gas so uh to write the um attach thirty bytes in the tx um you need a 500 gas and last one is uh performed kca hash so um one hash takes 30 guests but since you can um take arbitrary inputs in this hash but uh per word uh per uh every 32 bytes of input takes six extra uh gas and so um the major difference between the uh as store and the code data is that um the data as stored you can access any time with uh from from a contract so you can uh read that data like if store like uh f-o-o equals uh uh one two three then uh like ten days later you can use the you can still use the contract to uh use s load and and get the value of one two three but uh for the data in the code data it's not as accessible uh to the contract you cannot uh uh it's not a variable in a contract but uh if you have a client uh or or um you have a phone note and that syncs the things that uh ethereum blockchain you can get that piece of data and that's how uh the coordinator works they uh or or a what watcher of the road system you can like sync the four node and get those piece of data and we can risk con reconstruct some data um by that trick so uh the tech way here is like uh storing data on chain is super expensive attached data in the code data is much cheaper and calculating uh hash function is also cheaper so that's why we don't want to store much data on chen and we prefer to like um sometimes we need to calculate when we really need those piece of data so yep so here we can talk about the smart sparse merkle tree so this uh sparse markov tree that you commit a big size of vector like uh you can have a 10 level 3 and commit uh like 1024 items so you imagine uh if you write python you can have a list but it's fixed size it's only it has only uh 1024 items you cannot add more um and so end level trees can store uh tutor power and leaves so what does this mean this means scalability you have one extra a little level you have double the vector size you can commit and uh uh the the sparse microphone is different from the traditional youth uh mercury is that you can save the uh this cost using the default hashes uh we will talk uh talk about that later and the last feature my membership curve is also a feature of sparse merkle tree okay now here we can draw this little happy tree here and uh here we can imagine we have a vector uh that has like a first three item is a string a b and c and uh the we we have nothing um in the last by item of the uh of the of the vector and then we hear uh h is the hash function and we derive the hash hash of a and we we call this uh this output this digest is uh d0 uh then uh so the first uh digit is the label so uh we we call this uh level zero uh sorry let me get a yeah we call this level zero and level one and level two and level three and the second digit is the index so we start uh we count the items uh from zero zero one two three four five all the way to the seven and second level is zero one two three and third level is zero and one and lastly is zero and uh as as you can see in the the computer science um the tree is growing upside down the root uh the tree root is at the top and the tree leaves is at the bottom um okay and oh yeah and here the second level of hash is the hash of the left child and the right child and so this is how the microchip constructed and all the way to the top so you can imagine that if like some of this uh leaf is changed for example i want to change this to hash of b then the d02 is changed d11 will be changed and d20 is changed and these video that rules will be changed too so this road is so sensitive to all the inputs here okay so uh so we can like um we can think this merkle root as a representation of this vector uh the current status of the vector and we can store this miracle rules or um or the commitment uh all the hash of this merkle root ang chen so um in the row up this usually is the stay room which means it represent the status of our balances and these three nodes these are all 32 bytes and also these leaves and also the data like a and b and c these state these data are stored off chain when we say off channel means something like a centralized coordinator or operator and they might have a good hard disk and they can store all this data and we don't need to store all this data on the uh means uh layer one and means all the four nodes all the poorer four nodes they have to uh they don't have to store this a large amount of data they just store uh this tiny 32 bytes and it can measure that this uh these balances are with uh are like um haven't been tempered and uh and okay so let's focus on the uh operator slide um notes that um uh this uh so this uh uh this this uh notation is the null uh it it could be uh something like uh as arbitrary string you defined but um we can see that at d03 to d07 these are all same uh same hashes so you don't have to store any disk you can pre-compute them in the memory and then this d d one two and d one three are also the same so here we actually uh this uh three levels of uh merkle tree uh actually we we only need to store three hashes in the memories and these are very easy to come to calculate like with a simple um python called you define your uh the default hashes this button and then you just append the uh previous item and hash together to get a new next levels hash and then you get all the default hashes so actually the the data you need to store is just abc and hashes above um okay so now um now there's the membership proof uh how do if uh let's say i want to prove that uh your your uh your chain that uh a smart contract in uh it stores d uh three zero and you have this micro root and how uh and you can prove to that smart country that um see this hash c is a member of um of the tree uh smart country does not have the data of the leaves but once you provide this d10 d03 and d21 you can compute this hash you hatch the c d 0 2 and 0 3 together to get the one one you hatch the d1 0 to get and hatch the d11 together to get b to zero and hatch the d20 and the d2 one to get at these three zero and you can compute uh if the hash of these three things together match to the d3 or the store down chain and then if that matches that means c must be the member of this tree because you cannot find other inputs that [Music] go through all these hash functions and still get the same output of the d30 that's the non-collision property guarantees so and now membership proof you can also prove that some of the uh spots in this vector is vacant like d04 you can provide this uh uh of of the path uh these notes and then you hatch together and uh to check if it must match the uh merkle root and if it matches uh it means the uh they you just prove that uh empty uh this uh empty empty hash is the member of the tree then you approve the my membership so yeah and and we we kind of like magically get the um get the those uh nodes of the outer path but how do we actually find it like uh like algorithmic remix so before we find that uh other path let's uh focus on how do we walk from the merkle roots to to that leaf so for american route you walk right and then you walk left then you walk right to this particular leaf and you can do so this is uh index five you can do a binary uh uh decomposition so um if you don't know what's the binary decomposition you can do like um divide it by two and get the uh reminder and then you get one zero one and if you get a one you go right if you get a zero you go left and you go you know one you go right and then together all the path um actually the other path is just the sibling notes that's uh that's that's next to the the leaves so uh if you need to compute this hash you need a sibling of the d05 if you need a hash of d21 you need a sibling of d12 so you need d13 so whenever you you go right before you now go left and you go left before you go right so you can get this this node um together yeah okay uh let me check the question um how do i check the questions right uh why is membership that important if it's not different uh from the value of membership um good question because uh yeah let me answer this quickly because it's not possible in the traditional merkle tree because traditional marketing you need to grow the tree it's not fake size you can like grow infinity forever but you you don't have the spots that uh live there but in in in the uh spa smart country um we have already uh we are we already have uh like we have already like uh 1024 uh items already like uh uh sitting there and and and so so we can compute num the membership and another point is that um why not my membership is very useful when you need to perform like if i want to deposit from l1 to l2 and i need to find an empty spot in this tree to move the l1 asset to the l2 tree so you need to know that that particular [Music] items that let's say i want to move two balances to the tree and i want to move to empty spaces so i am not overriding other people's uh balances and yeah so so so yeah this uh the the membership is used for in the in a uh l1 moving trail to case yeah uh so lastly i want to talk about updating the an item of the vector so for example i want to update this c to d so this is changed and you'll notice that this is changed and this has changed this is changed and we also need those audit paths to compute the changed value yeah so yeah and here we show the library of mercury so this we can compute the mercury roots in a solidity code so we have this compute root function it takes the leaf input yeah which is the the hash of the item and a path uh this is actually the index so that like um for example uh this index five index five and this is the hash of the uh index five and and these are all the witness notes then we uh we look for awareness length and we we try to get the i-speed uh from the right so this we shift uh like let's say i is two we shift to uh shift two bits and check if it's zero uh if that bit is zero and then it determines we have to hash the current computed hash with the witness uh which which part is led and which price right and then we we have the computed hash computed three roots here in the output and then when we verify we could take an input that's the roots stored on chen and then we come we compared with the computed route then this is how we check the membership in the uh in a smart country so if you are implementing an optimistic roll up and you need to check the balance of certain leave and that's how you verify it in the country so yeah the tech way here is that yeah um so the splash mercury is a very simple uh commitment scheme uh that they just store a small amount of data on chen and it buys the large amount data of chen and uh yeah sponsored um and it pers uh the sparse market improves the membership and non-membership and it has a face is it's big sized and it has default hashes and yeah we talked about other thing the tree and application is scaling is that we can move the cost of uh storing like uh for billions of accounts and we moved that cost to as a centralized operator and we got a protection uh from the layer one with that micro route and application in the privacy is that we could have the merkle rules on chain and then when like in the tornado cache you want to withdraw and you prove that you are a membership you are a member in that leaves because when you deposit in the tornado cash you get a membership in that leave but that you cannot reveal that membership when you withdraw because the people will know who uh who's the depositor and and uh toronto cash uh used uh uh zk snark uh to prove that membership in inside a smart circuit so it use the mercury to keep your privacy uh so that's it uh i'm from the privacy and scaling exploration we are looking for contributors if you are looking for building cool projects with barry whiteheads and and lots of amazing people like uh like kevin and javon and many people are here and uh reach out to me the floor or yeah email and telegram here thank you so much okay uh any questions for cc very quickly everyone maybe thomas mccarrah oscar alex robin harris i'm just calling out all the like people who asked me why we had like a mandarin talk and now we have english talks so any questions for cc yeah um so before i invite our next speaker just wanted to tell everyone like i've prepared this gather town space uh it's it's it's sort of this virtual space where you can hang out and meet people so i have the link ready uh so i'm gonna i'm just gonna drop it right before we head over to the character which is like at the end of the talk um so next up is stephen winston hello hello hello um my um yes yeah go ahead oh okay i i just type in uh do you want to ask like do you want to ask the question to cece or you want to ask uh i just want to ask cece about the topic uh just talked before about about sparse marketing yeah because i just work on some project with my professor that have to store more data uh try try to store a lot of data on the ethereum but the transaction fee will be the biggest problem so i just think of that uh if i use sparse 1.32 for a store more data how to store those of chain data carefully will become another issue you have to solve or [Music] or something that's easy what's your thoughts on that uh yeah uh did you finish your question or yeah it's the question right here yeah yeah yeah yeah yeah i finished my question thank you so so yeah so right also um so right uh i can imagine that um usually you you use a key value database and store you you use the uh like index as the depth and index as the key and the hash as the value uh there are different kinds of way you can sort this data you can store the parents and parents as a key and snap right children as the value and you have to be careful for the chain re-arc because each one can reorg sometimes so you might need to like wait wait for like more confirmations to prevent a tree reorg and so yeah it's also and and also yeah you need to make sure the uh like your tx uh is uh the the data to reconstruct the merkle tree is available in uh in your protocol design and then uh other than that it should be like uh storing the the miracle tree of chain in the database should not be the big it um it does have some engineering challenges but i could uh talk to you with that uh privately more okay cool yeah um thanks sanji