Breaking the I/O Bottleneck for Blockchains with Small Authentication Large Trie

Transcript

All right. Um, yeah, thanks for the for the  introduction. It's very nice to be uh to be back at MIT to talk about some uh researchy stuff we uh  just uh uh produced at Mega ETH. Um, by the way, Mega ETH is a um super fast Ethereum rollup  uh layer 2. Um, so the the core like feature is what we call real-timeness. ically um we want  to mimic the the level of VA 2 performance like um sub millisecond transaction latency and up  to 10,000 transactions per second in terms of throughput. Um but this talk I think is kind of  standalone. It's not really just about mega. It's a primitive that would be very useful for for  whatever um blockchain that still hopes to get some what we call state commitments. ically um  Merkel try roots um state roots in Ethereum or

this um Merkel commitment of all the unspent uh  UTXOs in Bitcoin. to this kind of stuff. Um yeah, so it's a it's a very long title. Um I'll just  shorten it to small authentication large try. This is what this is the name of the data of the data  structure that we developed and it's also kind of the the sense of the protocol of the of the of  the scheme. Basically you want to capture a large amount of data with a very small authenticating  uh authentication structure. So um so first um what is a um authentication structure? what is the  the primitive that we're working on. So we call it um the authenticated key value storage and yeah  I think people in uh in different communities like cryptographers they they call it um like  authenticated database I think system people

they call it um authenticated key value storage.  So basically it's it's just a mergry right. So you have a bunch of key value pairs for example your  um your account balances in Ethereum or um your your unspent UTXOs in Bitcoin whatever right you  but you want to capture um so for example Alice has $10 and um you want to compute a commitment  think of it as a as a hash um of these key value pairs of these individual elements of information  and um the commitment is useful because um you can generate a proof very efficiently and also  verify the proof very efficiently then that some particular um key value pair or some particular  like data element belongs to the commitment in

the sense that say I tell you that uh the current  state of Ethereum is captured by this commitment 0x that beef and then I can very succinctly prove  to you that my my balance for example I'm Alice my balance is $10 with just a very short amount of  data. So this is why why it's useful, right? It's basically what uh Merkel try uh allows you to do  and um yes so these kind of data structures they also allow you to update those uh state elements.  For example, Alice balance increased by uh by $10 and you can accordingly increase the commitment  to to reflect what's the the current state.

So why why why is this interesting, right? It's  interesting because it's by far the most important performance bottleneck on Ethereum or or any like  similar blockchain that still hopes to uh to uh to produce a up-to-date state commitment in real  time. So what I'm showing here is um um the like throughput or I should say the the amount of time  for you to um process a bunch of um historical Ethereum transa historical Ethereum blocks from  the Ethereum mainet on a machine with a relatively uh recent version of Wrath the currently um  leading edge um state u sorry Ethereum execution client. So basically what you're doing is you are  rerunning those Ethereum blocks updating the state

roots and also doing other things in real time  and uh then we're measuring the amount of time it takes for you to finish the process. So the  time is basically a metric for how performant this process is and uh by the way we also vary the  amount of memory available to the server just to test different scenarios. So here the green bar  the green section of the bars is the amount of time taken by those um reexecution processes  to update and maintain the state roots or to update and maintain the state commitments of those  authenticated uh key stoages. So you can find you can see that in um the ideal case where we have  like virtually an infinite amount of memory for you to use um maintaining the commitment takes  five times seven six amount of time than it took

um the process to actually run the transactions.  So basically you execute a transaction that you spend almost six times longer to u do all the  maintenance work on the state commitments which is arguably not useful work if you only care  about like transaction TPS right and um the issue worsens to nine almost 10x uh when you have  a limited amount of memory which is usually the uh the realistic case so um it's pretty tough  because sorry um yes it's pretty tough because um that basically says Hey, I want to build a really  fast blockchain and uh I it basically says that um if we uh don't worry about this um authenticated  key value storage, if we don't worry about like updating the commitment, then um it seems that  the best we can do is to remove the the purple

section and the the the blue section and at most  we kind of get a 10% improvement because we're not addressing the like the elephant in the room.  So this is really an very uh important problem and the reason that Merkel position tries or the  standard uh state authentication like uh key value storage used by Ethereum or most uh blockchains  is because they generate a ton of um random disk ios when you try to update them. So what you see  here is each node in um this Merkel Patricia try data structure is the hash of its children. So um  and also um the tree is structured in the sense that if you follow the path so each edge in the  path each edge in the tree has a u like a label a

segment of your key or of your address associated  with it. So if you go from the root and uh if you traverse the path that reconstructs your say your  wallet address then that's how that's basically the the list of nodes the list of internal nodes  that you have out that you have to update when you update your uh when you update your key. So  basically when you update your key you you have to kind of propagate all the changes back to the root  because they are all hashes. You you touch it you have to touch all the all the nodes in the middle.  Um and uh this generates a ton of um random disk ios and uh worse still it's sequential. So you  cannot even like do it at first and uh um and then hope to do all the remaining updates in  parallel. It's impossible. You have to do it

sequentially and it kills performance on more than  an SSD which has a ton of IOPS or IO's per second when you do them in parallel but not too much  when you do them in sequence in a sequential way. Um so this is why um Merkel position tries or the  like the state-of-the-art um or at least like the status quo data structures are not very ideal when  it comes to um speeding up updates or speeding speeding up like updates to commitments. Um but um  they also have some nice properties. For example, they are what we call historical history  independent in the sense that the state root is a pure function. pure function meaning  that there's nothing else like involved in the computation but of the actual state elements that  you want to capture like the account balances also

um Merkel partition tries are easy to maintain  um in the sense that it does not really burn a lot of CPUs or or memory or disk space or a  lot of bandwidth so um the wish list for us is to keep the nice properties of Merkel petition  tries but try to minimize the disio because this is what makes like updating state rules 10x slower  than executing transactions on Ethereum. Um so a crazy idea here is hey can we store the entire try  the entire merric try or whatever data structure in unreasonable amount of memory because if we can  fit everything in the memory then there's not like there's no bottleneck from like the sequential  dis IO's right we kind of skip you kind of get

around this um IO random IO issue um altogether  um so to to see if that is actually feasible able um there's a very important metric which is the  amount of data you have to store for um per state element you want to commit to in the sense so  we have heard of this um state bloat issue right Ethereum state is keep keeps expanding and it's  going to say 10x in the next say three years and uh with that it seems that the try the size  of the state uh commitment data structure the size of the um authenticated key value storage  will also expand 10 by 10x and at some point you cannot fit it in the main memory anymore. For now  it's possible. It's about say 100 gigabytes but

uh very soon it it may not be possible anymore.  So the the key metric we we optimize here is that we want to commit to an everexpanding a large  amount of um state elements or accounts or UTXOs with a relatively small like auxiliary data data  structure. the authenticated key value storage. We want to minimize the amvertised cost of this  authenticated key value storage data structure per state element that we uh commit to. So let's take  a look at how um Ethereum Merco Patricia try a fares. So in this case um record patricia try has  um about 16 exactly 16 uh children per node and um the number of levels in this data structure or  how large or how tall this data structure will be

is roughly the number of nodes or the number of  um state elements you capture divided by um yeah divided by uh your your depth sorry your your your  width uh which is r Sorry, I think there's some uh formatting issue. Um but basically in the ideal  case actually to capture say 1.5 billion uh keys or 1.5 billion addresses you only need about 3.2  gigabytes which seems nice but again this is the ideal case. in the realistic case because um there  is something which we call sparsity in Merkel producer choice that makes the actual like um that  makes the actual data size of Merkel petric much larger than this ideal case. So um in particular  we found that when you go deeper and deeper into

this Merkel Patricia try um there are fewer nodes  or each node has fewer children and um when a node has less than 16 which is the optimal the maximum  number of children it has it can like capture a smaller number of children right by definition.  And because each node is like managing a smaller number of children, if you ultimately want to  handle the same number of um accounts or um nodes in the bottom layer, you have to add more nodes in  the in the in the in the middle because like yeah, it's because each node has less children, right?  Each node is managing a fewer each node is not doing each internal node is not doing its best um  capturing the hashes of its children. So you have

to use more of them and uh that in that expands  that kind of inflates the the number of internal nodes and uh um yeah the the size of the tree  just expands and here is some theory and some um experimental data. So the the the points are  from our experiments and the curve is derived by some theory and um the optimal case is the  uh the black curve which is on the bottom and uh the realistic case is the the green curve  here. Um and you can see that there's almost a um eight times difference from optimality to  um to the reality. And um yeah in Ethereum's current size 1.5 billion uh keys you need almost  17 gigabytes to fit all those internal nodes.

It's just internal nodes. So um there has always  been a proposal of say um vertical tries where the essense is basically you expand the like  the width of the tree to make it fatter but um um shallower and in theory that should help  you um reducing the the number of internal nodes but it seems that because of the same issue  because of the sparity the the like like the the effective is limited and from the optimality  which is the black curve vertical tries Um, basically 256 array radics tries they they don't  do so well either. And uh we can even that and we even proved in theory that even if you just keep  expanding like the width of the tree to make it to compact it to make it even shallower and shallower  um you only achieve so much. So um the purple

curve is the uh the average case at different  arity or at different like width of the tree and uh the vertical bar the the y-axis is the uh  the size of the um data structure divided by the number of keys basically the per key per account  overhead when you want to authenticate them. Um this reduction stops at some point even if you  keep increasing the arity and the trend actually goes and just goes horizontally where um the uh  optimal case which is to use a complete perfect um balanced tree um you get the the like you keep  getting um effectiveness as you increase the so it just says that just blindly expanding the width  of the tree does not really help. So um the so

what we have uh learned so far is that we want to  minimize the disk IO when you um uh like commit to and when you update the state state commitments  of your blockchain. And um the idea to circumvent this random disio issue is to fit the entire  authentication data structure in the main memory. And um the key metric we optimize for is to reduce  the amount of overhead in terms of bytes per um state element committed or per address or  per key um to a minimum. And the challenge here is that you've just blindly follow the like what  traditional um algorithm or data structure people tell you which is to expand the width of the tree  you hit a block which is sparsity and that kind

of limits how much you gain from uh from these  protocols from these schemes. So what we did is we found that actually there is a trick that can take  which are not elaborate. Um but basically what we learned was that a perfect data structure  should be heterogeneous in the sense that um you should divide your data structure into two  parts. want a static main try which is complete. Basically what computer scientists are hoping  for um in the sense that all the nodes inside this static main try is complete and has all the  children it it should have um filled with and then you replace the bottom layer which is plagued  by sparity with hashts. Hashts are nice because

um they deal with sparity very gracefully. they  they don't really like expand in number of layers. you just you just resize the you just resize the  hashts and um um it can accommodate a different number of um elements fit inside um without  really incurring extra extra work basically that's the way I would I would summarize and um so  this is basically our um data structure we have a um main um try which is complete and uh shallow um  no no spaces being left no space has been wasted because it's complete. It's it only covers the the  top layers which is not plagued by sparity. And um yes and um then we have the buckets which are  hash tables instead of sub trees. Um these

layers usually in um regular in normal trees in  normal MPTs they are plagued by sparity but but yeah hashts are are immune to that and um you just  like fuse them together you get a very nice data structure. I will um skip through the process  of using this data structure but you ultimately get a very nice data structure that outperforms  Merkel Patricia tric or any form any variant of it um by uh almost um 16x. So here again I'm showing  the reality with Merkel Patricia choice which is the blue curve um the purple curve which is  Merkel choice in theory and the optimality um which is complete trees which is the like the  dream of every computer scientist but if you look

at our data structure which we call ST um it kind  of approximates it approaches the optimality when the number of keys is large enough and here it's  about um 10 billion ion. Um so basically in the in the case where we actually care about which is  about 10 billion um accounts um you and also going going from that beyond um we approach what you  can do um optimally with those um authenticated key value storage data structures. Um yes and  we uh did a bunch of we yeah we actually took an implementation in our test net and we did a  bunch of uh tests and uh it shows that um the new data structure completely um gets us around  this random disk io um bottleneck and the IO

bottleneck is no longer a an issue for us and u it  has slightly increased computation cost compared to Merkel partic but it's manageable and uh it's  paralyzable. So if you just throw more CPU cores, which is very easy to do, relatively easy to  do, um you get to higher throughput. And um we also compared it with um a few other um recent  works on solving the same problem. QMDB from um I think layer zero and noomt I think from  solving labs. Um and we found that our performance um is better than theirs um at a cost of  slightly again increased CPU consumption, but again CPUs are cheap. disk IO is very hard to  scale. So this is kind of the approach that we're taking and um yes so um short on time so I'll just  pause here. Um it's been live since day one of me

testn net um this March and uh we're going to  ship it in mainet very soon. [Applause] Yeah. Um if there's a Q&A session I can take a few  questions uh on the stage or offline. Yeah. Uhhuh. Oh, I didn't say what date  uh we are shipping, but yeah, it's a nice question. Very, very soon. Yeah. Thank you.