Danksharding / Dankrad Feist

Transcript

foreign [Music] thank you yeah um yeah so thanks for the introduction I will give a quick uh overview of uh over what's now called dank sharding which is a construction that I introduced at the end of last year and yeah like I hope at the end of the presentation you have some more idea on how it works

so um I'll quickly um oh yeah I'll go come over here I will quickly talk about data shots or data sharding I will explain how data availability sampling using KCT commitment Works what the 2D kcg schemas will go into proposal Builder separation which is one of the building blocks that we need and then I will go to the come to the construction um so data charts are a way to provide data availability for Roll-Ups as well as other data

scanning Solutions so um what you might have seen that um uh originally um like several years ago when we first started talking about charting we I thought that what we're going to construct or what we need to construct is execution charting which is we distribute the ethereum execution across many different charts and and in this way we can we can scale the ethereum blockchain to execute much much more but then over time it has emerged that there are other ways to scale blockchains and one of them a so-called Roll-Ups so roll ups are

those construction where instead of executing all your transactions on the on the base ethereum execution layer you only post all the data or the transaction data and you have another means that ensures that the execution is correct so that the new State Route is correct and that can be done by different means either by providing a complete proof as a so-called zero knowledge proof that the execution was correct or you can use optimistic rollups which do that via fraud proofs and um so um at some point it basically became clear that Roll-Ups are actually a much more efficient means of providing

execution because they do not burden the consensus notes um with with all those loads that comes to execution they only need to for example resolve the conflicts in an optimistic roll ups and so they are much more efficient and at some point it it emerged that probably even if we did all these execution shots ultimately people would just use them to post roll up data on them um and so uh that's why in roundabout late 2019 our roadmap pivoted and we said well our main goal now is to provide a large amount of data availability um and uh yeah I've got some numbers here so the the goal is to provide about 1.3 megabytes of data availability per second on lithium blockchain which is

about 10x the current maximum capacity so if you have blocks completely filled with data but actually about 200x the the typical capacity that we have on ethereum now the the block of um creating data shards is data available to sampling so fundamentally we want to scale and scaling means we need to be able to to create more so data availability in this case than a single node can process like somehow we need to break this bottleneck that every single node has to process all the blockchain and instead we we have to

know that say of end data is available using just a constant amount of work and so the basic idea is that we distribute this data into n chunks and each node just downloads K randomly selected chunks so that's shown in this picture and the problem if you do do that naively is well one of the one one of the chunks that you aren't sampling is missing like basically then this client just doesn't detect it right so like there's this one single chunk of data missing and the probability that it is among the ones that you sample is just very small and so this doesn't work for blockchains

like for some other for some other constructions this might actually be okay but because of the way that we we work with blockchains for this for example Financial applications even like a single bit of data missing could mean that someone is printing a billion ether in that in that chunk and you can't detect it because it's missing so that that doesn't work um so what we need is we need a way to amplify this we need a way to uh to encode the data so that data availability sampling actually works and so the way we do that um is we take our data and we encode it with Erasure codes and we use our

so-called read Solomon codes which is a fancy name for polynomial interpolation and so the way it works is you have some original data in this case it's for I yeah Drew four chunks of data and and you extend it so you put a volume of degree three through that there's only always a premium of degree three going through exactly four points and and you evaluate that polynomial at four more points and because of this fundamental property that that any Four Points Define a polynomial of degree three it now means that any of any four of these eight points allow me to reconstruct the full polynomial and so we say the coding

rate in this case would be 0.5 because the the unit is 50 to reconstruct the data and this means that the data availability sampling becomes efficient because now a small number of queries can ensure that a large amount of data is fully available so let's say for example someone wants to construct a block and they want to hide the data behind it they have to hide at least 50 of the data why if they hide less than 50 percent so if they make four of them available then someone can just find those for and reconstruct all the data so they haven't hidden anything they haven't succeeded but if they make more than 50 available then

it's very unlikely if you make enough queries that all of your queries are going to be available so that that's basically the trick so for example if you make 30 queries then it's 2 to the minus 30 which is one in a billion which is a very small probability and the one tricky thing here is that what we still need to do is somehow ensure that this coding is correct so the one thing that we basically skipped over here is we we have this um these eight blocks but what if someone just puts random data in there like they just aren't actually on this polynomial of degree three it's um

it's just random data and then everyone could download 50 of it but if they try to reconstruct it they would all arrive at different data so that doesn't work and this is where kcg commitments come in so um kcg commitments are a type of polynomial commitment scheme and what is cool about it is basically because it's a polynomial commitment scheme it always commits to a polynomial so um you probably are familiar with Merkel Roots so they are a way of committing to any amount of data using a Merkel tree but the problem with that is it can be any data so you have no assurances of

what's actually in the data in particular you can't be sure that it encodes a low degree polynomial as we want but if we use kcg commitments then that's all automatically guaranteed by the commitment so basically you can think of this kcg rep root as something similar to a merkelroot but it always commits to a polynomial in other words it almost guarantees that our encoding is correct um and the way we use it is um we we introduce in addition um what we do is we introduce a a two-dimensional kcg scheme and so the

way it works is we will have many rows of data each commitment commits to one row but further we also extend um it in the columns and the property of the scheme is that each row and each column will on its on themselves be a code so they they will each uh be a polynomial and in other words um they they each have this read Solomon called property if you know 50 of it you can reconstruct the whole row or the whole column and the the reason we do this is uh why couldn't we just encode everything into

the into one big kcg commitment well the problem is then that you need a super node if you want to reconstruct let's say we detect um like oh yeah like we have enough samples there's like 60 available but some of them are missing we need to get all of them right ultimately we want to make sure that all of them are available so now someone needs to get all of them and that could be a large amount of work uh but we want to avoid this assumption that there's someone like super powerful who can download all this data to reconstruct it and so that's why we have this 2D scheme because what we can do then is that we just assign different validators to different rows and columns

and uh and they can basically reconstruct the single rows and columns and where they intersect they they can distribute like from a row to a column or from a column to a row and what this means is that um that if the data is incomplete then we can in a completely distributed way reconstruct this data and and the data availability sampling basically works the same as as for a for a single kcg commitment with um with a small change that if you if you look at it you basically you you need 75 of the square in order to be

sure that you reconstruct so basically uh yeah so the the data the um the number of checks you need to do to make is a little bit higher due to this property it's not 50 but 75 percent and it means that you need 75 checks well I mean the 75 is just a random accident that it becomes 75 don't don't think that's because it's 75 and so this means that um what's really cool about this like the total bandwidth to ensure that all this data is available um so that's uh 32 megabytes um per block um or 1.3 megabytes per second is only about

um 2.5 kilobytes per second so in the future basically full nodes are able to ensure that all this data are available um using only this really small amount of bandwidth um the final building block um that I want to mention in order to to construct this dank shot in construction is proposal Builder separation so propose I build a separation is an idea that comes from the Mev world and it's invented uh to fight the centralization um tendencies that come from Mev and um uh the the problem with Mev is that we expect that sophisticated actors can

extract more Mev than um say at home validators who are only have access to open source algorithms for example so that would create an advantage for big mining or validating pools and so the idea of PBS proposal the separation is that we contain the centralization tendency inside a special role so we um we we let the validators be proposed us as they are now but we add a new row which are the builders and basically validate us role for new blocks becomes to just select a builder according to an auction system and this means that for the proposers we

as before we always need an honest majority assumption and so we have high decentralization requirements but for Builders we can live with a lower decentralization requirement because we only need an honest minority assumption um the anonymous minority assumption in this case it means that what we want is that there's one honest and so non-censoring Builder which doesn't mean that we only need one Builder we need several Builders to ensure that but the requirement is much lower than than for the validating system right and basically the idea of tank sharding is this is to to use this poser

Builder separation so uh quickly to come back to the 2D scheme one thing we haven't yet talked about is that um we we found this way of uh of reconstructing it very efficiently by doing that in rows and columns but someone still needs to uh to compute um this this full encoding so we still still need someone to do that initially but basically we only want to rely on them for liveness and not for safety and so thanks to this proposal Builder separation we can say like oh we we say like uh we we externalize this role into the Builder so they are responsible for creating this encoding and distributing

all these samples and proposers are just responsible for select for selecting a builder through an auction foreign how the construction works so what we have is like um there's a proposal block uh which is sent by a validator and they select a builder and uh the Builder um will will build this full encoding uh with all the sharded data and the beacon block that will also after the merge include the execution block um and uh and then the the committee votes as as before they vote for this aggregate of this construction and then the next block is again this dual block

um so in summary we're using the 2D kcg scheme which allows us to uh construct a 2d Constructor for free data availability scheme with high throughput and all the safety properties so sampling of correct encoding and reconstruction which ultimately is the necessity for convergence so that ultimately all consensus nodes come to the same conclusion they are fully guaranteed without any super nodes because so we don't have any requirements for a powerful actor in The peer-to-peer Network in order to to ensure these and only the encoding and distribution of samples requires this Builder

and thanks to PBS however we can ensure that ordinary validators are not required to to fulfill these requirements and so for liveness we have a new honest minority assumption that's dependent on this uh this Builder and one one of the implications is that what we are still currently doing active research on is uh to to improve the censorship resistance properties of this so there's great research done by Francesco in the research team on like building this um yeah cr-list techniques that allow ordinary validators to impose certain restrictions on Builders so that they have to include honest transactions

and that is the construction so I conclude my presentation here and I'm open for any questions okay there's a microphone in the audience if anyone put their hand up we'll get you the microphone ah right at the very back um just a quick question on the proposer can can the in your scheme can the proposer decline to um take the auctioned block from the

Builder and just still make his own block yeah so yes that's possible yeah what's likely is that the proposal so the proposal you can also just submit your own bits so that this is always a possibility there's no restriction on that um so yeah for sure you can always construct your own blocks it's just likely that you will extract less Mev and um it's also if you don't have the ability to construct say large data blocks then you can construct a smaller block and just use that for example so that possibility exists yeah so why do we need proto-dang shodding

um so so Proto dank sharding is a is a simplification of this um well basically protodank charting is not a scalable construction it's a it's a way to um to introduce some amount of extra data availability on top of the currently existing system um to really to relieve the pressure um a bit um that basically uses the same building blocks so that the upgrade later will be smoother and we need it because we're we'll need more time to fully develop the Full sharding Construction until then okay another question from here yep uh yeah uh yeah okay so

[Music] so for about the amount of data basically we store okay we spread it across validators across different nodes across different shards but but then we also increase the amount of data dramatically like it's like two times for polynomial and then four more times so it's like eight eight more times basically eight more times the amount of data like the original data so won't it be kind of four four times yes so yeah the encoding has an overhead of a factor of four yeah that's correct yes [Music] um we really increase the amount of data like we're going to stores right we will

really benefit from it like uh like taking this in account yeah I mean we we benefit from it and that not ever node needs to store the full amount of data um so that that is the trade-off yes so if you require every node to just store all the data then you don't have this overhead but then instead you have the problem that now you have you require um very large notes so it's a trade-off yes yeah I think there was a question over here somewhere I saw a hand over here okay thank you for a talk just to uh start

spreading some fud um can you can you tell so there is a trusted setup needed for kcg commitments uh and the receiving project working on the ceremony client implementation here on the hackathon so if you could say more about that uh yeah so the the kcg um uh commitment scheme is based on elliptic curves and it requires a trusted setup so that's similar to how many zeroid proof systems work like you've probably seen like um zcash has done one in the past but also many ethereum protocol projects have done things like that and the way it works is that it will require um many people to participate and it

gives this guarantee that if at least one of these participants was honest and honest means that they contributed and afterwards they destroyed the randomness that they used they didn't keep it or publish it or anything then the whole thing will be completely safe so if at least one honest participant was in a ceremony which I think like if you manage to get to sample or somehow get like thousands of people from the ethereum community I think it's a very safe assumption that I'm very comfortable with um but yes it is an additional assumption and we are currently working on making this as safe as possible okay uh the opposite corner of the room maybe if you kept this mic active as

well I can run to other people uh so the question is this sampling technique it checks chunks availability at the moment of block production but what about the chunks storage long-term storage um so what's the plan here um okay well long term can mean many different things um so there will be a plan to uh to have some amount of storage in the peer-to-peer Network so like we will we will require storing them for um some number of weeks what we do not what we do not want is to require nodes to store them forever so

basically after two or three months or something like that nodes will be able to forget all samples and the way you should think about the ethereum network in the future is think of it a bit like a a public notice board so you can publish something and it guarantees like this has been published and everyone who wanted to see it was able to see it but it's not an archive system and ultimately the only way you guarantee that data remains available is if it's interesting and and I think like basically we need to design our system so that it's not a crazy amount of data so that people who find it interesting will just not be able to store it but I

think like the way we design it is we keep that somewhat in check we still make it put it into the realm of of individual people to like store all of it if they really want to like you will have to buy a couple of hard disks every year probably but that's definitely possible and so I'm not worried about that data getting lost and I don't think we have to build incentives into it but but definitely we have to make sure that those actors can get the data if they want to here oh thank you yeah so uh very simple appointed question how does this affect uh and if in any way as stores and S loads and the relative gas costs

oh it doesn't have anything to do that with that because the estrogance s store load are about State and the state this data is about data availability so this is a different kind of data that we're talking about so on the on the base layer I like on the L1 this will not affect storage costs or anything like that it what is the difference that will enable layer tools that can have their own pricing and have very different pricings for these operations cool thanks thanks and cool that it's named after you um I just wanted to ask

um if in the process of building this if you learned anything from like these other data availability projects like Celestia or maybe even filecoin I don't know okay so firecon is not a data availability project um but yes I mean Celestia is a very um very cool project and like we are we are talking to them regularly as well um Mustafa also like developed this the the basic idea um with with vitalik several years ago um uh yeah I mean I think like um they they are clearly doing something very similar there are some differences in our exact approaches so one of the major differences at least at the moment

is that um they they do not enable this distributed reconstruction that that we are very keen on having so they they will require also for safety to have this um this powerful actor assumption um I think it's a it's an interesting trade-off and it's great to to see them rolling out something hopefully a bit sooner than we will be able to and so we will get first experiences about the whole data availability sampling foreign does this mean that the centralized uh staking services will earn most of the Mev until sharding is live or is there

potential for the proposer Builder separation to happen before sharding um so yes so there's the there's currently a project which you might heard of it which is called math boost by flashbust so they're developing a software where they Implement a form of PBS that does not not built into the protocol but with somewhat stronger assumptions on the honesty of of the um of the builders like you can still build something and I think it will hopefully be ready for the merch yes so even individual valid datas can profit from Mev at that point okay and I'm afraid time is up thank you very much Dan Fred for coming

to talk to us about this foreign