Understanding Design Choices in Data Availability Sampling / Leonardo Bautista-Gomez

Transcript

can you hear me yep okay thank you all right uh thank you very much uh so yeah I'm Leo um I got I want to present uh some work that we have been doing about data availability sampling I want to say this is a research collaboration with the Italian foundation and the Codex team uh which are you know my team members uh Team colleagues Shabba Dimitri and myself uh so before the start I want to talk a little bit uh introduce myself I come from Latin America I was born in Nicaragua I grew up in Colombia I did a bachelor in computer science in Paris and mastering distributed systems then I did a PhD on super computers at Tokyo Tech and then I work at the Argo National Laboratory in Chicago for three

years working on error detection for scientific Computing and then I moved to the Barcelona super Computing Center where I work on scientific Computing but also on blockchain Research I got several grants from the ethereum foundation now I'm a researcher at the status and the founder of Mega labs um so this is the outline of my talk um first I'm gonna talk a little bit about the motivation which is ethereum scaling then I'm going to try to explain the data availability sampling structure some model input that we have some data that we have gathered that we are going to input in our simulator so I'm going to present the simulator that we are developing and then some conclusions no so Eternal scalability so if we talk about ethereum like the global computer

what we want to do is to transform that into a global supercomputer that is way way more performant that we we have today so um when we talk about performance for this blockchains we usually talk about transactions per second today we can do about 15 transactions per second and we want to go into a world where we have the capability of executing ten of thousands transactions per second okay so this is a three orders of magnitude increase and this is uh extremely challenging of course now uh the idea is to do this to achieve this through roll ups okay but Roll-Ups need space to you know put data that they require for them to work properly and so for that we need to kind of increase the block size now if we

increase the block size um if we look at the Block side that we have today is usually in the order of 100 kilobytes and we want to increase this to say something like 32 megabytes now the problem of doing this is that we are kind of forcing all the nodes in the ethereum network to become super computers the self to be able to handle all this amount of data and to make it fast enough for this to work so instead of doing this what we want to implement is charting more specifically data sharding and these are charts by the way so the idea is that instead of handling the whole block nodes will only have part of the block so you can for example divide the Block in rows or columns and then you send a certain number of blocks

sorry number of rows on number of columns to different nodes so that's the that's the idea now what is the problem behind this is that sometimes node goes offline and then we might lose the data that they have right and of course this is unacceptable so we use something that is called a ratio coding it's a technology that is well known in computer science and the idea is this following one for those that are not familiar you take your data set and you divide it in chunks like for example four chunks as we see here and then you apply some magic mathematical tool that is going to increase that with some other fortunes for example and now that you increase you have four extra chunks of data now notice that this is not replicated data this is just some kind

of encoded data that doesn't mean anything if you look into it but will allow you to recreate any four blocks when they disappear if they disappear so doesn't matter which floor blocks you lose you will be able to recreate um the the lost data okay now this is all good well now really what happens if the block Builder is a malicious actor and then he's gonna send you the real data and then the Erasure data is not really a ratio data it has not been computed with racial coding but it has it's just garbage right so what happens is that you think you might be able to recover everything but in fact you will not be able because the data that you have for the encoded data is just garbage

so that is the problem how do we fix this is using another mathematical tool that is called kcg commitments and this allows you to uh when you receive that chunk of data have the guarantee of the proof that this chunk of data is actually has been calculated using reselling encoding and following the polynomial and etc etc okay so then once we have these mathematical tools we can build some more complex structures like for example two-dimensional encoding so for example you take your block of data you divide it in two-dimensional grid okay like this one and then you encode the first row all right you apply the kcg commitments to it and then you do the same to the second and third and the

four rows then you do the same with the columns and you end up with a structural IDs and then you can actually do that the same thing on the encoded data and then you will end up with a structure like this okay now this is the current proposal for um Dan shardin and it looks more or less like this I'm not going to go in through the numbers here um there online if you are interested but basically what you see here is the blue part is the original data or the data that is going to be blob data and there is Meaningful data and the red red squares are just encoded data that will help us reconstruct the original data in case many nodes goes offline all right um okay so what about

um this allow us to do is that when you have for example in here the blue is squares are the data that is available you can as far as you have 50 of the data in a row or in a column you can reconstruct the entire raw column so here we can reconstruct all these rows and then basically now we can reconstruct all the columns and we have the whole data set so the block we can say is available now if you end up in a situation like this for example you lose all these white spaces but then the blue spaces will allow us to reconstruct this for rows and then once you do that you can reconstruct all the columns and then you have all uh the the data available again all right now if you look at this configuration um instead here is more tricky you have

three rows and three columns that where you have all the data but all the other rows and columns have less than 50 percent of the data so that means you cannot reconstruct anything there and then basically this block cannot be reconstructed right so you in this case we want the validators to say well this block is not available therefore cannot be part of the canonical chain all right so this is just the first part of building um charting or data sharding but then we need more steps first we build this data structure we then disseminate rows and columns to validators Once to do that then we distribute these samples into a DHT and then we do what is called Data availability sampling which is nodes

actually sample for a specific chunks of data and then if they receive all the chunks that they are supposed to receive then we can say that the block is available for example if you sample 70 chunks of data and you receive all of them that means that you have like one in a trillion chances of the block not being available so you have a fairly high confidence that the block is actually available or reconstructable right so in this talk I'm going to focus only on the disseminations or rows and columns which is the part that we have been working on in our simulator so what you have is you have many nodes in the network uh Bitcoin nodes that are connected through uh to the to the network and behind each vehicle node you

have multiple validators or sometimes one validator depending on uh whether you are a Solace taker or you are an institutionalist taker right and you want to the blog Builder has to disseminate all the rows and columns to the validators you know according to their assignment uh committees okay so some of the numbers today we have around 600 000 validators um we have to distribute about 250 000 samples and we have about 10 000 Bitcoin nodes in the in the network yeah so all these data we have gathered using our crawler this is a dashboard that we have developed at Mika Labs if you're interested you can look at the QR code I'm going to have the time to present all the details here but just very to go very briefly we have a bunch

of data in the dashboard uh we have the number of nodes we know that it is up around 10 000 nodes in the network we know that the distribution is about 40 to previous 40 to Lighthouse and then nine percent to Tech who and Nimbus and then the others lost star Grandin Etc uh we know about the geographical distribution of the nodes we also know that about 55 of the nodes are in clouds uh about 40 of them are in residential homes we also know how many nodes are subscribed to a certain number of attestation networks and based on all these data we can put all these in parameters into a simulator to try to actually simulate uh the ethereum network but with data sharding and proton sharding so the simulator so this

is what we have been building over the last few months this is work in progress if you want to access it you can go and look at the QR code the the code is open source of course and but as I say this is work in progress so don't be surprised if you find a few bucks here and there and if you do please write issues and we will be happy to fix those or just you know contact us we'll be happy to work with you so the simulator you know simulates a gossip sub Network for those that are not familiar with gossipsop you know is a graph mesh in which you can push messages and then you can send gossips and pull new content content when you need it today we have about 64 channels for this for the different attestation

networks the idea is that in the when we Implement uh charting the data sharding and datability sampling in ethereum we will have one channel or one gossip sub channel for every row and column now today the structure that we have is about 512 rows and columns okay that's the current size that we are looking at but this can change in the future and so then we expect to have about a thousand gossips of channels in which validators will go to subscribe and say Hey I want to subscribe to row 27 and column 32 and I want to receive those for every block and so on and so forth now uh the simulator is highly configurable um we have a huge simulation a space that I'm going to present in a minute

and we have other parameters for example we can make simulations deterministic that means that they will produce exactly the same result bit by bit every time you execute it with the same parameters and this is extremely important for reproducibility okay we don't want that every time you launch the simulation you get different results and there is actually of course a bunch of Randomness going on in a network but we have a ways to make it deterministic there is a lot of other choices you can decide to Output all the data into XML files to plot the data and so on and so forth now I want to talk about the you know simulation space which is huge so this is the configuration file of course I will not have the time to go in through all the details but just to mention a few we can decide how many numbers of

nodes you want to have in the network you can also decide what are the type of nodes for example it's important to make the difference between Solace takers and institutional stakers because it's different to have one validator than running a thousand validators in terms of bandwidth and unload and then of course you can decide what is the bandwidth for us for each one of those types of nodes is not the same running revalidator.com they're in a huge cloud in a huge machine and you can decide also how many validators you want to have per node for those two different types of of nodes we can also decide the block size this this has not been decided yet how many rows and columns every validator should receive the latency of the network the sample size and many other things so

this is just to give you an idea of all the parameters that we can configure in the simulator that we can play with uh we can also play with the failure rate for example and so on and so forth so what can we do with the simulator um so these are some results uh that we have gathered this is a simulation running in 7000 nodes and around 530 000 validators so it's not that far from the current numbers which is I think 600 000 validators what you see on the left side is a figure that shows uh how many validators are subscribed to each row and column so as I mentioned we have 512 to do that's that's why the x-axis goes to 512 and then we can see that around

900 validators are subscribed to each rows and columns so there is a huge replication already going on there in addition to the ratio coding replication right and then on the on the right side you see a figure that shows how the simulator I mean how the distribution of the rows and column progress and the x-axis is in milliseconds okay so you can see that the whole distribution which is the red line uh goes from zero percent to hundred percent in about 500 to 60 hundred milliseconds so it's basically half a second the amount of time that it takes for this particular simulation with seven thousand nodes and so on so on to distribute rows and columns um uh to all the validators and then you can see the blue line is how many is how many evaluators have received all the

data that they need and how many nodes have received all the data that they need now what else can we do with this we can also look at the sent and receive data so in this particular example we Define that the staking pools has like five gigabits per second of bandwidth and solar stickers 50 megabits per second of bandwidth and this is exactly what you see here uh and this is for the block Builder and then the Solace takers they only have to share a slow amount of data uh but you can also play with the parameters that mentioned in the configuration file for example we can increase the failure rate to 80 and see what happens that means that 80 of the samples get lost in the network either because the networks are reliable or because the nodes go offline or because

there are malicious nodes that receive the sample and they don't disseminate them whatever reason right so and then what we see what happens is that the dissemination of samples get stuck at 35 percent so it's not 100 and then it gets stuck and it cannot increase and you cannot move Beyond there so that happens that that means that nobody in the network has any data to reconstruct any row or column and then basically nobody gets what the the data that they are supposed to to receive okay so this is the kind of things that we can that we can do with this simulator we can also for example uh change um the amount of data that we want to send for example instead of sending the whole row or column you can we can say well I send you half of it and then uh

you actually calculate the other half using result morning coding because you can do it right and then I say 50 of network bandwidth so what happens when I do that and we did the simulation and we see that instead of using taking 600 milliseconds sorry we take 400 milliseconds that means we are actually gaining about 33 percent in in time uh which is uh which is a great game um now I want to mention a little bit about codex because we're also working on the centralized storage now codex is a different um you know it's focused more on data durability which is different from data availability okay uh in the case of ethereum Dash we are focusing on availability and not on long-term storage so those are two different

perspective also the verification is quite different between codex and ethereum dash we are we have a snar based verification in the case of ethereum does we have an interactive sampling right and then the data sets are also different because in you know decentralized storage we are working with files of different sizes and in the case of ethereum does is that fixed block size that is a regularly coming every 12 seconds so those are the differences that basically uh between the two teams but I just wanted to mention that all the other tools that I have mentioned here which is a ratio calling resolution encoding data sample sub-linear sampling and so on and so forth are the exact same of tools that we have been working on developing

codecs and this is why this collaboration between the ethereum foundation and US made sense so just to conclude um basically we have been exploring multiple designs for data availability sampling uh in in ethereum we are building an open source Das simulator that you can all play with if you want and we have been also measuring the trillion network with the crawler that we have at Mega labs and for long-term storage we are building codecs so with that said I think um that's it thank you very much for your attention wonderful thank you very much so you know though um yeah fantastic work uh I think we've got a time for like one or two questions if anyone's got any

anyone like to ask a question um oh we've got one hey fantastic presentation thank you I'm just curious like what would be a call to action from you for the community I think a lot of people feel that ethereum isn't as scalable as they want it to be and they're sitting around trying to figure out like what can I do to make ethereum more scalable in terms of like data availability sampling how do you think that they could apply their interest and work to furthering along the research and development of that oh nice very interesting question um I think I mean of course first of all if anybody has experience in simulating part-to-peer networks please please come and talk to us because we are looking

for engineers and and people interested in working on these challenges so that's that's the first thing I would say and also for our simulator we are we need you know a lot of data in order to make sure that the simulations that we do are realistic and so in that sense we need a lot of data we are gathering data about the size of the network the number of nodes and so on but there are other things that we don't know for example we have you know uh staking pools are you know very protective sometimes with the data we don't know how many validators are running a node uh what type of nodes they use how much bandwidth they allocate for this and all this information could help us uh uh you know make the simulations more realistic and yeah I think lastly uh what will be

interesting is you know people uh being interested on these things reading about it and also communicating to other people's writing blog posts explaining in videos what is data availability sampling so that the community can also be more involved in this research project wonderful thank you very much trying to Applause again Leonardo seconds [Music]