Rethinking PeerDAS: Transparent, Post-Quantum DAS with FRI

Transcript

Okay, hello everyone. Uh thank you for being here on this very last talk of SCC this year. Um so I'm Stefano. I'm researcher at Nethermind. Um I'm presenting today a a topic that I really like to talk about even these days after recent announcements from Google. Uh it is about how we can rethink peer DAS on Ethereum using a a new schema polynomial commitment scheme that is post-quantum secure.

Okay, so I will start with a very high-level intro of why we need DA on Ethereum. So with the um scalability roadmap of Ethereum, we introduced this concept of rollups and these rollups uh are using data that was posted on on blobs. Um why on blobs? Because you we introduced this new uh transaction type to don't overload Ethereum blocks. And uh yeah, so blobs are not stored in in the main blocks, right? So they are stored as a sidecar and distributed over the network. And in the very first uh implementation, we had blobs distributed entirely to all the validators that were checking the blobs. And to introduce a

kind of commitment to this data that were distributed uh around the network, we used KZG commitments. Uh these commitments gives us some very nice properties of binding with the data. So it was uh interesting on the next level how to verify this data. And we will see this in a minute. The problem with KZG is that is not post-quantum secure. So so what's next? Quick agenda for this meeting. Uh first of all, I will uh give an overview of what we have today with peer DAS.

And what's the problem with uh post-quantum security Uh uh with KZG? Um and introduce a new scheme, a new polynomial commitment scheme that is used called FRI, and this has a suitable polynomial commitment scheme for post-quantum security. It introduced some overheads and some complexity, so we present here a solution to mitigate this complexity. Uh we conclude with observations and the trust assumptions of our our approach and the next steps. Okay so with Peer DAS, we introduced this cool concept of data availability sampling.

With data availability sampling, we allow validators not to download the full blobs, but just some chunks of the of the blobs. And very high-level how it works, we take the blobs, we put the blobs in a matrix from the proposer side, the proposer encode the blocks the blobs with an erasure code extending the blob for some uh repetition and and then distribute columns of uh of this erasure coded data to validators.

We recall that we have in the blocks the commitment to we can commit using KZG to these blobs, and we include the commitments in the block, so the block remains light and we can distribute it over the network. While from the validator perspective, we just download some chunks of this data and and receive also as a tiny proof, which is constant size, that we can use to verify the validity of the chunk. And this is called the KZG proof. So, both the KZG commitment and KZG proof are constant size, which is quite cool, right? Because we receive this proof, and what we can do, we can verify that the encoding was done correctly. So, we achieve these properties of encoding validity.

Sorry. Um Right, so and this is a cool property that comes with KZG. Another property that the peer does gives us is data availability, right? So, if we have many validators that sample, then eventually we we expect that from the majority of validator we can reconstruct the date the original data. So, the data is indeed available. Right. So, what's the problem with with post-quantum security? The problem is that KZG is based on traditional cryptography building blocks.

It's based on on pairings operations and elliptic curves like BLS signatures are using. So, with quantum quantum adversaries, this is not very nice. Here in this slide I have an example. So, we have our super powerful quantum adversary, which is our proposer with a red dot. And this guy what can do can do the same thing of erasure coding the data from the blobs, but now he can forge a commitment that from a validator point of view, it's a valid commitment. But what can do we he can now send chunks of data that are not really valid for that commitment, even

though they look like valid. So, in this case the validator will verify the chunk and verify against the commitment and it will be happy. So, it looks good. But the problem is that encoding validity is broken. So, behind this commitment the data you are receiving is not binding to any real data. And data availability even is broken because if the validators try to reconstruct, they will reconstruct nothing or garbage. Good news. We have some alternatives to KZG.

Uh we can use something called hash-based polynomial commitment schemes that under the hood use uh hash functions which are uh resistant to quantum adversaries and they're plausibly post-quantum secure. But, there are some problems. So, let's first see uh a a valid candidate uh for this. And the valid candidate is uh FRI. is an interactive Oracle proofs of of proximity for uh codes.

And in very high level, I won't spend too much here, but it's a protocol uh between a prover and a verifier where the prover, you can think about it as a uh block proposer, and the prover can uh claim to know uh a valid uh piece of data that has been erasure coded. So, here you see as a an array of uh of uh elements. And this data is valid valid from the point of view of the commitment. So, the commitment here is not a KZG commitment anymore, but you can think about like uh Merkle tree use like commitment. So, you use Merkle trees, you commit to the data, and you share the commitment with

a verifier. And here the the initial commitment is just a few hashes, right? The root of the Merkle tree. Now, the protocol is interactive in the sense that uh the verifier wants to get convinced that the commitment is valid, and to do that, he will just ask positions uh of the initial data. So, we'll ask for position number uh one, position number 10, and uh with this interaction, the propo- the the prover will answer with the value of the position along with a proof. Where, since we're talking about Merkle trees, the proof is a is an opening uh of the Merkle trees.

We iterate this again and again until uh the verifier get convinced from a probabilistic point of view that uh the commitment is valid. And now we end up with this proximity proof. You see you see it on the on the right which is an object that includes commitment plus a bunch of openings, right? And this gives us a very good value of for encoding validity. But how about data availability?

Let's try to put FRI in a real practice in practice in a real use case. So this image is similar to what you saw before. We have a validator that is trying to sample. But now in a in a block we are not adding KZG commitment, but we have this proximity proof. And as you can see is very large. The proximity proof is distributed over a block to everyone and validators will receive it. When the validator sample a column, it will receive the sample object plus its own opening plus the commitment with the proximity proof.

That's a lot of data, isn't it? So from the network point of view it's a a huge overhead. And these large commitments is a are a bottleneck nowadays for for this solution. Just some trying apple to apple comparison. We implemented FRI we we compared it with KZG and you can see here the the example is for 21 blobs which is the state of the art of Osaka with maximum number of blobs available and with FRI with 128 queries in the proximity proof. This this is just for security. We can parameterize this.

But in this case you see that you we have a huge difference in terms of sizes in um dimension of 100 of kilobytes. So, what's the approach the intuition behind I'm presenting today? So, the approach is the following. By observing fries, we realize that fry has this interesting structure of um that can be distributed in terms of the verification point of view. And this is because the protocol is interactive. We can make it non-interactive, but let's say that the protocol is interactive in which very the verifier will ask one position and receives back the the value and the

proof. So, the intuition here is that we could split the proof for the proximity into small chunks, and we can ask a committee of trusted parties to verify those individual proofs. Now, what the result here is that every party in the committee will just verify a smaller proof. It's just a couple of openings. Uh in this example, it's just one. And provide an attestation. If the majority of if the whole committee provide attestation, then we we have a certificate, right?

And here again, we're talking about post-quantum stuff. So, we want this attestation to be post-quantum secure. We can use uh a post-quantum signature, uh which is around 3 kilobyte per signature, but we can aggregate them in a ZK-VM. Okay, so the committee gives us uh the certificate gives us the same uh security of a proximity test. And now, we need data availability. So, in practice, again, what we could do is that instead of putting the proximity proof within the block, we just put the commitment, which is a few hashes, and the certificate.

And we distribute it to the network. So, now from a validator perspective, when I want to sample cells and columns, sorry, what I have to do is just receive a single object, which is the object I'm sampling, plus the opening, because we are talking about Merkle trees, plus the commitment with the certificate. So, the verification is much lighter because I just verify a signature for the committee validity, and then my received opening. So, in this approach, we sample only for data availability, we don't sample for encoding validity. The encoding validity is offloaded to the committee.

We implemented it, and this is just an a rough example. So, in our distributed verification verifiable um verifiable approach, uh we we This diagram is for a committee of 100 validators in the committee that are providing a post-quantum signature that we can aggregate with a with a ZK-VM, and you see the advantage in in our case, the commit the commitment is around 100 KB. Of course, the sampling proof is the same, uh but is a is a big advantage in terms of uh network overhead.

And of course, we buy post-quantum security. There is no free lunch. Uh the problem here is that we are drifting from uh universal verification from another a different trust model, right? Here, we trust a committee of parties that have to perform the heavy lifting for us, and we trust them. So, encoding validity is on the committee, and the data availability is still on the on the global validator set. Uh of course, we could do better.

We could uh for example, um yeah, consider some threshold in the committee. So, let's say we have 2/3 of honesty in the committee, but this would require us to increase the the number of queries in the proximity test because you want some repetition to cover the 2/3. We do have a preliminary implementation of the scheme. So, if you guys want to have fun, you can go to our repo. You can benchmark both fry and the our distributed version of it. Uh there are some many parameters that you can use.

You can change the validator side the validate the sorry the committee sides and all the parameters that the fry protocol requires and observe different values in the results. Next steps. This is the most exciting part. Uh yeah, as I said, there are so many parameters that can be configured not only on the committee side, but also on the fry side because the protocol have many different parameters, repetition parameters for the encoding and all the stuff. So, very interesting is to benchmark everything.

Uh and try this with spot between the sides of the committee and also the the post-quantum signatures because they introduce some additional overhead uh that we have to balance when we talk about aggregating them and compared with the uh distribution of the fry protocol. So, in one side we increase the committee, on the other side uh and and reduce the complexity of fry, but we increase the complexity of the signature of the certificate. So, the sweet spot has to be found.

Um if the committee is corrupted, uh we could do something like fraud proofs where the validation will check that uh the committee is corrupted was corrupted and try to challenge it. And also another interesting part is that this protocol could be completely compatible with EPBS, where we have this delayed verification. And we introduce already the concept of committees in the protocol in the Ethereum protocol. This should be a thank you slide with my Yeah.

Thank you, guys. Yeah, hi. Thank you for the presentation. And thanks for benchmarks this. And I was wondering for the benchmark also for a while. And I'm wondering like like if I were using like it's kind of like a delegated like uh DA, right? So, if you already ask like 100 uh uh committee members to verify the uh encoding, right? So, why do we still need a fry here? We can just a simply like uh encode the data hash Merkle hash it. And then just let's this 100 uh

or which I it doesn't matter what's the size of your committee, right? Just download all the data and then decode it right? You mean to download you don't want them to download the whole data, right? Because potentially you want to increase the number of uh the number of blobs in in the data. So, you don't want to send the data over. No, no, no. I mean if like uh the DA is a Why we why we want the DA to be like uh minimum consumption on the bandwidth consumption? It's because we want like everyone join the network want to be the validator, they can download the data. So, we need to control this part. But if you are only have like just a 100 uh uh or I don't know how much like uh committee member needed to check the

encoding right? Then they don't need a fry. They can simply download the data. And it's just a 100 times the like blob size. It's not any overhead from the network at all. Yeah, again, it depends on the size of the blobs you're talking about, right? I mean, let's talking about what even 100 gigabit. How and then you you times with like one gigabit you times 100 is 100 gigabits. How how large it is? Yeah, but you still want to allow the sampling part, right? Yeah, but your sampling part only checks the data part, right? You only checks the data integrity actually. So it's basically uh With the commitment. Yes, so which means uh you you didn't check the encoding, right? By individual members. So which means any hash coming

like hash tree is already enough, right? I just open. It doesn't change that part, right? It's What I want to say is like if in this situation you don't really in your setting you don't really need a fry here. You can simply download all the data. It does the same exactly like outcome with fry but without fry and you you can get actually higher confidence. Uh yeah, probably can be a good approach, but I still believe that if you want to change the protocol then and increase the committee or change parameters in the committee, you still want the flexibility of the proximity test.

Okay yeah thanks. Thank you. No more questions.