Understanding Design Choices in Data Availability Sampling

Transcript

thank you um so yeah I'm Leo I work with the Codex team we are a team that specialize on decentralized storage and this work was done in collaboration with my colleagues uh shavan Dimitri who are sitting in the public so thanks to them but I also want to thank JSC Eric Ben Mark and all the other members of the Codex team for so many discussions that help in this research and I also want to take Italian Foundation because of their trust and so many discussions in this collaboration that we are doing with them so today I'm going to talk about ethereum scaling about the structure for data availability sampling the model input the data that we have gathered

from the Ethereal Network and also uh the simulator that we are building and then I will finally conclude so we want to scale ethereum so if you think about ethereum like a small computer in the old 90s we want to transform that into a super computer now when we talk about performance in blockchain technology we talk about number of transactions per second so today with a about 15 transactions per second and we want to scale to Something in the order of tens of thousands of transactions per second in the future now to do that we are focusing on a roll-up Centric approach that has been already presented in the last few days but the thing is that Roll-Ups needs

data where they have to you know put their information and so for that we need to increase the block uh the block size and so today if we look at the average block size for the ethereum blocks is about a hundred kilobytes and we want to increase that to Something in the order of maybe to 32 megabytes all right now the problem is we don't want all the networks in ethereum network to be super computers to be able to handle so much data so in order to solve this uh we have to do sharding more specifically data sharding okay and then when you are doing Nita sharding basically you are taking your block and you are Distributing that

block in different chunks and you are sending the chunks to different validators in the network but nobody in the network has the entire block no and there is a risk because then if some nodes go offline then you might lose some of the data and then that force you to do what is called Data availability sampling now there are several recipes for datability Sim available availability sampling we focus on this one uh that is the one that I'm going to present today so you need two cups of ratio coding better if it's resolving encoding a tablespoon of kcg commitments and a lot of sampling now there are a lot of recipes for data availability sampling out there I'm not

saying that this is the only one perhaps even not the better the best one but this is the one that we are exploring right now and that might change in the future now uh what you want to do is you take your block you divide your block in different chunks and then you Erasure code that and then you have some extra data that you can use in order to repair your block if something uh goes down so if you lose two chunk for example you can repair it if you lose up to four chunks in this particular example you can repair it um and then you can recover all the data now this is not uh enough because it could be the case that the block proposal actually distributes the data but it also distributes parity data that

is not really parity data but only garbage data and then you will not be able to recover in case of failures so to solve that we use what we call kcg commitments and is basically a proof that says that the chunk of data that you are getting is uh part of the polynomial of the resolument equation that you solve in order to do the encoding and this is a small proof that guarantees you that the piece of data that you are getting is actually something meaningful and that you can use that in order to recover data when data is missing now you can do that in a two-dimensional structure and so basically you use uh to block data you put it in the blue

squares that you see there and then you Erasure code all the rows and then you get this kind of structure but you can also do that with all the columns and then you can also repeat that with all the rows and columns that you have encoded and you end up with a structure like this now to give you some numbers of how the structure for that looks like today basically you have samples or chunks that are in the order of 512 bytes and to that you're going to add about 48 bytes for the kcg commitments and then you the original data is the blue part of the block and then the red part is what you generated with the racial codings

and so um what you want to do here so in this particular example we are working with blocks of 512 columns and 512 rows and then uh that gives you a super block that is more or less of the size of 140 megabytes okay so um when you are looking at uh block availability like for example if you have only the original data you can ratio code that horizontally and then you generate that part and then use the rest to encode vertically and then you generate the whole structure now let's imagine that you distribute the block over the network and a bunch of nodes go offline and you end up with a structure like

this on the left side so do you still have enough um 50 of the blocks of the chunks uh in the in the left side to generate uh the rows and then once you have all the rows being regenerated you can use that to regenerate The Columns and then you have reproduced the holy structure again but now let's look at an example that is not possible to reconstruct here you have three rows that are entirely correct three columns that are entirely correct and the rest of the data has disappeared over the network in this case you cannot reconstruct any other row or any other column and then you have lost too much data and then basically here

you can to say you can say that the block is not available okay so in this case we don't want validators to address for this block all right now that is about the structure of that now let's talk about what happens after you generate the structure so the block Builder sends this block to the network but how does it do it uh it has to disseminate rows and columns to different validators so each validator in the network will get a specific number of rows and columns it could be two could be four could be eight we are playing with those parameters after that you populate a DHT with all the samples of the block and then you do sampling to check that the the blocks that the chunks are actually

where they are supposed to be if you find all the data that you ask for that means that the data is available and you can attest for that block but in the presentation today I'm going to just focus on the dissemination of rows and columns to the validators which is the first part of the simulator that we are building now as I said you have this block Boulder Builder that is connected to the network and is connected to many Bitcoin nodes and so you may have been you might maybe connected to a validator that is behind a bigger node but there are also bigger nodes that have multiple validators and then they will have to access multiple rows and multiple columns uh depending on the number of

validators that they have behind now let's focus on the data that we know from the ethereum network today for that we use um the crawler that we have been developing for a couple of years already you can access it in the QR code and there is this public dashboard that that we have so all this data you know is not a hundred percent exact vision of the ethereum network because Crowley appear to peer network doesn't give you an exact figure to this but it does give you a good estimate of how the Trillium Network looks uh today so um you have about 10 000 nodes in the network today about 40 Lighthouse 40 prism uh between seven and 10 and 10 are Nimbus and teku and then a few others

let's start a few others regarding the number of uh nodes that are subscribed to at the station networks we see that about 6 000 are not registered in any other Station Network and there are about a thousand of them that are registered to 64 at the station Networks these thousand nodes most likely are hosting many many validators perhaps in the order of hundreds of validators behind one single Bitcoin node so we can use all these data to put it into our simulator and understand what is happening we also know that about 55 percent of the nodes are in a in a cloud and about 40 of them are in residential homes uh regarding latency we also see that

the distribution geographical distribution is not that great that was already mentioned in the Latin talk which is very interesting but regarding latency we see that most of the nodes are located within 100 milliseconds from each other uh when you look about the networks at the sorry the nodes between them you will see clusters that form like inertia which is the top left side of the heat map in the center you have Europe and in the bottom you have America but most of them are located within 100 200 milliseconds so we can use that to plug that into our simulator regarding bandwidth we also did a study I'm not going to go too much into the details here but we have a good estimate about the average minimum and maximum bandwidth of the notes uh of the notes

over the network now the simulator so um we are working with a simulator that relies on gossips up gossip is an efficient and reliable protocol it uses a graph mesh to push messages you have nodes that are connected to six to eight nodes and then you send gossips in order to pull new content now here the idea is that you will have one gaussy sub channel for every row and column in this largest structure that I have presented so um if you look at um a structure with 512 rows and columns then you will end up with about a thousand causes of channels

uh the simulator is highly configurable we have a large simulation space so you have you can configure the number of nodes the type of nodes the number of validators per node the network degree the failure rate and so on and so forth we also have other parameters like if we want to make the simulations deterministic if we want to plot all the results and so on so if you want to access the simulator you can scan the QR code and you can play with it now just to say this is a work in progress we started working on this a few months ago so if there is something that doesn't work perfectly feel free to contact us we'll be super happy to uh to help you and to work with you now um just to give a an example of the

configuration file I'm not going to go through all the details here but yeah just to explain you can parameterize the number of nodes in the network and you can also say what are the type of nodes that you want to see in the network so for example you have two types of nodes uh what you have the Solace takers there are small nodes in houses that have perhaps a small one with and that only hosts one or two validators and then you have like the really large nodes that are probably you know mistaking pools that they have maybe hundreds of validators a great internet bandwidth and and great Hardware resources and then you can also configure how many validators you want to set in behind

each one of those nodes oops you can also configure the block size so this um is to parameterize how much data you want to put inside a block you can also play with the number of rows and columns that you want to send to which validator this is an important parameter uh for the for the for datability sampling because the more rows and columns that use that you send you have more reliability you have more redundancy in the system but you are also consuming more bandwidth and so there is a trade over there there's a sweet spot to be found uh we can also configure the latency of the network we can also configure the

sample size and we can also configure the bandwidth and actually you can configure different bandwidth for different types of nodes in the network now after you launch the simulations as I explained you have a combinatorial space with many many dimensions uh and then when you launch the simulator you will explore all these possible combinations that you set up in the configuration file and then you will get results for each one of those simulations and then I will explain here just a few examples of what the results look like and what are we doing with those so on the right side you see the number of validators that get assigned to a specific row or column okay so in this

particular simulation we launch it uh 7000 nodes and with the configuration of validators per node that give give us something in the order or 530 000 validators which is relatively close to what we see today in reality in the Bitcoin chain and we set up the block size to be 512 so it's normal that the x-axis that you see here goes until 512 because you only have 512 rows and columns and then you see how many validators are attesting for are receiving those uh rows and columns now on the left side no sorry right side for you um do you have the progress of how many um samples are received from the

beginning of the simulation until the end of the simulation please know that the x-axis is milliseconds and it goes up to 600 milliseconds so it's a little bit more than half a second to distribute one block over the network it goes from zero to hundred percent the blue line is the number of validators that are that have received all the samples that they have to receive and you please notice there is a bigger Spike and then the green line is the number of nodes that have received all the all the samples that they have to receive now you might be wondering why the blue line is not the same as the Green Line because validators are in nodes and the reason is because the blue line just says when the validators receive it in the green

line you only count as ready when all the validators inside the node have received all the samples okay so even if so if you have 500 validators you might have received 499 validators all the all the samples but maybe one validator still didn't receive uh all the data that it was supposed to receive so it will it will see this this delay of about 50 milliseconds or so now when we look at the network in this particular simulation we are using five gigabits per second for the staking pools and 50 megabits megabits per second for the Solace takers now please don't take this number as the ground true this is just an example of a

simulation that we used and you can see that this is exactly what we see we monitor how much data is sent and received over the network on the left side you see the send data and on the right side the receive data and you can see that yeah we are using the the demand width at the maximum in order to distribute all the rows and columns that we are supposed to distribute and for the Solace takers which is the light blue cyan line in the bottom we see that we don't pass the bandwidth that it was written in the configuration file now all this is nice but then what else can we do with this simulator so one thing that we can do is try to explore the breaking point okay how much failure

rate I can accept in my system until the block is not available anymore so here is an example of that on the left side you see the same simulation I just presented in which the red line goes to 100 meaning that the block became available and everybody received the samples that they were supposed to receive on the right side you see a simulation where the blue line and the green line are non-existent because the validators didn't receive the data that they were supposed to receive and this is because I increased the failure rate up to 80 percent and then what happens is that uh we send some samples some validators try to reconstruct some of the rows and columns using reseller morning coding but they

don't manage to reconstruct everything and the whole thing estaganates at 35 percent where there is no more samples that can be reconstructed in any direction and then nobody sends anything anymore and then at that point we are not making any progress and with the block is unavailable okay now another thing that we can do is to say well instead of sending the whole row or the whole column maybe you can send only the original data and let the validators pre-create the Erasure coded data by calculating the results encoding themselves in that way you save 50 of bandwidth because you only have to send 50 of the data and then maybe the simulation will be faster

and and this is what we see exactly um if you notice uh when we send the whole row and columns the simulation finish the block distribution finish at 600 milliseconds if we only send half of it then we finish at 400 milliseconds so that's an improvement of 33 percent in time to availability uh for the block okay so this is just to give you a few examples of the things that we are doing with this simulator there are many more and so if you are interested again please check out the the repository and feel free to contact us so in conclusion there are many recipes to building data availability sampling we are exploring this one but we are not close-minded we are leaving the space open there are many changes that can come in the future

we are building the simulator to study all those different parameters and to find the best combination to implement data availability sampling for the scalability of ethereum and we are also measuring ethereum Network in real time so that we can plug all these real data into the simulator and get the best possible solution finally I want to say that our team at codex is working on long-term storage which is also an important problem for ethereum and so if you're interested in that please come to talk to us thank you very much [Applause] [Music]