Data Availability Sampling from the Networking Perspective / Csaba Kiraly

Transcript

foreign [Music] so yep sing subtle okay so my talk will be about the networking aspects of data availability assembling specific to the ethereum context this is a verdict that we jointly done by Lana is Leonardo and Dimitri who are my colleagues at status status you might know from the from the status app from keycard from the numbers client and we are in the Codex team which is working on the centralized storage Technologies

and this work is funded by an ethereum Foundation Grant so thanks to the Italian Foundation we can work on this so what is the theory of the sampling and why we need it uh as I said we are focusing on the ethereum context so data availability sampling is is a generic technique uh but in the Italian context it's really the key the new key to scale ethereum so the goal what we have here is really increase the block size beyond what a single node can handle without really making the notes heavy so without changing the requirements on the nodes themselves so the question we should pause ourselves is how can we go and increase the block size so that put

ourselves in a situation where nodes cannot download the block and yet have the the system working and thinking of this double sharding pretty long shading dunk sharding uh there are some underlying realizations uh I was listing here three one is that that is data which is sitting in data blobs which nodes do not have to enter the plate so if nodes do not have to interpret it they actually don't need to download it to interpret it they're really downloading it for something else consider downloading it and what they are downloading fall is really to know that the data is available that the NATO was released that is not withheld

so that's the only reason they are downloading so you can do something else and something else that you can do is sampling it's probabilistic sampling so the other realization is you don't have to go deterministic and download all the block you can do a probabilistic sampling a statistical test and based on that you can hope to be lucky enough to figure out if data was not actually released and as you know that the data is not available and you can disregard that block so we'll add to sampling and as I said we have a statistical test the data the block is segmented and the sampling plus is going on uh

picking a piece and or maybe more pieces of the many pieces and based on that deciding whether we believe the data is available or we don't believe the data is available so the first thing we do is segment and Sample so uh the data is in some State it's either available or not and you it's augmented and you're asking for one of these pieces and if there were case segments and you are asking for one of these case segments you have one over capes of ability that you figure out that it was not available if you're on the right side if you're on the left side and it's available you'll find you will always find it available and you can ask for more samples you can

ask for S samples or the many kpcs and you have this linearly growing probability of figuring out that it's not available if it's not available encoding which has the base property that if any K in this example fall of the pieces are available of the extended eight pieces then you can reconstruct the data so when it's all available it's fine uh

but what you see below is also repairable right so you have four pieces missing the red ones uh four pieces aldel tool which will generated policy data two of the original pieces so you can reconstrate the data so you can look at it as the data being still available this is an interesting part is when five pieces are missing and then the data is not available and in that case you have kind of one over two in this example a bit more probability but if there are many segments is one over two probability that you figured out that the data is not there this one little single sample and the nice thing is that if you have two samples you have clf all and if you have S samples you have one minus uh

uh one minus one over two to the K probability of figuring out so it's kind of managing probability with the number of samples if you have many segments that you figured out with a statistical test that the data is not available and we are happy with this no we are not because there is a problem uh there was a lead someone encoding uh we think but actually we don't know that those pieces which were Dell can be used to degenerate the original data they can be just random data we will sample it we'll find out the P that the piece is Dell a piece is still something is there and we believe that the data is dead

because our test is showing that but they cannot actually be used uh to reconstruct the data so in the example you see that actually that five piece is missing we just don't know we sample we get something we believe it and that's wrong so that's why we have to segment we have to extend the data then we have to prove each single piece and then we will sample so what's happening is that we are proving delete someone code and this is going with the kcg commitment so there's a commitment to the data each single sample proof has a single segment has a proof attached so if you have the commitment a single segment

and the ploof these together enable you to to verify that the sample is actually from coming from the correctly someone encoding so your mass is working again if you're sample and you get something you know it's it can be used to deconstruct so once your second Sigma segment extend proof and simple you are having something which can be used to guess whether the data is available or not now this would be very nice but this is not what is being planned in ethelium that's a slightly bit more convoluted it's just a nice little step so this is what it is so this is how

block encoding is planned in in the next evolution uh by the K that you see there the 64k is not uh the K that you've seen before this is kilo so this is 64 000 segments so the date block which is 32 megabytes is divided into 64 000 segments uh which is half a kilobyte per segment and then over this there is a lead someone encoding but it's not a normal it's only encoding it's a two-dimensional it's someone encoding uh which has a nice probability that if you have K pieces so it's in this case 256 pieces

of an of an individual low then you can reconstruct the law or if you have 256 pieces of any individual column then you can reconcile the column so it is extended to 256 000 segments each one being for half a kilobyte and we have 128 megabytes of data and this is kind of a new block that we are going to sample on and of course there are kcg commitments so you see the numbers there uh the uh 40 128 megabytes of data you have something

like I don't find it now uh yeah 12 megabytes of kcg commitments I did so you have this extended set of data of which the top left corner is the the original data and sampling is going over over this now let's have a little quiz so is data available if these segments are there the blue ones and the white segments are not Dell and you would say yes this is the original data this is data from which the extra data was generated so

obviously this is the palable and this is available and with those and columns you can repair it you can see I repeat it all you can repeat all of those from those you can repair all the columns and yes it's available let's take another example is this applicable or not and this doesn't seem that obvious right but if you see that you can repel.com for example you see that you can repair all those that's so you see that you can repair all those those and you can repair the columns and at the MDS that was appealable what about this one

maybe notice that in these going back a little bit only 25 percent of the data was available so what about this one well we have almost 75 percent of the extended block available sounds likely payable right but actually it is not it is not because you cannot zip it anything there is no law or column where you can start repairing in episode or column you either have all the column of the detail so you cannot separate it because it's already repaired or you have only three pieces so you can start preparing so this is a no right what about this one solar different seasonings here one is

we just simply don't have enough data to have it repayable it's less data than the original data it can be available you can extend it and you get back to the previous one and you see this is not available so we have this nice data structure and we understand how they pay living works on this and we understand how sampling into this could work but actually this is not done locally this is done over the network so let's see the networking perspective let's see what happens on the network actually so how we check data availability over

the network in the context of ethereum so notice that in the context of helium there are different nodes and they have different goals so validators and four nodes have different goals that they want to achieve from this extended set of data validators that goal is they should either generate many attestations if the the data was available or they should generate very few attestations if the data was not available and that's the the system level goal we don't like things in between for notes it's a bit different

they want to find out is a very high probability during the statistical sampling if the data is not available because if it's not available then it can be a block which maybe it was even validated but maybe that is some super majority malicious or maybe for other reasons uh it should not be accepted so if it figures out that it is not available then there might be database hold and depending on the use of this this data whether it's used for an optimistic develop but it's used for ZK level up there are different use cases but for each one of these if the data is visible

it can be a huge problem so we have to get the data From the Block Builder Builder two the validators and to the nodes in a way that they can satisfy this so it's actually a process which goes through many steps the individual places here so that is the the block is being created extended as I was showing then the work proposal or the Builder is disseminating the lows and the columns to the validators and the writers do the job of by dating or not and then there is another thing which is the data is pushed into a new term

structure a DHT from which then the nodes can sample and then this structure might also need repairing because nodes are leaving that is churn so there are all these processes going on behind the scene now today I will focus on on the dissemination of samples to the validators so I will not go into the DHT part and I will not go into the actual sampling of a ddht but let's see what happens between the block producer and validators so familiar does validators each validator is checking a number of

rows and columns ended by default we are speaking of two because it's an easy example it's available parameter at the moment so each validator is selecting randomly two rows and two columns and they are checking that and that's the check is it that or not that and just to give you a bit of dimensions of the problem so we have 500 000 plus y datas around eight thousand plus Beaker notes behind which these radiators are sitting uh you have those 260k uh segments which are sitting in one thousand twenty four thousand columns and we have something like four seconds to to do this so how do we do it uh the elephant proposal the base purpose other time speaking of now is to

use a gossip sub orecosystem like protocol I would say because I don't think it will be the gossip sub as of now reachable version so uh we use aggressive Supply protocol and we knew a number of topics in Gossip sub so if you no gossips up you know what it means if you don't know gossip sub is building uh mesh Network like you see there those are Beacon notes behind which you have validators which are interested in the 2016 third column and they form a small mesh Network with a given degree in which they are sending the column so that everyone has it and you have 1024 of these networks

built [Applause] and will I go so sub and we like gossips are like but of course uh because they are robust uh they have defensive liability mechanisms so one is uh that they are building this mesh to push they are sending gossip messages so that nodes can pull information and they have also using reliable thumbs but they are using TCP those hip supports has downsides uh they send lots of duplicates and uh they are not yet ready for the large messages but you've seen we are not just using those ships up here we have two more Technologies here like you have the Azure coding and we have this 2D structures so we are adding two more layers of reliability

we have the lead Solomon chord which we can use as for the collection code from Communications if you know that so basically if you have half the low if you received it you are node you receive the half which I will have number of segments you can repel it and the topics alcos connected so if you receive something on the rule you have it on the column so we can use these two techniques as well so we have five reliability mechanisms uh there with which we can play to have a system which works well so what we did is uh Simulator for this uh it's a it's in Python which is nicely accessible we hope for for others it's

very much working progress and or everything I'm sure here is is prediminally so don't take the exact numbers and we do many simplifying assumptions from the networking perspective uh we don't care about TCP slow start we have 100 milliseconds relative time at the moment and this is what you see on the light side is one single dissemination with a builder which has one uh 1000 megabits per second link this is a conservative estimate but we are not counting with some factors we have 5400 nodes which are kind of solo stickers one validator these are smaller

bandwidths and we have 1600 nodes which are having their Beacon notes handling a bunch of validators and having a better network connectivity and what you see on the right side is is kind of the progress the evolution so on the top uh below the time so we are arriving to one second and in one second notes are receiving samples uh and validators start to validate what is this validate when they have all the rows and columns and then you also see a bunch of network statistics what is the transmission bandwidth the reception Bandits and how many duplicates you have uh now how we use this let's see one example uh this is about massive size so

I thought said we are sending those and columns but you can do it in many ways so on the left side what you have is sending using gossip sub with messages being close and messages being columns so message is 280 kilobytes this is the big message case and what you see there is that to validate so that for the green curve to go up we need something like 1.6 1.7 seconds on the right side we are using small segments so uh so small messages so every segment of those 260 000 is a message and then we are much faster another example of the simulator is

checking boundary conditions so uh what you see on the top is something which we know we know is available and available uh what you see at the bottom is something which we know is not repeatable and thus should be not available should not be validated uh what you see on the right side is validators basically all of them uh validating what's on the left what's on top in a second and something uh on the below what you see is that validation plug this is stuck at a low percentage obviously no one has more than on more than 75 percent of the chunks of these segments and this is what we wanted to achieve so

we have the simulator now as I said it's quite working plugless we are using it to kind of figure out the light combinations figure out what gossips are like means so we are experimenting with uh with different variations uh we will improve the simulation Fidelity we will do parameter space exploration because I've shown you a single lungs so they are defined in the statistical element uh exploring attacks and then dealing with the the other parts of the dissemination to ddhd end of the sampling so thank you you've got any questions [Applause]

thank you xava super interesting again very in-depth any in-depth questions from the audience over here so I wonder if what the blocks that are meant to be available for the for the period that this is under consensus are constantly sampled by the by the validators why they are constant examples if if if block availability should be like you know two weeks then all the two weeks worth of blocks are constantly each of them are sampled by from the DHT

by by notes by notes are constantly sampling it are doing the verification because they they don't validate if uh if they don't uh if they don't see it available the the notes are doing it uh because they should be they also want to be protected against the case when the validators themselves have a super majority of malicious misbehaving notes so it's it's kind of a case where they just don't believe everything to do validators okay another question from the audience no going once

go in twice 2.5 2.75 2.8 okay very good thanks again thank you we have just [Music]