Understanding Design Choices in Data Availability Sampling

Transcript

[Music] okay so hello I'm Chaba from the Codex team this is a joint work with my colleagues Leonardo and Dimitri boss from the correct storage team this is also work which is received in ethereum Foundation Grant so we would like to thank for the time foundation and for the collaboration that we have so I will be speaking about data availability sampling as an outline I will be going to kind of five fast topics first I will speak about scaling ethereum then I will introduce sharding and how sampling is done then I will so basically done

shutting then I will look at the networking perspective behind this and then our simulator from which we are deriving results so it's getting ethereum so everything starts with the desire to scale ethereum right today we have something like 15 transactions per second and this is how we measure the speed of blockchain and we would like to have more how much more uh is a good question either I was putting 15K but tens of case of transactions per second and the scaling problem is partly solved right we have develops and that is a load map to introduce olaps but zolabs should still store data on layer one so we can add sword partly not uh because the other one still have his

blocks and these blocks are still somehow Limited so at the end of the day what we want to scale is the layer 1 blocks which are now around 100 120 kilobytes in size so let's scale the blocks how about how much we can scale the blocks and that's a good question to which we don't have an easy answer or let's say we have easy answers to scale the blocks when we are scanning resources if we are not using uh small nodes homesteaking but we are going data center but it is ambitious and they definitely don't want to do that also because that would compromise decentralization so how much you can scale blocks if you are not doing that if you are still doing uh homes taking

and blocks I'll get into these nodes so we don't know how much we can scale blocks uh does that was an experiment uh with the ethnic Foundation uh to test the capacity of the deal mainnet uh now testing on mainnet is not that easy so they were creating large transactions they have submitted these transactions made a fee uh these were getting into large blocks then these large books were finalized so we know that a block of one megabyte can be finalized and that's a nice result uh but that would be a bit of a waste to do just that so they did more uh they were doing setting up notes which were measuring to The Matrix manual ethics but what is interesting for us is block propagation latency so

there are nodes in the network a few of them each client implementation actually running a few nodes which will remaining measuring the block procreation latency of these nodes and what you see below is a dashboard showing uh a timeline and where you see on the figure below the deadlines those are blocks which have a bigger size so those are blocks in which there are these transactions and you kind of see that there is a correlation right but those latencies are a bit bigger uh but that's a kind of a correlation so we did some work to actually collaborate this database block size and to see how uh the propagation latency the diffusion of the Block in

the network depends on the Block size now for this we took data from from data and some other sources and we came to this so how you lead such a figure so let's look at the blue curve the blue curve is showing small blocks so small blocks between 0 and 32 kilobytes and a point on the blue curve let's say the 2000 line that's two seconds uh if you go up up up you see that 95 ish percent of the blocks of the uh of the measurements well below this so we measured in several places measured for several blocks and blocks and 95 percent of the

of the measurements were below this so you can say that 95 percent of the of the arrivals are before that and then others are after that the problem is that if you go larger with the block size you see that time is increasing and the other problem is that there is a deadline which I was not showing here but four seconds is a deadline and why here it seems like everyone is is meeting that that line you see that small percentage on the top which is not meeting the deadline and then you could imagine how if you would increase the work size these curves would shift to the right and you would be in trouble so uh so we know that you can scale block size a little bit but not too much uh so we can do different things uh we can try to optimize the protocol uh and

that was a nice presentation on that yesterday for my colleague which you can find here uh but this is not what we want to speak about now we want to speak about another approach which is sharding and sampling so what if we want to scale beyond the single block size limitation uh what if most nodes have no chance to download the block because they just don't have the resources so you should look at why we were downloading block and there are two kind of independent reasons to download the block before one is that notes will verifying the block and the other one is that nodes were having the block as they were having the data does they were knowing that the data is available so after data sharding you will not have

these but nodes don't leave me in the block because the data which is inside the Lola data is not something they should interpret so they don't really need it uh and they don't have the blocks so they don't have data availability they don't know about it so they should do something about this and this is what they do they are we are segmenting the block and they are sampling that block and this is what we are speaking about so how you segment and Sample the block well that's easy segment on the Block choose a piece download that small piece from someone and if you got that you kind of know that with some probability uh does the block uh if you have K segments and you download one it's one of the K if you download S It's s double

k nice linear the problem is if there's just one missing you have so few low probability of figuring that out so you do more you do Azure coding so you segment extend and then simple so we use Azure coding in which we extend the data we had the four segments we are extending it to eight segments and now the probability that we have is any fault is enough so if we know that uh if the at least four blocks available for segments available then the block is available now if it's simple you know much more if you sample one you know with half probability if you sample twice you know it's equal to Priority Etc that the block is available

but that's actually still not enough because when I was saying we are extending data visualization coding you were believing me that we were extending data that we started recording but no one is guaranteeing that so when we are extending database other coding uh the block might be extended with garbage and then you have simplink you are downloading a garbage and you say yeah the block is good I Could reconstruct it but then when you try to reconstruct it you would figure out that you cannot see constructed so it's actually not available so we need to prove that the other is recording is actually good so we use uh kcg commitment over the Polynesian polynomial which is used for delete someone encoding the

other recording so that uh the data the actual allegian extension is proven so when you have the commitment you have the segment and you have the proof this is self-contained and this is telling you that this is a good one so you can actually sample again so this would be good but this is still not enough we have which is extending but it has a problem the problem is that when you want to repair you need all four chunks to get the other ones so you basically when you would need to repair you would have to download the block so you could easily get into a situation where you cannot CPL because you don't have the bandwidth and it

would be a chicken leg problem but you can do something else you can do a two-dimensional needs someone encoding a two-dimensional extension which has this property which not going too much in detail is that you can repel some partial data so you can repair any low or any column on that structure below and uh so you're just simple and if something is missing a low low the column can be repaired now I know this was very fast and there's more so this is the actual concrete structure of dunk sharding as it is animation now just to put some numbers uh behind it so we have 32 megabytes of data in a block and this is

just Lola data uh which is segmented to 256 times 256 segments so it's 64 000 segments each segment is 500 bytes and then you are extending this structure to 512 times 512 so you have lots of segments and then there are kcg commencements behind this which is actually quite computational intensive to calculate overall you have something you started from 32 megabytes and you are driving to 140 megabytes each 12 seconds to distribute but not distribute fully so just a quick reminder and availability so I was

saying we can repair on the column and below so what does this mean what does this mean is this book available uh if those segments are available and the others are not and if you would sample you would most probably say no it's not available because we would most probably hit on something which is not there but if you are depending and sampling then you say yes it's available so this is a block which is available if you are sampling it at the wrong time it's not but uh but we are sampling we would say yes it's available and it is available now this is another one is this available not available again we have 25 percent of the data uh and yes it's available you can repel it is this available

and you will see how you have lots of data this should be available but actually this is not if you look at it that is in the upper left side of the black thingy which is missing you could put anything there and you could repair it so it cannot be repealable because there's a point where you could put anything and in fact you cannot do a repair there is no line or column which has at least half of the data so you are stuck and the data is not available and well I have the N that data is missing from the original so you have a missing sync uh that might be a transaction which is blowing up your level up so this is definitely not available is this available this is defined not available right you don't have enough

data for this to be available you have less data than the original block so it cannot be available well you could do some repairing but still it's not available okay so now we understood what is what is uh having a block extending it and sampling it but this was all kind of very theoretical we should do it in the network right all these things should go on the network so what's happening on the network while we are doing this so how we check data availability over the network and here I think I should remind you that there are different actors in the network that are validate to this and there are four nodes and they have different goals

the check is kind of a first line of defense and the second line of defense so validators they are the ones generating the other stations uh and the other first line of defense if they're not infested at the stations the block will not be part of the chain and actually many blockchains are happy with this but ethereum is ambitious here as well and they say this is not enough we need the second line of defense we need also the full notes to do sampling to figure out with very high probability if the data is not available even if the validators did something nasty so we have first and second line of defense and then we need a system which is serving all this

so how does this work first of all maybe I should note that we have here here the process separation so you have a Blog Builder and this is building that huge huge structure and then it is cutting it into this rows and columns and it is sending down specific rows and columns to the validators actually each validator is choosing some of those in some columns let's say two rows and two columns and say I'm checking only those and I'm checking those of those and those columns and if those are fine I'm fine I'm signing but that's only for the validators then there are the Denver nodes so for them to sample we need something to sample

from and it cannot be the probability so the data is uploaded into a DHT a distributed hash table and then the full nodes are sampling from that and then on top of all this we need repair so it's quite complex today I will focus on the first part which is the dissemination of samples dividend the switch is complex enough so what happens here from Builders to editors we have say two uh lines or lows selected by each other and we have a dissemination some reliable the best decentralized

published Supply mechanism which is sending the data from the Builder to the validators interested in in those specific things let's say we have actually now we have more but we have 500 000 validators we have something like eight thousand Biko nodes behind which that is 500 000 writers we have a large amount of segments we have many loads and actually we have four seconds to do all this distribution of data so how do you do this uh we use something similar to what was used before uh we use I was saying we gossip sub like protocol it's kind of Gossip sub it's not exactly the same and it's not yet clear exactly but we are

studying it so what you have seen before was the block for the big block sent to All Beacon nodes behind which that could be one or many of our debtors um in one gossip sub Channel and then in the system we have other gossip sub channels or decode topics so we have other gossip subtopics we have something like 67 64 plus uh some a few here we would have 1024 gossip subtopics Chris crossing the beacon notes and sending down rows and columns to them so this would be an example of one gossip subtopic which is column number 233 and imagine 1000 of these glucing

we like gossip sir because it's the best it's reliable uh Gossip sub for those who don't know it is sending is pushing data to many neighbors so it's forming a mesh a graph with each node having six or eight neighbors and when it receives the data it's pushing to all of them and then it has another mechanism which is uh it is telling the other nodes randomly which what data it has so others can ask for it this is the pool and then it is doing the sanding of a TCP so when it sends it sends reliably it also has some downsides it has lots of duplicates and it's not yet ready for the last messages if you have seen that are improvements

the important things to note here is that here we have two other reliability menus so we have the mesh as we said in which the data is pushed we have the gossip uh pulling data when data is passing from one node to another one it's reliably passed using TCP and then we have the lead Solomon code the least common code means that we can when we are sending the law it's enough to send half of it it doesn't even matter which half so I can just send some of the segments from the tool and the other side if it has enough can restore the hollow and then we have another mechanism because we have the those and the columns

so if you receive something on a row then you can switch it on the column and send it on the column so it is a complex system which has five the liability mechanisms and we don't know really how to play it so there's lots of things to study which we like and that's why we are building a simulator so the simulator the simulator is uh to simulate this shouting and data we're at the same link you can find it there it is simulating the the as encoding obviously it's not doing it because it doesn't have to do the additional coding well it doesn't have to do the uh the tools and then it simulates the dissemination

to validators it does it simulates the 1000 gossip sub channels it is not doing yet the DHT and the sampling it's highly configurable so you can Define simulations and study things like what if I would have much more nodes but if I would have fewer notes what if I have a strong note uh institutional stickers what if I have homesteakers how many validators are designing uh how I'm configuring my gossip sub what is the degree of neighborhood what if there are failures what is Network bandwidths and then many of those things so it's quite easy to configure it's basically python python code so you just set the number of nodes type of nodes bandwidths

values in a configuration file and you can also set up studies so you can set up Lane studies from this to that parameter and then it explores the whole simulation space so when you do a single simulation run this is what you see so this is an example there's one Builder and let's suppose it has 5000 megabits per second link it's kind of reasonable to assume uh Mr Builders data today and let's say we have 7000 nodes of which uh 500 5400 uh I was calling them class one this is basically

homesteakers so homesteaker is was putting in its 32 East and it's running it's one validator behind one node and it has let's say a 50 megabits per second Uplink and then we have a bunch of nodes which are institutional stickers they are running a beacon node and behind it we can note that a bunch of validators let's say 500. we could randomize these numbers but it wouldn't add too much uh to the simulation so we are just doing these two classes and let's say they have uh they also have five wickets per second links and then you start simulating and these are the curves that you get so the most interesting one is on the top this is telling you uh well the most

interesting is on the bottom which is the time so you have the time axis and then you have evolution of different things in time and the most interesting things in is in the top of which the most interesting thing is the green one the green one which is telling you how validators style to validate but nothing happens and at one point basically everyone is validating and the block is fully validated the blue that you see is kind of plugless in segments received so we are sending segments and we are randomizing them so we are sending them down one by one on these links on all the 1000 topics and notes are receiving segments

but no one has enough to to validate and at one point basically everyone has enough and this is kind of a nice probability of the system that does this changeable and then uh does the orange curve which is measuring how many nodes already so what you see at the end is basically notes uh those are home stickers which are validating a bit later in this specific scenario and then we have measuring other things we are measuring the uh the traffic utilization how many duplicates are also useless traffic is generated by the system because of Gossip sub uh and so on and so forth but the nice thing is according to this simulation it finishes in less than a second

right now it finishes with less than a second with many simplifying assumptions of which again if you go to the talk on the zip sub that I was referencing before you can see many details on that but we are having some similar simplifying assumptions on the graph on tcp's Flow start and on latencies so let's take more conservative numbers we change the Uplink and benefits to one megabit one gigabit per second and then you are Distributing in in one second still really good and you can do other studies so this study is looking at on the left side you see

the figure that we had previously so what if this is if if the system is doing uh the distribution sending individual segments uh randomizing them moving them from those two columns and doing all the things that we could come out with on the right side that is a simpler version of the system in which on these 1000 rows and columns you are sending messages which are entitled those columns we actually have those in columns because you don't have to send the whole thing but you are not sending individuals more messages and you become slower as we would expect or you can do other interesting studies on the top you have a situation when the

Builder was releasing just enough segments so just enough segments released uh and you see the blue uh Oracle is going to 1.0 below almost enough segments released we have seen that case right the data is not available there is something missing and in this case we want the system to notice it and that's what we see the uh 75 percent of the segments actually alive so note C segments but actually the few validations validations have available and this is what we wanted so to conclude here we are looking at dunk sharding basically

but we add team working on codec storage and we do this because there are many things in common that we can learn from so we are using in collect storage editor coding like index clouding and studying was the best way to do it we both use subliminal verification with the sampling actually in different ways but we both use sublinear verification we both use the P2P stack and even more importantly this is important for us because there are lots of intuition in both systems which are mutually useful there are differences as well done Shades focuses on data availability in storage we are focusing on data

usability doesn't need long-term storage you just need to prove that things were released and that's fine and you are not doing this for long term we are doing long-term storage is doing interactive sampling notes are going and sampling we are doing snack based verification but both are subliminal modification is using physical size we are accepting our data sets but overall it's very useful for us so finally conclude we are building this open source simulator uh we are happy if if you come and die and contribute we are exploring multiple design for the Das we are exploring the Das parameter space to understand what will happen if

situation changes this way and that way and we are building a long-term long a long-term storage with codex thank you [Applause] one question thank you [Applause] [Music] foreign

[Music]