leanDA and da.fast

Transcript

Yeah. So the the the first construction uh that we attempted was essentially just to use fry inside a circuit. So um we have our code word provided as private witness. Um we compute the root of the code words um and then use that route essentially as um our randomness to construct a random linear combination of the code words. We then have one aggregated code word and we essentially fold um until we have a small enough um code and we can assert that uh you know it kind of match it it uh satisfies a relation of a valid code word. So this worked. Um we got

around 364 kilobytes per second of throughput. Um and uh yeah kind of triggered exploration in the direction of um you know verifying uh correct in encodings inside circuits. So the second uh construction we attempted was um instead of doing fry and doing folding inside the circuits we would use um the barcentric um parity identity. So uh once again we compute some randomness using commitments to the code words um and then uh essentially use this barry centric um parity uh parity identity to uh verify that the

code words were correctly encoded. So this was um also pretty pretty good. We made um we made around a 3x improvement on the on the initial fry base construction um and got to around one 1 megaby per second. Um this is measured on a MacBook M2. Um but yeah, just to note that these numbers are using Poseidon which have subsequently been you know it's been deprecated. Um but I believe the numbers do translate reasonably well um to uh binary fields as well and um yeah the conventional hash functions we've been

using there. Um so this is the third construction we explored. Um it's very similar in terms of the uh the code word verification. We use the same um barry centric uh parity identity to to verify that code words are correctly encoded. Um but the commitment scheme changes slightly. So each row is essentially a blob and we split the um we split each blob into cells. So um in in this case we've got five cells and each of them uh sorry six cells and each of them you know contain a number of uh a number of

chunks. Um so yeah we we we hash um you know the code words into cells and then for each specific blob um we can uh we do a sequential hash over the cells and that gives us a commitment to the systematic cells of each blob. Um this was chosen because in most cases um consumers of these blobs say L2s um you know are are primarily interested in the systematic data. So um you know we try to make that as efficient as possible.

Um and it yeah that's kind of how we've approached it. Um then we uh merkelize the commitments of the systematic cells of each code word into a Merkel tree. So you have efficient um kind of authentication paths for each code word against the Merkel root. Um and then uh on the column axis because Ethereum uses columns um to uh in in its DS construction the data availability construction. So we also merkealize over columns. Now I'm not sure if this is absolutely necessary. we may be able to

deprecate the the the column commitment but nonetheless in this construction we did include it. Um and then uh once we've got the you know the Merkel route for each column we then subsequently merkelize those um column Merkel roots and we combine um both the the the column and row Merkel roots into a single um you know final Merkel route. So, in terms of performance, um, back then this gave 1.1 megabytes per second. Um, but I've been told by Emil, I'm not sure. Yeah. Oh, yeah. Been told by Emil that we're getting around 2 megabytes per second if I'm not mistaken. Is that

on an M4 or >> M M4 Max? Okay. So, reasonably good performance on uh on consumer hardware. Um so yeah this is just a visualization of the construction. Um basically what I said but just uh yeah kind of visualized a little differently. Um one further exploration was lean air which is um essentially like the same construction uh this this exact construction using the um the the the parity identity to verify the uh the code words but instead

of using a virtual machine um we go for the circuit based approach. So we had a single circuit which in this case was Poseidon. Um and uh we essentially just you know just use hash permutations to verify that the hashing is done correctly. And then we have um virtual relations between inputs and outputs and you know the various different rows to enforce the the the kind of wiring um across the the the commitment scheme that we see here.

And um we also encode the the the parity check as um yeah like a as as a sum check construction essentially. Um so this uh I mean it's not it's not a fair comparison because um I ran this uh ran this experiment on a on a graviton. So, you know, arguably um more CPU than uh than the the M4, but we were able to get up to 7.5 um megabytes per second for a single proof. And uh we're able to run, I believe it was free proofs, a batch of

free proofs um which totaled out at around 25 megabytes per second. um still unsure in terms of which direction to take. Um also there's potential that you know this commitment scheme will will change somewhat but I think we've um you know broadly proved that uh it is viable to um to do uh you know DA um DA commitments in a in a uh ZKVM. So that brings us to DA.fast.

Um so the general idea is to run an auto research challenge uh to find you know uh an efficient scheme for Ethereum's data availability. Uh there's the paper foundations of data availability sampling from uh Benedict and and co um and that kind of specifies the the core properties that we um you know that we're interested in in a construction for Ethereum. And there's also this lean formalization which could serve as kind of the baseline for um the evaluation loop of uh a future auto research challenge. um still unsure at

what level of kind of abstraction and flexibility we'll will uh we'll host it um and also uncertain of the target. Uh there's a lot of work taking place with lean VM. So um you know we'll potentially use lean VM or we may also have a a parallel challenge uh for um you know kind of defining construction directly over circuits. Uh let's see. So that's touching on kind of the cryptography side of things. Um but I think it would be good also to discuss the future of blobs in the con uh in the context of the broader Ethereum protocol

and some of the plans that we have. So um the first of which is blocking blobs. So we have execution proofs which are um you know they've been integrated into some consensus layer clients and we've run devets uh and you know it's working relatively well but um this gives us the opportunity where in which we no longer need the execution payload to verify um the correctness of a payload. So um ultimately we'd like to reduce would like to leverage that that uh you know potential um such that we don't have to download the payload but ultimately we

we still want to prevent against data withholding attacks. So the idea is that we will take the payload um or take the payload body and we will encode it into blobs and then you know uh validators on the network will sample the blobs and that's how we address the the availability problem. Uh so this brings us to the question of to blob or not to blob. Um so as I mentioned we put payloads into blobs. So the question becomes does it still make sense for us to have um separate blob transactions or should we just have users put data directly into call data as um you know they once did before. Uh

I was unsure of this um and I still am to be honest, but I'm leaning in the d direction of no, we should not because um if we force users to put their blob data or or you know kind of all of their data into call data that uh ultimately increases the size the the size of payloads, right? we we we need all of the blob d all of the call data to be able to compute the transactions route the the transactions route. So for any um pier that is re-executing it ultimately uh kind of bloat the size of the payloads that they have to retrieve and you know ultimately the bandwidth on the network um for data

that isn't isn't relevant or isn't actually leveraged in the execution environment. So um my I'm leaning in the direction that we should still keep blobs. We should not uh you know just kind of unify everything into core data but we should um unify pricing. Uh you know ultimately blobs and core data are going to be consuming the same resource on the network. Um so they should be uh priced um you know equally. Next is the problem of blob packing. Um so currently blobs are a fixed size. Um and this is somewhat problematic for uh

you know users on the network L2s etc. where um you know they they they often would like to be able to post data to Ethereum at low latency but it may not be economically sensible to do so due to the fact that you know they can't they can't saturate a blob. So um there was one proposal in which uh the idea was to defer um blob construction to the builder. Um so the builder would would receive uh kind of blob data. They would do the erasure encoding and then um you know that would subsequently be uh kind of distributed to the network. The problem with this is um you ultimately

put uh it's you you um you increase the bandwidth requirements on the hot path because uh you know you wait until the builder has constructed all of the blobs before you can disseminate them. So we kind of lose all the nice um optimizations around the sparse blob pool and ahead of time um dissemination that we we we we currently have or I believe um the sparse blob pool is landing in uh Gar. Um the alternative solution uh that I believe should be viable I haven't um this still needs some thought. It's a is an it's a new idea, but um the the the proposal is that instead we allow for um

cells to commit to an arbitrary amount of data. So if we go back to this construction here, if we look at um if we look at uh free um we can essentially allow users to kind of pack arbitrary amount of data into each of the cells and ultimately they all produce just a single digest. So you would still have 128 cell digests um yeah cells uh per blob but those um cells would be uh yeah differently sized.

This also brings us to the question of pricing um because there is a fixed overhead with the merkealization of um of these cells. So uh the proposal would be that users would pay for you know some fixed overhead um for for for the merkealization and then there would be a uh a um cost per bite essentially. So depending on on how much uh how many bytes each cell encodes um that would scale the the the cost of the blob.

Um so yeah then there's the question of blob proving. So do we um do we uh I mean as as I mentioned previously one of the proposals was to defer construction of blobs to the to the block builder. The alternative proposal is that um you know we kind of leverage the blob pool as much as we can to um do this ahead of time dissemination. And one of the ideas in that direction is essentially to have each user who submits a um a a blob transaction to also provide a zero knowledge proof of

the um you know the validity of the of the of the blob data or the validity of the encoding of the blob data. I suspect that this fits relatively nicely with 8288 which is um you know kind of introducing the the the possibility for users to to submit zero knowledge proofs. So it could be the case that um you know we can kind of piggy back on top of that construction um to uh yeah to kind of still enable this ahead of time dissemination.

Um and yeah, it it's it's it's uh PQ compliant essentially. So that's the idea. Many of these um questions are still open. Um so these are just some ideas. Um yeah, this one's far more speculative but also pretty interesting. Um so the the the concept is essentially can we um somehow leverage uh DA to kind of address or partly support the um state issue that we have um currently. So the idea would be that we could introduce a

um a sharded uh a sharded custody policy for for state. So each peer on the network would essentially be um assigned to a shard or you know some subset of shards. Uh we then enhance bowels. So boughs have most of the information we need um but not all of it. So I believe there's uh there'll be kind of boundaries uh between the shards at which um we'll need to add uh some some Merkel m yeah Merkel material to allow um to allow peers in combination with the boughels and the Merkel information to kind of update the the the kind of subset of their Merkel tree of the or

their shard of the Merkel tree um for each block. And because we'll also be putting bows into um into blobs um we can leverage the arasure encoding for the availability of the blobs. Um so that ensures that the state updates are um you know always available to peers on the network which allows them to update their state. Um and yeah the state requirements uh per node uh are reduced. So um in terms of how this could work, as I said, this is uh just an idea, but um each pier could store the finalized version of their uh their shard plus um

you know, kind of the head overlay or a number of head overlays for the various different forks. And then as you know, the the the finalized head updates, you would essentially just um kind of commit the overlay, so to speak. Um, and this may also allow us to address the issue with mele maintenance in the kind of stateless or semi-stateless paradigm because if a peer on the network needed some state to uh validate a transaction in the tra transaction pool um they could potentially request it from um from from peers in their network um and and subsequently update

it using bowels. >> Yep. >> Um I'm trying to understand exactly how it would work for state just because it's notoriously very hard to um prove that you hold state and >> prove that you will serve state unless you literally ask uh for for a request. But like then it's it's very wasteful obviously because you need to have all these sort of like dummy requests I guess. So just to check that nodes actually hold the state uh they are saying they hold or that they are supposed to hold I guess and we've been really struggling with this issue. I

think you know even chains like filecoin and everything has tried and it was not working super well. So yeah I'm wondering how you are thinking about this. >> Yes that's a good question. So um like proof of replication and and proof of serving is definitely uh you know a challenging one. Um one idea would be to have the validators um as they're they're signing their consensus attestations somehow encode the Merkel authentication path um with the attestation. Um I with zero knowledge proofs that would certainly be uh possible but you know that if if we had

one ZK proof per attestation the bandwidth is just going to explode. So I'm not sure if there's like some clever stuff that we can do with Sphinx or XMSS to kind of embed um this witness material into the signature itself. Um I'm unsure. So that that's a yeah it's an open question basically. Uh and I don't have the answer right now. >> Cool. And then I think the other hard question um it sorry uh it's um you can maybe let's say we come up with like a super smart scheme that allows us to make sure they can prove that they hold

state. Um that doesn't mean they will serve it. Um and so you have this sort of like incentive trick uh because imagine you want to reward people for holding state. Um then you will know that we they will actually serve it when you asked them for that particular piece of state and then yeah so it's a whole mess like it's it's actually very tricky to to ensure people are doing what they are supposed to. >> Yeah I agree I agree. I mean, I don't have the answers for it now. I guess ju just to kind of engage the conversation, how would you um see this different from say serving history now?

>> Like what what what are the current incentives in the protocol for um you know for peers to to serve history? Um none but the big difference is that history is static uh and state is all in interdependent and dynamic. Um >> when you say interdependent what do you mean by that? Sorry. >> You know like when you are touching some parts of state you need other parts of state um that are connected to it to make proofs uh about it.

>> Right? Um and you know even if you're not doing anything for example on your balance or something uh but uh you have USDT and the USDT contract is actually like changing a lot uh then if you want to sort of like know about the state uh of your USDT uh you need to also hold the state of the USDT contract which is huge. So you have all these sort of like inter interdependencies which are very different from this sort of like static history that is not going to move right and that is there. Um and so yeah I think that's the biggest difference in terms of incentives.

I mean there are not incentives right now for history but I'm I'm just a bit less concerned about history because of those properties. >> Yeah. I guess um maybe a more accurate analogy would be blobs, right? >> Yeah. >> Um so like >> we do inherently have the assumption that peers are kind of behaving honestly and they will serve their their blob data. Um if we put payloads into blobs blocking blobs um we kind of enshrine that uh kind of assumption for blocks. Um, so if it's good enough for blocks, maybe it's good enough for state. I'm not sure.

>> I would argue blobs in terms of the the data properties are closer to history than to state. >> Well, I mean, if you don't have if you don't have a block, you can't produce the new state. Um, so you've got the >> pardon. >> You can you can update your state with the bells. >> Well, that the bows will go in the blobs as well, >> right? But you can just like download parts of the blobs that keep your like allow you to update your your state. >> Um yeah, but the the the point is that um we're trusting the uh we're trusting the the the blob dissemination construct to make that uh bowel or payload available to

the network. So like if if if blocking blobs go ahead um that is ultimately the the assumption we're working under that uh you know we believe that you will be able to you you're not the the network is not vulnerable to data withholding because of the fact we've got um you know attestations from the from from validators on the network that the you know the appropriate data has been made available. Um but I I do I do see the you know the concern and I I wouldn't say it's a onetoone kind of anal uh analogy. Um >> I think that's a good analogy. Maybe the difference is like that you we're talking either about like a critical sort of like you know data part like the

val that like every validator sort of like relies upon to update its state and whatever versus like I don't know I feel like with state like we in a partial stateless world where like you can earn your all your rewards by just like verifying proofs and you don't don't actually need to hold any state >> um a lot of validators might just drop it uh and And how do we ensure the state is still like available uh for everyone and that we and we like truly be served is a big issue. >> I agree. I agree like the I guess the the the lazy validator problem is um present even outside of you know this context like even now arguably you could just wait for like a super majority to

form and then you know throw your attestation in. Um >> yeah, the diff I think is that if you have a ton of state, um then the costs start like weighing on you and >> like unlike today like basically people probably just do it because it's it's cheap um and it doesn't really cost them that much. But like if you have this sort of like growing state and you start being very constrained and you need to now buy hardware because to to accommodate it for example then you might be like hey maybe you know maybe I'll drop it because I won't lose anything anyways.

>> Yeah that's that's that's a you know that is a fair um a fair point and I I don't have the answer. Um I guess you know one argument is that if you shard state you're reducing by a factor of you know 32 or 16. So you make it more feasible for uh you know for four peers to maintain it. Um but that's not necessarily it may not be a strong enough property for us to have confidence that you know we can we can rely on this mechanism. Um it's just an idea.

>> Yeah. Yeah. Cool. >> Okay. Uh just uh one concern I think also worth addressing is that well this uh with linda uh we basically have now lin proves and um uh well the way it will look like basically we have the postpbs we have the bits and each bit would need to kind of contain this linear proof and these proofs they kind of creates a lot of bandwidth and would be great if we could for example uh maybe defer somehow the sending of the proofs um as you described like we basically have two parts of the scheme.

We have Merkel proof construction which is cheap and then we have LINVM uh proving which is kind of a bit slower and the proofs are large. So just something to keep in mind. I think that would be great if we for example the beat would would only contain the maybe the root part and then we have like maybe another uh message uh some kind of smart propagation of the proof part. Uh so that way basic and maybe even think about like sending this proof only when the builder can assure that his bid was accepted. That way we can really reduce the bandwidth in the network. Yeah. Just curious if you were thinking something about this or >> Yes. So um bandwidth overhead is certainly a concern. Um I guess 8288 is

interesting because you kind of um frontload the proof dissemination in some respects to the blog pool. Um, so it I mean if you were to push this to the limits, you could potentially even have validators attesting to the fact that they're custodying specific blobs ahead of time. So by the time it reaches the block builder, they could choose to only include um blobs which have already been attested to ahead of time. Um and as a consequence of that um you know there is no there is no dissemination of proofs on the hot path. Uh but in the current construction yes we need to

consider it for sure. Um maybe something like this this scheme for um fast payload dissemination would would would fit here. And I I I feel like uh you know PQDA is certainly sensitive to to kind of bandwidth and um dissemination efficiency, but there's going to be uh you know kind of PQ consensus stuff that is also going to be kind of sensitive. So yeah, you've got a lot of work on your hands, sir. Good.

>> Yep. >> Okay. >> Thanks, [applause]